ONEZERO - Ones and zeros

Certain positive integers have their decimal representation consisting only of ones and zeros, and having at least one digit one, e.g. 101. If a positive integer does not have such a property, one can try to multiply it by some positive integer to find out whether the product has this property.


Number K of test cases (K is approximately 1000);
in each of the next K lines there is one integer n (1 <= n <= 20000)


For each test case, your program should compute the smallest multiple of the number n consisting only of digits 1 and 0 (beginning with 1).



hide comments
piyush9620: 2016-10-16 18:16:41

instead of using bfs, we can use a counter. counter is basically a number counter.
but when u notice carefully, 1 -> 1, 2 -> 10, 3 -> 11, 4 -> 100 .... the binary representation of the counter value converted into equivalent decimal value can help us solve the problem. eg when value of counter is 5 -> 101 in binary, the number which we want would be 101 in decimal.

rohitranjan017: 2016-09-03 16:51:31

BFS + Backtracking !
AC ! :)

Sarthak Munshi: 2016-09-02 17:55:18

storing string or integer is trivial . Just store the remainder of leftchild%n and rightchild%n and check each of those to be 0 .

sonupmandal: 2016-08-19 12:39:17

backtracking :)

Last edit: 2016-08-19 12:56:01
vaibhavi760: 2016-08-14 12:39:19

weak test cases
try 999.

malibarbar: 2016-08-12 19:26:40

Got AC in one, 0,98
Check modular arithmetic

a_thinker: 2016-07-14 13:26:43

@candide how would that make a difference if we do bfs ending with the left most digits or bfs ending with the right most digits ?

invincible_rm: 2016-07-05 19:41:32

Used the Queue n the Modulo(n states) n Backtracked for number

Last edit: 2016-07-05 19:44:07
ajay_5097: 2016-05-26 17:13:42

easy one !! 2nd on bfs ! :)

candide: 2016-05-16 01:58:46

@kartikay singh: "Wonder,how ppl did it in 0.00s??"

Response: I did using a bfs ending with the left most digits of the number we are asked for. On the contrary, the most common and intuitive bfs method ends with the right most digit, and even optimised the later bfs needs 0.02s or more (checked 2017/03). Perphaps there exists a more mathematical (and ad hoc) method.

Last edit: 2017-03-25 00:58:41

Added by:PaweĊ‚ Dobrzycki
Time limit:8s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:II Polish Olympiad in Informatics, Ist Stage