La un foc de tabara, intr-o
seara, participa N
copii, numerotati de la 1
la N. Copii
spun pe rand bancuri, insa fiind foarte obositi dupa excursiile de peste zi,
adorm incet, incet toti. A doua zi vor sa stie care a fost ordinea in care au
adormit. Fiecare copil isi aminteste exact cate dintre bancurile fiecarui coleg
de al sau le-a auzit inainte de a adormi. Numarul de bancuri ascultate de copii
se memoreaza intr-o matrice patratica de numere naturale A,
cu N linii si
N coloane, unde
A[i][j] reprezinta
numarul de bancuri spuse de copilul j
pe care le-a ascultat copilull i
inainte de a adormi.
Cerinta
Scrieti un program care
determina ordinea in care copiii au adormit.
Date de intrare
Pe prima linie a fisierului
de intrare jokes.in se
gaseste un numar natural N,
reprezentand numarul de copii care au participat la focul de tabara. Pe urmatoarele
N linii, se
gasesc elementele matricei A,
cate o linie a matricei pe cate o linie a fisierului de intrare, valorile de
pe aceeasi linie fiind separate printr-un spatiu.
Date de iesire
Fisierul de iesire jokes.out
contine pe prima linie N
numere naturale reprezentand numerele de ordine ale copiilor, in ordinea in
care acestia au adormit.
Restrictii si precizari
2
<= N <= 300
0 <= A[i][j]
<= 1500
A[i][i]=0
pentru orice i=1,2,...,N
Se garanteaza existenta
solutiei pentru toate datele de test alese.
Daca exista mai
multe solutii se va alege prima solutie in ordine lexicografica.
Un vector x=(x[1],x[2],...,x[N])
spunem ca este mai mic in ordine lexicografica decat vectorul
y=(y[1],y[2],...,y[N])
daca exista un indice i
astfel incat x[1]=y[1],
x[2]=y[2],...,x[i-1]=y[i-1]
si x[i]<y[i].
Exemplu
jokes.in
jokes.out
Explicatii
3
0 1 1
2 0 0
3 1 0
2 1 3
O
posibila secventa a evenimentelor este:
- Copilul 1
spune un banc
- Copilul 2
spune un banc
- Copilul 1
spune un banc
- Copilul 2
adoarme
- Copilul 3
spune un banc
- Copilul 1
spune un banc
- Copilul 1
adoarme
- Copilul 3
adoarme
prof. Carmen
Popescu
Colegiul National "Gheorghe Lazar" Sibiu
Contact: carmen_cngl@yahoo.com