|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
19.01.2017, 16:22 | #11 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Там для N=100 и K=3 вообще немыслимое количество возможных чисел - 3^100. Так что перебор вообще нереален и только хитрый алгоритм ))
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
19.01.2017, 16:52 | #12 | |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,309
|
Цитата:
Как вариант: 1. Формируем массив из 10 элементов. Выделяем цифры числа и инкрементируем соответствующий элемент массива и считаем сумму цифр. 2. Если сумма нечетная - это несчастливый билет. 3. Если сумма четная, то просматриваем элементы массива. Те элементы, в которых число цифр четное инициируем нулем, а те, в которых число цифр нечетное - инициируем единицей. 4. Ищем сумму оставшихся цифр. Если сумма нечетная - это несчастливый билет. 5. Если сумма четная, то перебираем варианты. Тут вроде и о рюкзаке можно подумать. 6. Поскольку набор оставшихся цифр ограничен и известна сумма, которую надо получить, то решение может быть найдено достаточно быстро. Любой вариант, когда сумма складывается, дает счастливый билет. PS: Поправьте, если что не так. Такой алгоритм только что в голову стукнул и некогда попробовать. Как-то так, ...
Как-то так, ...
|
|
19.01.2017, 21:07 | #13 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Мне кажется, что здесь расширение обычных "счастливых билетов".
Те ведь как искались (например, для N=6): - для группы из 3 (6/2=3) цифр искались все возможные суммы цифр перебором. - получался массив S[0...27], каждый элемент которого был равен количеству чисел из 3 цифр, сумма которых равна данному индексу массива. - в цикле перемножали S[i]*S[i] и суммировали произведения. Итоговая сумма была ответом. Так может и здесь требуется получить матрицу S[i,j], элемент которой равен количеству чисел длиной j, сумма цифр которых равна i. Далее перемножая S[i,j]*S[i,N-j] и суммируя произведения получим Количество счастливых билетов. После вычитания из 10^N этого количества получим ответ. Матрица для N=100 будет достаточно значительной S[0..9*100, 1..99] ~90тыс элементов и ещё и по форме - треугольной, заполненной наполовину. Её элементы, возможно, будут длинными числами. Но это всё равно будет быстрее, чем простой перебор. Осталось сообразить, как заполнять матрицу на основе ранее заполненных ячеек. |
30.01.2017, 10:03 | #14 |
Форумчанин
Регистрация: 13.05.2016
Сообщений: 111
|
Нашел код на Phyton'e. Его вообще не изучал. Мб кто-то может переделать под C#/C++?
Код:
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Железнодорожные билеты - C++ | Sayroxx | Общие вопросы C/C++ | 1 | 20.10.2015 09:02 |
Билеты по схемотехнике | Salec | Фриланс | 0 | 10.01.2013 00:43 |
Билеты на мюзикл | hewlett | Помощь студентам | 6 | 09.05.2012 16:23 |