основной форум
Архив сообщений 2004-2006 года

Алгоритмы, методы, исходники


Олимпиады >> Задачи

Страницы: 1
log
новичок
*

Рег.: 09/09/06
Сообщений: 3
Из: ---
Помогите с задачей
      #12056 - 09/09/06 10:12 AM

Найти наименьшее число, в десятичной записи которых присутствуют разряды только из заданного набора, для которого известно - сумма его цифр равна N и оно делится на M.
Как ее решить с помощью ДП, интересен переход из одного состояния в другое


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
ulan
новичок


Рег.: 11/25/04
Сообщений: 1
Из: Кыргызстан
Re: Помогите с задачей [Re: log]
      #12058 - 09/10/06 02:13 AM

Просматриваем числа в порядке возрастания десятичных знаков, состоянием будет булевский массив exists[K][N+1][M], где exists[k][s][r] обозначает существование k-значного числа с суммой цифр s и остатком r.
Code:

// База
for (int i = 0; i < digits.size(); ++i)
exists[1][digits[i]][digits[i] % M] = true;
// Переход
for (int k = 2; ; ++k)
{
if (exists[k-1][N][0]) break;
for (int s = 0; s <= N; ++s)
for (int r = 0; r < M; ++r)
if (exists[k-1][s][r])
for (int i = 0; i < digits.size(); ++i)
if (s + digits[i] <= N)
exists[k][s + digits[i]][((r * 10) + digits[i])%M] = true;
}


Нужно еще добавить обработку случая, когда нет решения, и вывод числа.
Задачу можно решить за O(N*M) времени и памяти (если оптимизировать приведенный код).


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
log
новичок
*

Рег.: 09/09/06
Сообщений: 3
Из: ---
Re: Помогите с задачей [Re: ulan]
      #12063 - 09/10/06 10:36 AM

Основная сложность в восстановлении числа, так как нужно наим. число с трубуемым свойством!
Если хранить в состоянии число, то необходима длинная арифметика что увеличивает время работы программы...
Как же поступить в данном случае?


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Gleb_Grenkin
здесь был не раз


Рег.: 07/27/04
Сообщений: 32
Из: Vladivostok, Russia
Re: Помогите с задачей [Re: log]
      #12064 - 09/10/06 12:24 PM

Для каждого состояния хранить предшественника.
При выводе числа сначала восстановить всю цепочку добавляемых цифр, а потом пойти от начала цепочки.


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
log
новичок
*

Рег.: 09/09/06
Сообщений: 3
Из: ---
Re: Помогите с задачей [Re: Gleb_Grenkin]
      #12067 - 09/11/06 09:32 AM

При таком подходе не получается наим. число!
Что же делать?


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
juver
здесь был не раз


Рег.: 06/21/06
Сообщений: 29
Из: Челябинск
Re: Помогите с задачей [Re: log]
      #12068 - 09/11/06 11:18 AM

Задача с заочного тура личной олимпиады.
Просьба закрыть тему


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Страницы: 1



Дополнительная информация
0 зарегистрированных и 413 анонимных пользователей просматривают этот форум.

Модератор:  Илья Кантор, Sergeyev, M_Gustokashin 

Распечатать тему

Права
      Вы не можете создавать новые темы
      Вы не можете отвечать на сообщения
      HTML выключен
      UBBCode включен

Рейтинг:
Просмотры темы: 12159

Rate this topic

Переход в