DRŽAVNO NATJECANJE 2015. – Drugi dan natjecanja / Srednja škola, II. podskupina (3. i 4. razred) - 2. zadatak

Mirko i Slavko cijeli dan gledaju filmove o divljem zapadu, a nakon toga igraju igru koja ima više veze s matematikom nego s divljim zapadom.

Neka je zadana kvadratna matrica cijelih brojeva koja se sastoji od N redaka i N stupaca.

Za neki element te matrice kažemo da je sedlo ako je strogo veći od svih drugih koji su u istom retku ili istom stupcu.

Ako matrica u svakom retku i svakom stupcu ima točno jedno sedlo onda kažemo da je ona kaubojska matrica. Težina kaubojske matrice je suma svih njenih sedala.

Mirko i Slavko se igraju tako da Mirko krene od prazne matrice te upiše neke cijele brojeve između 0 i 100 (uključivo) u neka polja.

akon toga, Slavko mora popuniti sva prazna polja (također cijelim brojevima između 0 i 100 uključivo) tako da dobije kaubojsku matricu.

Dodatno, od svih mogućih kaubojskih matrica koje može dobiti, Slavko popunjavanjem želi dobiti onu koja ima najveću moguću težinu.

Mirko i Slavko žele odigrati nekoliko partija.

Napišite program koji će za svaku partiju odrediti da li Slavko može konstruirati kaubojsku matricu, te, ako može, odrediti jednu takvu matricu najveće moguće težine.

Vaš program će dobiti parcijalne bodove ako pronađe bilo kakvu kaubojsku matricu kada god ona postoji – vidi poglavlje 'Bodovanje' .

Ulazni​ podaci

U prvom redu nalazi se prirodni broj P (1 ≤ P ≤ 5)- broj partija koje će Mirko i Slavko odigrati.

Slijedi P blokova od kojih svaki opisuje jednu partiju.

U prvom redu K-tog bloka nalazi se prirodni broj Nk (1 ≤ Nk ≤ 18) ) - dimenzija matrice.

U svakom od sljedećih Nk redova nalazi se Nk cijelih brojeva odvojenih jednim razmakom - jedan redak matrice.

Za svaki cijeli broj X u matrici vrijedi -1 ≤ X ≤ 100. Ukoliko je X jednak -1 to znači da Mirko u prvom koraku nije popunio to polje.

Izlazni podaci

Potrebno je ispisati P blokova, svaki blok treba sadržavati rješenje za jednu partiju onim redom kojim partije dolaze u ulazu.

Ukoliko Slavko ne može konstruirati niti jednu kaubojsku matricu, K-ti blok treba sadržavati samo jedan red koji sadrži samo broj -1 U suprotnom, K-ti blok treba sadržavati nađenu kaubojsku matricu.

Matricu treba ispisati na isti način kao u ulazu.

Primjeri test​ podataka

Ulaz

1
2
1 2
-1 -1

Izlaz

1 2
100 1

Objašnjenje

Pojašnjenje prvog test primjera: Mirko i Slavko igraju samo jednu partiju.

Sedla u ispisanoj matrici su u poljima (1,2) i (2,1) te imaju sumu

1. Kaubojska matrica s najvećom mogućom težinom još je i:

1 2 100 0

Ulaz

3
3
-1 -1 -1
1 2 3
4 5 6
3
86 41 -1
-1 90 -1
35 24 88
2
-1 -1
-1 -1

Izlaz

-1
86 41 3
5 90 7
35 24 88
100 0
0 100