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

Автор riadwaw, история, 7 лет назад, По-английски

Tomorrow is GP of Dolgoprudny which is prepared by my colleagues and me.

Hope, you'll like the problems which we can discuss here after the contest.

Also, we've prepared mini-tutorial which I'll post here after the contest too.

Good luck!

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

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

Кажется, провести опенкап вышло неплохим отвлекающим маневром :)

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

My solutions for problems I had solutions.

A
B
C
D
E
F
G
H
J
K
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как решать L и O из див2? (О квадрате из прямоугольников и о сокращении дроби). Спасибо.

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

    L. Начиная с последних цифр изменять отдельно числитель и знаменатель дроби. Каждый раз когда они увеличиваються — упрощать (делить оба на 2, 3, 5, 7 <10, т.к. A[i] и B[i] < 10), пока дробь становиться неупрощаемой.

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

      Ничего не понял? Я вообще думал , что надо начиная снизу все время получать общие знаменатели и в конце вывести формулу. Но ничего не вышло.

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

        Да, верно, так и надо. Только еще надо упрощать, например: 2/4 => 1/2.

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

    O. Прямое решение: создать матрицу 301 x 301, заполненую 0. По двум осям (x, y) заполнить единичками. Далее рекурсия: 1) ищим уголки (в начале ровно один — x=1, y=1), 2) от каждого уголка засыпаем единичками прямоугольник двумя вариантами (повернутый и не). Посли засыпки 3 прямоугольников, проверяем от x=1, y=1 — засыпан ли квадрат.

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

      К тому же перед посылкой забыл изменить 15 на 301, но получил AC. Потом взломал себя — код выдает YES на тест "3 3\n3 6\n9 6\n" и NO на "30 30\n30 60\n90 60\n".

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

      Поясните пожалуйста как Вы делаете заливку на входном тесте 8 2 1 6 6 7 с каких уголков?

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

        Заливка с аналогичным тестом (ideone, Perl). Переберая все возможные уголки с поиском по рекурсие.

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

Как решалась задача P. No Triangles ?

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

    Надо вычеркнуть числа не являющиеся фиббоначи.

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

      1 2 3 4 5 6 вычеркиваем 4 и 6 ответ 2

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

        Спасибо. А почему именно их?

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

          Уже понял. Из-за неравенства треугольника. Рассмотрим самое большое число Фибоначчи — fib[i], которое меньше, либо равно n. Оно не может быть стороной треугольника, потому что оно равно сумме двух предыдущих чисел фибоначчи: fib[i-1], fib[i-2]. А все остальные суммы будут меньше. Поэтому мы переходим к числу fib[i-1] и повторяем рассуждения.

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

Nice problem set. May I ask why do you make B with n = 104? I think it's more fair to have n = 5, 000 for O(n2) solution.

With n = 104, we should be extremely careful with the constant involved in the computation.

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

    It was made to prevent solutions with complexity. Sorry if you had to spend much time optimizing your solution.

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

Can you provide the contest link please?