Problemi 066

Kërkesa

Është një numër magjik me 16 letra ku letrat vendosen në një tabelë 4x4 dhe spektatorit i kërkohet të zgjedhë një letër dhe të thotë rreshtin në të cilin ndodhet. Pastaj “magjistari” i mbledh letrat, i pret, dhe i shpërndan përsëri në një tabelë 4x4. Spektatori thotë përsëri rreshtin në të cilin ndodhet letra që ka menduar, dhe magjistari gjen se cilën letër ka menduar.

Letrat i shënojmë me numra nga 1 deri në 16, dhe na jepet vendosja e letrave në fillim dhe rreshti që ka zgjedhur spektatori, si dhe vendosja e letrave herën e dytë dhe rreshti që ka zgjedhur spektatori. Bëni një program që gjen se cila ka qenë letra e menduar prej spektatorit. Nqs ju del se ka më shumë se një të tillë, i bie që magjistari ka bërë ndonjë gabim, kështu që programi duhet të nxjerrë “Bad magician!”. Nqs nuk del asnjë letër, i bie që spektatori duhet të jetë ngatërruar ose ka gënjyer, kështu që programi duhet të nxjerrë “Volunteer cheated!”,

Referenca: https://code.google.com/codejam/contest/2974486/dashboard#s=p0

Shembull

$ cat input.txt
3
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2 5 4
3 11 6 15
9 10 7 12
13 14 8 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

$ python3 prog.py < input.txt
Case #1: 7
Case #2: Bad magician!
Case #3: Volunteer cheated!

Në rastin e parë letra e menduar ndodhet në rreshtin e dytë, dhe pastaj në rreshtin e tretë, kështu që i bie që të jetë letra 7.

Zgjidhja

Sqarime

Kemi shumë topa pingpongu të bardhë dhe të zinj dhe kemi krijuar dy rreshta me gjatësi N përkrah njëri-tjetrit. Këta rreshta i shënojmë si vargjet X dhe Y, të përbërë prej shkronjave W and B, ku W shënon një top të bardhë (white) kurse B një top të zi (black).

Tani duam të krijojmë një rresht të tretë Z në mënyrë që ham(X, Z) + ham(Y, Z) të jetë sa më e madhe. Funksioni ham(A, B) është Hamming Distance midis vargjeve A dhe B me të njëjtën gjatësi. Kjo distancë midis dy vargjeve është numri i pozicioneve ku këto vargje kanë shkronja të ndryshme. P.sh. ham(‘WBB’, ‘BBW’) është 2, meqenëse shkronjat e para dhe të treta janë të ndryshme.

Meqenëse mund të ketë zgjidhje të ndryshme, programi duhet të nxjerrë atë zgjidhje që është alfabetikisht më e vogël. P.sh. shkronja B është më e vogël se shkronja W sepse ndodhet përpara saj në alfabet.

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

Shembull

$ cat input.txt
1
WBWB
WBBB

$ python3 prog.py < input.txt
BWBW