Problemi 22

Kërkesa

Që ta zërë gjumi shpejt, delja Bleatrix merr një numër N, pastaj dyfishin 2N, pastaj trefishin 3N, e kështu me radhë, deri sa ti ketë parë të paktën një herë të gjitha shifrat: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

P.sh. nqs merr N = 1692 ka parë shifrat (1, 6, 9, 2). Pastaj merr numrin 2N = 3384 dhe ka parë edhe shifrat (3, 8, 4). Pastaj merr numrin 3N = 5076 dhe tani i ka parë të gjitha shifrat dhe e zë gjumi.

Cili ka qenë numri i fundit që ka parë Bleatrix para se ta zinte gjumi? Shkruani INSOMNIA nqs asnjëherë nuk i shikon të gjitha shifrat.

Referenca: https://code.google.com/codejam/contest/6254486/dashboard#s=p0&a=0

Shembull

$ cat input.txt
5
0
1
2
11
1692

$ python3 prog.py < input.txt
Case #1: INSOMNIA
Case #2: 10
Case #3: 90
Case #4: 110
Case #5: 5076

Në rastin e parë, shumëfishat e zeros janë gjithmonë 0, kështu që asnjëherë nuk arrin ti shikojë të gjithë numrat.

Në rastin e dytë, i shikon me radhë shifrat 1, 2, 3, 4, 5, 6, 7, 8, 9, dhe kur arrin the 10 shikon edhe 0.

Në rastin e tretë, kur arrin te 90 shikon edhe 9-ën, që është shifra e fundit.

Në rastin e katërt shikon numrat 11, 22, …, 99, 110.

Rasti i pestë është diskutuar më sipër.

Zgjidhja

for t in range(int(input())):
    N = int(input())
    if N == 0:
        print('Case #{}: INSOMNIA'.format(t+1))
        continue
    n = 0
    digits = set([])
    while len(digits) < 10:
        n += N
        digits |= set(str(n))
    print('Case #{}: {}'.format(t+1, n))