|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
19.01.2017, 14:07 | #1 |
Форумчанин
Регистрация: 13.05.2016
Сообщений: 111
|
Несчастливые билеты
Здравствуйте. Пожалуйста помогите с задачей.
Необходимо определить количество несчастливых N-значных номеров, которые можно составить, используя цифры от 0 до K. В номерах допускается любое количество ведущих нулей. Номер билета является счастливым, если сумма некоторых цифр этого номера равняется сумме оставшихся, к примеру: билет с номером 561743 счастливый, так как 5+1+4+3=6+7. Хотя-бы опишите алгоритм словесно, а то сложнота какая-то. |
19.01.2017, 14:12 | #2 |
2 the Nation Glory
Старожил
Регистрация: 27.05.2014
Сообщений: 3,289
|
Кто умер, но не забыт, тот бессмертен.
Лао-Цзы. |
19.01.2017, 14:20 | #3 |
Форумчанин
Регистрация: 13.05.2016
Сообщений: 111
|
Эти алгоритмы я находил не раз, в моей задаче понимание "счастливых билетов" другое. Повторюсь: Номер билета является счастливым, если сумма некоторых цифр этого номера равняется сумме оставшихся, к примеру: билет с номером 561743 счастливый, так как 5+1+4+3=6+7.
Последний раз редактировалось Kef1r; 19.01.2017 в 14:45. |
19.01.2017, 14:27 | #4 |
Форумчанин
Регистрация: 14.02.2013
Сообщений: 222
|
|
19.01.2017, 15:02 | #5 | ||
Старожил
Регистрация: 09.01.2008
Сообщений: 26,238
|
или я что-то упускаю, или....
Цитата:
но, перебирать все варианты для каждого из чисел в диапазоне от 000..<n>..0 до KKKK. <n>...KKK - это займёт тучу времени (для достаточно больших N, конечно). кстати, а есть ограничение на N ? суда по всему это задачка $435 c acmp.ru ? так там есть ограничения: Цитата:
Последний раз редактировалось Serge_Bliznykov; 19.01.2017 в 15:04. |
||
19.01.2017, 15:10 | #6 |
Форумчанин
Регистрация: 13.05.2016
Сообщений: 111
|
|
19.01.2017, 15:21 | #7 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,238
|
я почитал обсуждение на acmp.ru.
Дело в том, что, думаю, что существует какой-то алгоритм решения, до которого нужно додуматься (скорее всего, используя ДП). но я, например, не вижу этого алгоритма. Можно, конечно, решить задачу "в лоб", просто перебором, но тогда будьте готовы к тому, что ваша программа для подсчёта будет работать непрерывно несколько часов. а ещё, там, по моему, длинная арифметика нужна. в примере на acmp.ru для N=11 и K=9 ответ 50184219171 очевидно, что при возрастании N число ответов тоже будет сильно возрастать. |
19.01.2017, 15:28 | #8 | |
Форумчанин
Регистрация: 13.05.2016
Сообщений: 111
|
Цитата:
|
|
19.01.2017, 15:47 | #9 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,238
|
|
19.01.2017, 15:54 | #10 |
Форумчанин
Регистрация: 13.05.2016
Сообщений: 111
|
|
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Железнодорожные билеты - C++ | Sayroxx | Общие вопросы C/C++ | 1 | 20.10.2015 09:02 |
Билеты по схемотехнике | Salec | Фриланс | 0 | 10.01.2013 00:43 |
Билеты на мюзикл | hewlett | Помощь студентам | 6 | 09.05.2012 16:23 |