А есть ссылка на условия? А то не выходило зайти.

Заметим, что первые n-m цифр делятся на p (p — последние m цифр), если p не равно 2 и 5(разбирается отдельно). Перебираем все простые числа длины m. Дальше бинпоиском находим такую верхнюю и нижнюю границу, что первая цифра равна последней.

Есть подозрение что решение такое: Если взять число из первых Н-М цифр, то оно должно делится на простое образованное последними М цифрами, за исключением М=2 и М=5. Дальше вроде-бы очевидно как: перебираем простое число , ставим первой цифрой последнюю цифру заданного простого и считаем кол-во таких окончаний что-бы было кратно, что должно быть не сложно.

Я делал так: находим все простые числа длины m(решетом Эратосфена), а затем для каждого простого числа выполняю следующую процедуру: находим наименьшее(min) и наибольшее(max) из чисел длины n, m последних разрядов которого равны данному простому числу(наименьшее имеет вид p000...prime, где p — последняя цифра простого числа, prime -само простое число, наибольшее — такое же, но вместо нулей девятки). После этого нахожу левую и правую границу left = min / prime, right = max / prime (если min не делится на prime, увеличивам min на единицу). После этого остается посчитать кол-во чисел вида x...0...01(где последовательность 0..01 имеет длину m), принадлежих интервалу от left до right (назовем их кол-во K, подсчет их количества за O(1)). Тогда сумма K для всех простых чисел длины m — и есть ответ.

dp[i][v] — За сколько дроблений можно получить сумму v, используя первые i товаров.

Берем i-ый товар. Перебираем все простые делители числа i. Пусть очередное простое число — p. В сумму вклад i-ого товара будет a=goods[i]/p. Для любой цены t: dp[i][t + a] = min(dp[i — 1][t] + 1, dp[i][t + a]); или же dp[i][t + a] = min(dp[i — 1][t], dp[i][t + a]); если не "дробим".

Можно хранить только dp[v], как в рюкзаке.

Извиняюсь, за неумением юзать тех.

также приведенное выше решение можно немного соптимизировать: если сумма всех чисел меньше sum, то сразу выводим 0, иначе считаем приведенное ниже дп, но уже не для весов до 10⁶, а до 10⁵ так как сумма всех чисел не превысит 10⁵

лекци по програмированию точно будут, в анкете регистрации спрашивали что больше хотелось бы послушать из этого списка:

• Объединяемые структуры данных
• Декартовы деревья (в т. ч. по неявному ключу)
• Дерево отрезков. Групповые операции в дереве отрезков и нетривиальные применения дерева отрезков
• Совершенная Хеш Таблица
• Статические струкрутры RSQ (n-мерные), RMQ
• Потоки. Алгоритм Эдмонса Карпа, Динницы и Хопкрафта-Карпа
• Компаненты силной связности (двусвязности вершинной и реб ерной)
• Жадные алгоритмы. Матроиды. Примеры матроидов. Общие алгоритмы для матроидов
• Обход в глубину. Использование времен входа и выхода

Был в этой школе в прошлом году.

Поселение: Общежитие квартирного типа с кухней, минусы — отсутствие холодильника(правда под эту роль мы приспособили занесенный снегом балкон) и довольно прохладный климат. В смысле, что был дубак, особенно ночью. Это все можно пережить. До корпуса, в котором проходили занятия минут 10 ходьбы.

Питание: Вот тут все шикарно! Столовая просто замечательная, и питаться там одно удовольствие. Если же вечером проголодался — рядом с общежитием есть круглосуточный магазин и subway. Расписание питания — 9:00, 15:00 и 18:00 (по-моему).

Контесты: Контесты проводились каждый день с 10:00 до 14:30, вроде бы. Система для проведения контестов — старый добрый codeforces. Также можно было помаяться фигней, выводя кого-нибудь в топ по вкладу :] К слову о качестве/некачестве контестов. Первый контест был проведен для разделения на 2 группы(А и В). Проще говоря, в А попадали школьники примерно уровня параллели B в ЛКШ. Остальные контесты были ориентированы на прочитанные днем ранее лекции. Давалось 2-3 задачи уровня первых задач Div.2, остальные были уже по темам, прочитанным ранее. ИМХО это связано с тем, что народ набрался оочень разный(кто-то сдавал все задачи, кто-то уровня writeln(a+b)). Наверное, поэтому в этом году отбор и проводился. Хотя остается непонятным, по какому принципу выбирались школьники ^^

Лекции: Каждый день было две лекции по 2 часа каждая. Они были довольно занимательны. Конечно же, проводилась агитация в духе "ФИВТ МФТИ лучший в мире", но лекции были стоящими. Очень интересные, некоторые из них не относились к олимпиадному программированию, но это тоже круто. Единственный минус — к семи часам вечера мозг яро сопротивляется функционировать

Что-то еще: НЕТ ОТБОЯ! И это ооооочень классно ;D