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

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.