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
khoaph: 2022-06-01 10:32:00

If n = 8, the result will be 1000

yasser1110: 2021-08-11 13:57:28

The question is good but I/O bounds should have been mentioned more clearly. Since the questioner has not bothered to provide that information let me provide it to you.

1 <= n <= 20000

may not fit in long long int

yzs: 2020-10-11 09:18:22

simple bfs to consider all possible permutations of 0 and 1, starting with 1. :)

knight_27: 2020-06-27 01:56:52

it is beautiful to understand a proof that an answer always exists

nandadeep_2001: 2020-06-12 13:16:16

can anyone explain the algorithm

cpp219: 2020-05-30 16:06:17

ez from LMH

aryan__0406: 2020-05-07 23:48:13

Good Question. Worth it!

aryan__0406: 2020-05-06 20:47:27

Every number till 20000 don't have such property such as 8.So in test cases only those numbers will be given which are valid.So chill!

cheesy: 2020-04-28 15:28:44

Is it guaranteed that an answer will exist?

ajaygupta007: 2020-04-08 10:31:07

1.learn how to compute mod of a big number using string.
2.use bfs

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