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
for _ in range(int(input())):
# lexo rreshtin e pare dhe tabelen e pare
r1 = int(input())
M1 = []
for _ in range(4):
M1.append([int(i) for i in input().split()])
# lexo rreshtin e dyte dhe tabelen e dyte
r2 = int(input())
M2 = []
for _ in range(4):
M2.append([int(i) for i in input().split()])
# merr rreshtat e perzgjedhur dhe gjej prerjen e tyre
R1 = M1[r1 - 1]
R2 = M2[r2 - 1]
I = []
for i in R1:
if i in R2:
I.append(i)
# jep pergjigjen ne varesi te prerjes
if len(I) > 2:
print('Bad magician!')
elif len(I) == 0:
print('Volunteer cheated!')
else:
print(I[0])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