Блог пользователя undefined_error_

Yet Another Multiple Problem
Автор undefined_error_, история, 5 лет назад, По-английски

I am trying to solve it for a while but didn't come up with a efficient idea. Any hints would be great. Problem Link: https://uva.onlinejudge.org/external/16/1653.pdf Thanks :)

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can solve this in O(N) using BFS.

Let your state be (current_mod, has_digit).

Start with state (0, false), and any transition to an allowed digit is ((current_mod * 10 + allowed_digit) % n, true). Iterate on allowed digits in ascending order.

Now you need the minimum path from (0, false) to (0, true).

→ Ответить