Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 15.07.2010, 21:23
гость

 
Сообщений: n/a

Задача по числам
Подскажите идею решения.
Для заданного N (N<=1000) найти минимальное целое положительное число, которое делится на N, и сумма его цифр равна N.
  #2  
Старый 15.07.2010, 22:46
гость

 
Сообщений: n/a

длину перебираешь.

для генерации требуемого n-значного числа (слева направо генерация), используешь динамическое программирование. состояние - пара (сколько цифр уже сгенерировано, текущий остаток).
  #3  
Старый 15.07.2010, 22:47
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
(сколько цифр уже сгенерировано, текущий остаток).
еще сумму сгенерированных цифр
  #4  
Старый 15.07.2010, 22:51
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
еще сумму сгенерированных цифр
хотя не... число сгенерированных цифр - не надо в состояние, а то сильно много. Пусть это будет результат динамики, т.е. решай задачу (сумма цифр, остаток по модулю N) -> минимально возможное число цифр в таком числе.
  #5  
Старый 15.07.2010, 23:04
гость

 
Сообщений: n/a

А какие рекуррентные соотоношения будут? Т.е. как будут связаны между собой эти состояния?
  #6  
Старый 16.07.2010, 00:48
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
А какие рекуррентные соотоношения будут? Т.е. как будут связаны между собой эти состояния?
f[s, m] = 1 + \min_{0<=d<=9, d>=s} f[s-d, (10m+d)%N]

s - сумма цифр
m - модуль (- сгенерированная часть цифр слева имеет этот остаток, и требуется приписать цифры справа, чтобы свести его к нулюю
  #7  
Старый 16.07.2010, 00:50
гость

 
Сообщений: n/a

[quote=гость;12622]f[s, m] = 1 + \min_{0<=d<=9, d>=s} f[s-d, (10m+d)%N]
а с нулём беда, да... давай так: отдельно перебирай сколько нулей приписывать (больше 10 нет смысла), и затем цифру от d=1..9 по формуле выше.
  #8  
Старый 16.07.2010, 11:45
гость

 
Сообщений: n/a

Спасибо за советы. Попробую реализовать.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра