Problemi 138

Kërkesa

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

Zgjidhja

for _ in range(int(input())):
    X = input()
    Y = input()
    Z = []
    for i in range(len(X)):
        if X[i] != Y[i]:
            Z.append('B')
        elif X[i] == 'B':
            Z.append('W')
        else:
            Z.append('B')
    print(''.join(Z))

Sqarime

Nqs topat korrespondues në një pozicion të caktuar në X dhe Y janë me ngjyra të ndryshme, atere sido që ta zgjedhim topin për rreshtin Z shuma e kërkuar do rritet vetëm me 1. Por meqenëse programi duhet të nxjerrë një zgjidhje që të jetë alfabetikisht sa më e vogël, atere ne zgjedhim një top B (black).

Në rastin kur topat në X dhe Y janë me të njëjtën ngjyrë, atere në Z zgjedhim një top me ngjyrë të kundërt, sepse kjo e shton vlerën e shumës me 2.