Problemi 075

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ë.

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

Zgjidhja 1

Sqarime

Kemi një funksion që kontrollon nëse një numër i dhënë është tidy, pastaj vazhdojmë ta zvogëlojmë 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

Kjo zgjidhje fillon nga një numër që ne e dimë që është tidy dhe më i vogël se numri i dhënë, dhe gjen vazhdimisht numrin pasardhës tidy, deri sa ky numër të bëhet më i madh se N. Atere numri i fundit tidy që kemi parë është zgjidhja e kërkuar.

Kjo zgjidhje në përgjithësi është më e shpejtë se zgjidhja e parë, sepse nuk i kontrollon numrat me radhë por vetëm ata që janë tidy, dhe numrat tidy nuk janë shumë të shpeshtë. Gjithsesi edhe kjo zgjidhje është e ngadaltë për numra shumë të mëdhenj (rasti i fundit).

Detyra

Trajneri i futbollit të një shkolle duhet të zgjedhë P nxënës për të përfaqësuar shkollën në kampionat. Shkolla ka N nxënës dhe aftësitë e secilit në futboll shënohen me një numër natyror \(S_i\).

Trajneri mendon se skuadra duhet të jetë e niveluar, dmth të ketë P nxënës me të njëjtin nivel aftësish, sepse kështu do të luajnë të gjithë si skuadër. Në fillim mund të mos jetë e mundur që të gjenden P nxënës me aftësi të barabarta, kështu që trajnerit do ti duhet ti stërvitë individualisht disa nxënës, për të rritur aftësitë e tyre. Me një orë stërvitje aftësia e një nxënësi mund të ngrihet me 1 pikë.

Sa është minimumi i orëve të stërvitjes që duhen për të krijuar një skuadër të niveluar.

Referenca: https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e01/00000000000698d6

Shembull

$ cat input.txt
3
4 3
3 1 9 100
6 2
5 5 1 2 3 4
5 5
7 7 1 7 7

$ python3 prog.py < input.txt
Case #1: 14
Case #2: 0
Case #3: 6

Jepen N dhe P, dhe më pas aftësitë e çdo nxënësi.

Në rastin e parë mund të trajnohet për 6 orë nxënësi i parë dhe për 8 orë nxënësi i dytë, dhe atere tre nxënësit e parë do kenë të njëjtin nivel aftësish.

Në rastin e dytë, dy nxënësit e parë kanë të njëjtin nivel aftësish, kështu që nuk është nevoja për trajnime shtesë.

Në rastin e tretë, nxënësi i tretë duhet trajnuar për 6 orë, dhe kështu të 5 nxënësit do kenë të njëjtin nivel.