Lara_Croft's blog

Could you please give me a hint for this problem?
By Lara_Croft, history, 9 years ago, In English

I looked up everywhere but couldn't find a tutorial for this gym contest (VIII Open Programming Championship of Kazan Federal University 2015), and so I'm stuck at problem J Polycarp and Dividend. It looks easy but I couldn't find the solution. Could anyone help me or at least give me a hint?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Construct a graph with A vertices, each representing its number. From any vertex, can go to any vertex with number CurrentVertexNumber * 10 + a[i] mod A for i < n, where a is the array of usable digits. Now your task is to find the shortest path from vertex 0 to vertex 0 (A mod A) and print that path.
Beware from starting with digit zero.
Good luck!

→ Reply