Problemi 051

Kërkesa

Dejvi shkoi në pazar dhe pa fshatarët që po shisnin kosha me rrush. Mirëpo numrat e kileve që kishin koshat nuk i pëlqyen se iu dukën pa lidhje. Dejvi do të donte që pjesëtuesi më i madh i përbashkët i të gjithë numrave të ishte i plotpjesëtueshëm me K. Bëni një program që gjen numrin më të vogël të kileve që duhen shtuar ose hequr nëpër kosha, që të plotësohet ky kusht dhe asnjë kosh të mos ngelet bosh.

Referenca: https://www.codechef.com/problems/DEVUGRAP

Shembull

$ cat input.txt
2
2 2
3 5
3 7
10 16 18

$ python3 prog.py < input.txt
2
8

Në rastin e parë kemi 2 kosha dhe numrat e kileve duhet të plotpjesëtohen me 2. Mjafton të shtojmë ose të heqim 1 kile nga secili prej koshave, që të plotësohet ky kusht.

Në rastin e dytë kemi 3 kosha dhe numrat e kileve duhet të plotpjesëtohen me 7. Mund të heqim 3 kile në koshin e parë, të heqim 2 kile koshin e dytë, dhe të shtojmë 3 kile në koshin e tretë. Gjithsej, 3 + 2 + 3 = 8.

Zgjidhja

Sqarime

Në mënyrë që pjesëtuesi më i madh i përbashkët i të gjithë numrave të plotpjesëtohet me K, mjafton që secili prej numrave të plotpjesëtohet me K. Për një numër të caktuar shikojmë mbetjen M të pjesëtimit me K. Nëse kjo është më e vogël se (K-M), atere numrit i heqim M, përndryshe i shtojmë (K-M). Në këtë mënyrë plotësojmë kushtin që numri i kileve të hequra apo të shtuara të jetë sa më i vogël, dhe të gjithë numrat të plotpjesëtohen me K. Vetëm se në rast se vetë numri është më i vogël se K, atere duhet që gjithmonë ti shtojmë diçka që të bëhet K, në mënyrë që të plotësojmë edhe kushtin që asnjë kosh të mos mbetet bosh (ose asnjë nga numrat të mos bëhet 0).

Detyra

Çdo ditë Majko shkon në punë me autobus, ku pret një biletë. Çdo biletë ka një kod me shkronja latine. Majko beson se dita do ti shkojë mbarë nëse kodi i biletës ka vetëm 2 shkronja alternuese, si p.sh. xyxyxy… ku x!=y.

Bëni një program që merr kodin e biletës dhe nxjerr “YES” nëse është alternues, dhe “NO” në të kundërt.

Referenca: https://www.codechef.com/problems/TICKETS5

Shembull

$ cat input.txt
2
ABABAB
ABC

$ python3 prog.py < input.txt
YES
NO