Ответы пользователя по тегу Алгоритмы
  • Как подготовиться к олимпиаде?

    alexandret
    @alexandret
    Программист, программист, маркетолог
    Городской тур это уже хорошо :)
    Для начала выбрать язык. Есть несколько популярных вариантов: python, C, Pascal.
    Я бы рекомендовала python как самый быстрый.
    Требуется:
    1) Запомнить особенности ввода-вывода как с экрана так и из файла. Не поленитесь и разберитесь с тем как считывать из файла и как в файл записывать.
    2) Написать 3-4 задачек на if-elif-else mccme.informatics.ru в помощь
    3) Написать 3-4 задачки на циклы и массивы.
    4) Надо знать хотя бы один алгоритм сортировки. В python надо знать, что существует встроенная сортировка
    5) Если вдруг останется время почитайте алгоритмы на графах. Как графы хранятся в памяти, bfs, dfs.

    6) Будьте готовы читать внимательно.
    7) Высыпайтесь :)

    По опыту составления олимпиад. Мы почти всегда стараемся сделать хотя бы одну задачку, в которой для решения достаточно уметь считывать с экрана, уметь делать расчеты доступные любому школьнику, знающему математику на уровне 5 класса, уметь использовать if и в конце уметь выводить результат на экран.

    Я не могу гарантировать, что в вашем наборе задач этого будет достаточно. Просто расслабьтесь и получайте удовольствие :)
    Ответ написан
    1 комментарий
  • Как решить данную задачу за O(log(n)*n)?

    alexandret
    @alexandret
    Программист, программист, маркетолог
    Эту задачу можно решить методом сканирующей прямой. Добавьте для каждого круга на окружность 2 точки: точку первого пересечения с прямой и точку второго пересечения с прямой. Точка это на самом деле структура, которая знает свою координату, к какой окружности она относится и является ли она точкой с меньшей или с большей координатой х для этой прямой)
    За N log N сортируем окружности по значениям X.
    Далее просматриваем все окружности. На каждом шаге нам надо решить как обновить число пересечений. Далее порисуйте варианты на листочке и найдите решение :)
    Ответ написан
    Комментировать