undefined_error_'s blog

Yet Another Multiple Problem
By undefined_error_, history, 5 years ago, In English

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 :)

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

→ Reply