Problemi 152

Kërkesa

Një tabelë (matricë) me përmasa NxN e ka çdo rresht të renditur nga e majta në të djathtë në rendin rritës, dhe çdo shtyllë të renditur nga lart poshtë në rendin rritës.

Çdo rresht dhe çdo shtyllë e matricës është shënuar në disa shirita letre (janë 2xN shirita të tillë, ku çdo shirit ka N numra të renditur). Vetëm se një nga këta shirita na ka humbur.

A mund të gjeni se cilët kanë qenë numrat në shiritin e humbur, duke ditur numrat që janë në shiritat e tjerë?

Referenca: https://code.google.com/codejam/contest/4304486/dashboard#s=p1&a=1

Shembull

$ cat input.txt
1
3
1 2 3
2 3 5
3 5 6
2 3 4
1 2 3

$ python3 prog.py < input.txt
Case #1: 3 4 6

Kemi vetëm 1 rast testimi, ku N = 3. Më pas vijnë 2*3-1 rreshta me numra të renditur.

Zgjidhja

for t in range(int(input())):
    n = int(input())
    L = []
    for i in range(2*n - 1):
        L.extend([int(i) for i in input().split()])
    F = {}
    for i in L:
        F[i] = F.get(i, 0) + 1
    A = []
    for i in F.keys():
        if F[i] % 2 == 1:
            A.append(i)
    A.sort()
    print('Case #{}:'.format(t+1), *A)

Sqarime

Çdo numër që ndodhej te tabela është shënuar dy herë në shiritat e letrës, një herë sipas rreshtit dhe një herë sipas shtyllës. Kështu që çdo numër normalisht do shfaqej një numër çift herësh në shiritat e letrës. Më përjashtim të numrave që ndodhen në shiritin e humbur, të cilët shfaqen një numër tek herësh. Pasi të gjejmë ata numra që shfaqen një numër tek herësh, mjafton që ti rendisim, dhe këta do jenë numrat e shiritit të humbur.