Problemi 028

Kërkesa

Cufi ka gjetur dy fleta letre shumë të vjetra. Secila prej tyre fillimisht ka pasur shkronja latine, por meqenëse fletët janë shumë të vjetra, disa prej shkronjave janë bërë të palexueshme. Megjithatë numri i shkronjave në secilën fletë është i njëjtë.

Cufi do të donte të vlerësonte ndryshimin midis këtyre vargjeve. Le ta quajmë vargun e parë S1 dhe vargun e dytë S2. Shkronjat e palexueshme janë shënuar me një pikëpyetje (?). Ndryshimi midis dy vargjeve përkufizohet si numri i pozicioneve i të tilla që shkronja S1[i] është e ndryshme nga shkronja S2[i].

Ndihmojeni Cufin duke bërë një program që gjen ndryshimin më të vogël dhe më të madh midis dy vargjeve, nëse i zëvendësojmë të gjitha shkronjat e palexueshme me shkronja të tjera.

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

Shembull

$ cat input.txt
3
a?c
??b
???a
???a
?abac
aba?w

$ python3 prog.py < input.txt
1 3
0 3
3 5

1. Në rastin e parë mund ti zëvendësojmë pikëpyetjet në mënyrë të tillë që S1 = 'abc' dhe S2 = 'abb'. Atere S1 dhe S2 do ndryshojnë vetëm në një pozicion. Por mund ti bëjmë edhe S1 = 'abc' dhe S2 = 'bab', dhe në këtë rast ndryshimi midis tyre është 3.

2. Po ti bëjmë zëvendësimet të tilla që S1 = 'dcba' dhe S2 = 'dcba', atere ndryshimi është 0. Por mund ti bëjmë zëvendësimet edhe të tilla që S1 = 'aaaa' dhe S2 = 'dcba', dhe ndryshimi midis tyre do ishte 3.

3. Po ti bëjmë zëvendësimet të tilla që S1 = 'aabac' dhe S2 = 'abaaw', ndryshimi është 3. Po ti bëjmë zëvendësimet të tilla që S1 = 'xabac' dhe S2 = 'abayw', ndryshimi është 5.

Zgjidhja

for _ in range(int(input())):
    s1 = input()
    s2 = input()
    dmin = 0    # diferenca minimale
    dmax = 0    # diferenca maksimale
    for i in range(len(s1)):
        if s1[i] == '?' or s2[i] == '?':
            dmax += 1
        elif s1[i] != s2[i]:
            dmin += 1
            dmax += 1
    print(dmin, dmax)

Sqarime

Kur njëra nga shkronjat (ose të dyja) është ?, ato mund të kenë qenë të barabarta ose mund të kenë qenë të ndryshme. Kështu që diferenca minimale nuk rritet, kurse diferenca maksimale rritet me 1.

Përndryshe (të dyja janë të ndryshme nga ?), nëse shkronjat janë të ndryshme, rritet edhe diferenca minimale edhe ajo maksimale.

Detyra

Në një varg shkronjash, shenja ? mund të zëvendësohet me çdo lloj shkronje tjetër. Gjeni nëse dy vargje të dhëna, me gjatësi të njëjtë, janë të përputhshëm me njëri-tjetrin (dmth nëse mund të bëhen të barabartë duke zëvendësuar shenjat ? me shkronja).

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

Shembull

$ cat input.txt
2
s?or?
sco??
stor?
sco??

$ python3 prog.py < input.txt
Yes
No

Në rastin e parë, fjala score përputhet me të dyja vargjet e dhëna. Kurse në rastin e dytë nuk është e mundur të përputhen.