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

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

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