Gilgamesh_01's blog

By Gilgamesh_01, history, 4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Gilgamesh_01 (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Constraints on n?

»
4 weeks 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)