Привет, 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.
Why not codeforces?
Как решать F?
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. Предпосчитаем их коэффициенты.
Есть какая-то закономерность в этих числах? Можно доказать, что их достаточно?
Насчет доказать я не знаю. Просто перебрали : )
Можно написать перебор так, что очевидно, что он находит все такие числа.
А именно, нам нужно уметь представлять число 1 как сумму дробей вида 1/k_i(тогда к списку ответов нужно добавить lcm(k_i). При этом, каждый раз, когда мы добавляем очередное число, а осталось набрать число s с помощью t чисел, мы знаем, что существует одно из слагаемых 1/k >= s/t, т.е k <= t / s
Чтобы он заработал быстро, возможно, нужны отсечения, хотя для 7 может быть и укладывалось, не помню.
How to solve B, C and K?
Editorial
How to solve G?
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?