Problemi 068

Kërkesa

Le ta quajmë tidy (të rregullt) një numër që i ka shifrat të renditura në rendin jo-zbritës. P.sh. numrat 8, 123, 555, 224488 janë tidy, kurse numrat 20, 321, 495, 999990 nuk janë. Gjeni numrin më të vogël tidy që është më i madh ose i barabartë me një numër të dhënë N.

Referenca:

Shembull

$ cat input.txt
4
132
1000
7
900000000000000000

$ python3 prog.py < input.txt
Case #1: 133
Case #2: 1111
Case #3: 7
Case #4: 999999999999999999

Zgjidhja 1

def tidy(n):
    d = n % 10
    while n > 0:
        if n % 10 > d:
            return False
        d = n % 10
        n //= 10
    return True

for t in range(int(input())):
    N = int(input())
    while not tidy(N):
        N += 1
    print('Case #{}: {}'.format(t+1, N))

Sqarime

Kemi një funksion që kontrollon nëse një numër i dhënë është tidy, pastaj vazhdojmë ta rrisim numrin deri sa të gjejmë një që është tidy.

Kjo zgjidhje është llogjikisht e thjeshtë, por për numra të mëdhenj (p.sh. për rastin e fundit) vonohet shumë. Duhet gjetur një zgjidhje më e shpejtë.

Zgjidhja 2

for t in range(int(input())):
    D = [int(d) for d in list(input())]
    i = 1
    while i < len(D) and D[i] >= D[i-1]:
        i += 1
    while i < len(D):
        D[i] = D[i-1]
        i += 1
    print('Case #', t+1, ': ', *D, sep='')

Sqarime

Kontrollojmë shifrat e numrit të dhënë deri sa të gjejmë një vend ku rregulli prishet. Që aty e deri në fund të numrit i bëjmë shifrat të barabarta me shifrën e fundit që ishte në rregull. Ky numër do jetë tidy dhe më i vogli i mundshëm nga të gjithë numrat më të mëdhenj (ose të barabartë) se numri i dhënë.

Kjo zgjidhje është shumë më e shpejtë se zgjidhja e parë. Edhe për numra shumë të mëdhenj (p.sh. rasti i fundit) jep përgjigje të menjëhershme.

Detyra

Le ta quajmë tidy (të rregullt) një numër që i ka shifrat të renditura në rendin jo-zbritës. P.sh. numrat 8, 123, 555, 224488 janë tidy, kurse numrat 20, 321, 495, 999990 nuk janë.

Nqs numërojmë numrat nga 1 në N, cili ka qenë numri i fundit tidy që kemi numëruar? Ose me fjalë të tjera, gjeni numrin më të madh tidy që është më i vogël (ose i barabartë) se një numër i dhënë N.

Referenca: https://code.google.com/codejam/contest/3264486/dashboard#s=p1&a=1

Shembull

$ cat input.txt
4
132
1000
7
111111111111111110

$ python3 prog.py < input.txt
Case #1: 129
Case #2: 999
Case #3: 7
Case #4: 99999999999999999