Блог

Главная - Вопросы по программированию - Как найти минимальное кратное, учитывая неполное число, без использования грубой силы

Как найти минимальное кратное, учитывая неполное число, без использования грубой силы

#algorithm

#алгоритм

Вопрос:

Я просто хочу получить направление в этой задаче программирования от онлайн-судьи (URI online judge — 2699). Учитывая два числа, S и N, S является неполным, поэтому S может быть задано в форме ?294?? если первая цифра не равна нулю, мне нужно найти минимальное число, которое имеет те же цифры, что и S, и кратно N. Если это невозможно, то вы просто возвращаете * . S может содержать до 1000 цифр и N < 1000.

Я опишу свои попытки:

  1. Грубая сила: я пробую каждую комбинацию чисел и получаю первое, кратное N. Поиск решения, когда оно существует, вообще не проблема, но обнаружение того, что решения не существует, когда S велико, может быть действительно проблематичным и занимать бесконечное время.
  2. Грубая сила, но оптимизация формы нахождения остальных: в этой попытке я сохраняю в массив оставшуюся часть деления для цифры 1 в позиции i, поэтому для i = 3 в v [3] у меня будет 1000% N. Зная, что (AB) MOD N = ((A MOD N) B) MOD N, можно довольно быстро написать массив и оптимизировать способ вычисления модуля S, который. Эта попытка действительно увеличивает время, но является попыткой грубой силы и имеет те же проблемы, что и предыдущая.
  3. Используя остаток для выполнения рекурсии: Например: если у меня есть число?294?? в S я получаю остаток от 29400 и вычисляю, сколько нужно, чтобы иметь кратное (N — rem), затем я пытаюсь получить все это с первой цифры, если это невозможно, тогда я уменьшаю, сколько я хочу, и повторяю попытку, затем я иду влево ипопробуйте с другим числом. Например, если мне нужно 7, чтобы достичь N, и я могу получить 5 с первой цифрой, тогда я попытаюсь найти 2 во второй цифре и так далее.

Есть ли у него концепция, которую я здесь не вижу? Я пытаюсь решить эту проблему почти 3 дня, ищу способы сделать это и ничего не добиваюсь из-за нехватки времени.

РЕДАКТИРОВАТЬ: Спасибо за комментарии, подумав весь день об этой проблеме и прочитав много динамического программирования, я мог бы найти способ применить DP в этой проблеме, я не буду точно говорить, как, но ключ в том, чтобы понять DP и найти способ уменьшить размер вашей проблемы.

Комментарии:

1. После первого прочтения вашего сообщения мне кажется, что это dynamic programming проблема. Если вы не знаете, что это такое, пожалуйста, прочитайте об этом. Если вы уже знаете, что такое DP, пожалуйста, подайте заявку, и это должно решить вашу проблему с превышением лимита времени.

2. @ShridharRKulkarni к какому свойству вы бы применили DP?

3. Если не dp, это может быть сложно, может быть adhoc.. Я перечитаю сообщение, уделю немного времени и подумаю еще раз на досуге.