Сегодня прошел очный тур ИОИП.
После 18:00 (МСК), когда закончится 8 индивидуальная интернет-олимпиада на neerc.ifmo.ru/school/, проводимая по задачам ИОИП, предлагаю обсудить здесь решения и ожидаемые результаты (по правилам ИОИП за первые 5 попыток по задаче выдается количество баллов).
Предподсчитаем суммы на всех отрезках за О (n). Затем переберем число а и для каждого а бинарным поиском по ответу найдем лучшее решение. Сложность - О (n logn). Есть еще решение за линию, но я его не шибко понял.
Решение D на 100 баллов
Понятно, что любая тоговая конфигурация - группы подряд идущих единичек, разделенные одним нулем. Заметим, что при такой конфигурации мы приходим в группу, наступая обязательно на первый ее элемент, а уходим, наступая на последний. Кроме этого, переход между группами осуществляется ровно одним способом (перепрыгиванием через ноль). Пусть у нас есть P групп, длина i-й группы Li, количество способов ее пройти Bi. Тогда произведение всех Bi есть количество способов пройти через все группы от начала к концу, а сумма всех Li + P - 1 - суммарная длина всех групп (+P-1 берется потому, что в конце всех групп, кроме последней, стоит замыкающий ноль).
Получаем, что произведение всех Bi = k, а сумма всех Li + P = n + 1. Теперь надо найти любой такой набор групп.
Заметим, что Bi - это числа Фибоначчи. Преподсчитаем всевозможные Bi до 10^18 (их всего 87). После этого искомое разбиение на группы можно найти рекурсивным перебором.
Наверное потому, что k может и не быть числом Фибоначчи ;)
n = 7, k = 4
1110111
http://neerc.ifmo.ru/school/ioip/standings-2011.html
Неожиданно мало over 300...
UPD: думал первый буду)))
вот они
http://neerc.ifmo.ru/school/ioip/
отсюда можно попасть