Блог пользователя Yury_Bandarchuk

Автор Yury_Bandarchuk, 11 лет назад, По-русски

С 13 по 16 января проходила областная олимпиада по информатике. Предлагаю здесь делиться резами и обсуждать задачи:)

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

как решать 3 второго дня на 100?

  • »
    »
    11 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    Пусть мы нашли прямоугольник, в котором столько же деревьев, сколько в оптимальном ответе. Понятно, что сверху он упирается в какой-то прямоугольник, т.к. в противном случае, сдвинем его вверх и улучшим ответ. Аналогичные рассуждения проведем и для сдвига влево. Теперь переберем пару прямоугольников и предполагаем, что наш ответ упирается в первый сверху/снизу, а во второй справа/слева. То есть у нас есть O(K^2) кандидатов на ответ. Перебираем их все и за O(K) считаем сколько в них деревьев. Итоговая сложность O(K^3).

»
11 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Интересно, в каком-нибудь из регионов 45% участников удалось набрать не менее 50% баллов?

»
11 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

кто-нибудь выложите условия олимпиады пожалуйста

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Вряд ли кто из участников выложит. Разве что жюри. Просто архива нет. 17 января должны на http://dl.gsu.by/ выложить.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как решать 4 первого тура на 100?

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

    тут есть 3 случая. Если из кого либо числа извлекается квадратный корень то он ответ. так же если мы разложим число на простые множители до 10^6 и степень одного из них больше 1 то ответ этот простой делитель. дальше смотрим все пары и их нод. если нод не 1 то ответ будет наш нод. Почему можно смотреть делитель до миллиона. Ну так как простых делителей больших кубического корня будет строго меньше 3.

»
11 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Вот тут есть немного про задачи и их решения: http://tooruichii.wordpress.com/2014/01/16/regionals-2014/