Задача «Несчастливые билеты» РОИ 2008 Автор задачи: Владимир Алексеевич Кузнецов Разбор: Федор Николаевич Царев

Общий подход Две части решения: –Проверка «несчастливости» номера –Перебор номеров Обе части могут быть реализованы двумя способами

Проверка номера Задан билет с номером d 1 d 2 d 3 …d n Пусть S = d 1 + d 2 + d 3 +…+ d n Проверить, что не существует поднабора цифр числа, сумма по которому равна S/2». Решим противоположную задачу – «проверить, существует ли поднабор цифр числа, сумма по которому равна S/2» Задача о сумме подмножеств – известная NP-полная задача (подробнее об NP-полных задачах – см. google.com) Ее иногда не совсем правильно называют «задача о рюкзаке»

Задача о сумме подмножеств Решение описано в книге Шень А. Программирование: теоремы и задачи. – М.: МЦНМО, и на сайте раздел «Динамическое программирование» Два варианта: –Перебор за O(2 n ) –Динамическое программирование – O((k+1)n 2 )

40 баллов Перебор всех номеров за O((k+1) n ) Решение задачи о рюкзаке любым способом Позволяет вычислить ответ для восьми тестов

100 баллов Важен не сам номер, а мультимножество его цифр Пусть в номере можно использовать цифры от 0 до d, цифра 0 может входить в номер n 0 раз, цифра 1 может входить в номер n 1 раз, …, цифра d может входить в номер n d раз, при этом

Вычисление числа номеров по мультимножеству цифр Цифра 0 способов расставить Цифра 1 способов расставить на оставшихся позициях … Цифра d способов расставить на оставшихся позициях

Правильное решение Перебор мультимножеств Решение задачи о рюкзаке динамическим программированием Отсечение по сумме цифр – любой билет с нечетной суммой цифр является «несчастливым» Все 20 ответов вычисляются примерно за 5 минут

85 баллов Правильное решение без «длинной» арифметики

Частные случаи K = 1 : 10 баллов K = 2 : 15 баллов