А есть ли где-нибудь задача о счастливых билетах (тех у которых равны суммы цифр в половинках) со сравнительно большими ограничениями (больше тех которые на первом курсе в каждом втором вузе предлагают)? Ну в духе сколько есть счастливых билетов с 30-значным номером в 16-ричной системе счисления?
Гугл выдал пару ссылок на Тимус: 1044 из них простая, а 1036 вроде бы близко к тому что я ищу, но там предлагается считать билеты с заданной суммой и я, кажется, не пойму, насколько от этого становится проще / сложнее...
Ну так переберем сумму первой половинки (в Вашем случае она не превышеат (30/2)*15) и динамикой посчитаем, сколько есть способов получить эту сумму. Ответ — сумма квадратов по каждой сумме первой половинки
Так я хотел знать где её сдать можно %)
Решение-то я и придумал динамикой, хоть по суммам не догадался а хм... этакий многомерный треугольник Паскаля нарисовал.
Точно, проглядел.
Не знаю, как у остальных, а моему решении 1036 (очевидно, рюкзак) от того, что сумма задана, ни холодно, ни жарко. Разница только в том, что надо вывести DP[n][s] * DP[n][s] вместо суммы таких значений по всем возможным s.
Есть здесь 203 задача с acm.mipt.ru, до 400-значного номера
И на acmp есть задача: 100
Вот такая хорошая задача есть: http://acm.timus.ru/problem.aspx?space=1&num=1217