Вот и закончился САБЖ. Ожидаемые 99 из 99 я заработал, угробив на все 4:55 (включая 20 минут пеналей за ошибочные попытки). Скорее всего можно было бы и быстрее, но в сонном состоянии башка работала медленно и концентрации не хватало (поэтому допускал мелкие, но пакостные ошибки в исходных вариантах решения). Наиболее интересной оказалась вторая задача, на которую было угроблено часа 2.5. Пришлось вспоминать азы теории чисел. :) Плюс дополнительной засадой оказалось наличие чисел порядка 10^50 в большом сете: уже начав писать алгоритм на плюсах, уперся в то, что под рукой нет ни одной библиотеки больших чисел. А писать свою реализацию в 6 утра после 20 часов бодрствования ну совсем не хотелось. Пришлось переписать все заново на C#, для которого, к счастью, в 4-м фреймворке есть готовая реализация BigInteger. :D.
Во время отладки 3-ей задачи оценил-таки удобства "прилепленных" вотчей нового дебагера 2010-ой студии. Отлаживать цикл с состоянием на 4-х векторах с ними оказалось весьма удобно. ;)
Посмотрим, что будет в следующих раундах.
а если вкратце, каков алгоритм второй задачи? Просто в ней у меня не было вообще никаких идей.
ОтветитьУдалитьВкратце: нужно было заметить, что
ОтветитьУдалить(Ti-Tj) mod T == 0. Причем, независимых уравнений только N-1, то есть можно взять одно время (я брал минимальное) и получить N-1 уравнение (Ti-Tmin) mod T = 0. Отсюда видно, что T - делитель каждого Ti=Tmin, то есть максимальное T - это НОД от всех Ti-Tmin.
Найдя T, находим y:
Tmin mod T + y mod T = 0, => y mod T = - Tmin mod T. Если Tmin mod T = 0, то y =0, иначе
y = T - Tmin mod T.
Кстати, на сайте уже анализ задач выложили. :)