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

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

Привет, codeforces!

18 ноября в рамках MIPT-2015 ACM ICPC Workshop мы провели контест от нашей компании. В команду разработчиков задач вошли: zeliboba, gchebanov, Kostroma, riadwaw, yarrr, ValenKof, ArtDitel, Endagorion.

В воскресенье, 29 ноября, в 11-00 МСК будет проведена неофициальная трансляция этого соревнования на платформе Яндекс.Контест. Приглашаем поучаствовать всех желающих! Уверены, что каждый найдёт интересные для себя задачи в этом проблемсете.

P.S. Про MIPT-2015 ACM ICPC Workshop можно прочитать в блоге Rubanenko.

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

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

Why not codeforces?

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

Как решать F?

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

    2 : 2

    3 : 3 4

    4 : 4 6 10

    5 : 5 6 8 9 14 21

    6 : 6 8 10 14 44 52

    7 : 7 8 9 10 12 15 22 33 39 52 55 68 102 114 138

    Перебором найдем закономерность всех хороших чисел. Выше список. Например число можно разбить на 4 слагаемые то оно делится либо на 4, на 6 либо на 10. Для всех чисел кроме K = 7 мы можем посчитать включением/исключением. Для K = 7 различных lcm получится примерно 8000. Предпосчитаем их коэффициенты.

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

      Есть какая-то закономерность в этих числах? Можно доказать, что их достаточно?

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

        Насчет доказать я не знаю. Просто перебрали : )

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

        Можно написать перебор так, что очевидно, что он находит все такие числа.

        А именно, нам нужно уметь представлять число 1 как сумму дробей вида 1/k_i(тогда к списку ответов нужно добавить lcm(k_i). При этом, каждый раз, когда мы добавляем очередное число, а осталось набрать число s с помощью t чисел, мы знаем, что существует одно из слагаемых 1/k >= s/t, т.е k <= t / s

        Чтобы он заработал быстро, возможно, нужны отсечения, хотя для 7 может быть и укладывалось, не помню.

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

How to solve B, C and K?

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

How to solve G?

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

    There's one solution in editorial provided by Tima

    Few hints to another solution(suppose a>0, simmetrical case is similar):

    Let's find minimal x such that sin(ax)=0
    Let's do it using binary search.

    We need to points such points l, r such that minimal such x is between them, and between them there's exactly one such x. How do we choose l? How to find r?