Gilgamesh_01's blog

By Gilgamesh_01, history, 5 years ago, In English

Hi everyone, I need help with this problem, I tried 3 days, but nothing work. The problem consists about find the x smallest múltiple of a number n, and x only consists of 0 and 1 for example n=2,x=10 and n=3,x=111.. please help I try brute force but it doesn't work

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

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

Constraints on n?

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

Maybe bfs works? Make $$$n$$$ points, denoting the remainder when $$$x$$$ modulo $$$n$$$ is $$$i$$$. We start bfs from 1, and find the shortest path to 0.

At the same time, note that when extending points, first add the point when using 0, then using 1.

(Inspired from 1209F)