Profesorul Utonium a facut
o descoperire uimitoare, a reusit sa creeze cele mai dragalase animale de casa
pe care le-a numit crocobauzeri. Profesorul a creat prin experimente N
crocobauzeri si intentioneaza sa-i lase sa se reproduca un an dupa care sa-i
ofere prietenilor lui.
Dupa mult studiu asupra celor N
crocobauzeri, profesorul a descoperit ca oricare pereche poate sa se reproduca
si, mai mult, stie si cati pui va avea fiecare pereche intr-un an. Evident daca
profesorul ar pastra crocobauzerii in aceeasi incapere toate perechile s-ar
reproduce si ar avea numarul maxim de pui posibil la sfarsitul anului. Din pacate
acest lucru nu este posibil pentru ca incaperile sunt prea mici si daca ar pune
toti crocobauzerii intr-o incapere acestia ar muri. Totusi se pare ca sunt suficiente
doua incaperi pentru a-i pastra. Dupa ce profesorul va imparti crocobauzerii,
acestia vor sta asa pana la sfarsitul anului si oricare doi crocobauzeri din
aceeasi camera se vor reproduce.
Cerinta
Daca vreti ca un crocobauzer
sa ajunga si la voi trebuie sa-l ajutati pe profesor sa imparta crocobauzerii
astfel incat la sfarsitul anului sa aiba un numar maxim de pui de crocobauzer.
Date de intrare
Pe prima linie a fisierului
de intrare croco.in este scris
numarul natural N reprezentand
numarul de crocobauzeri.
Urmatoarele N linii contin cate
N numere naturale separate prin
spatii; al j-lea numar de pe
cea de-a i-a linie reprezinta
numarul de pui pe care crocobauzerii i
si j i-ar face daca ar fi in
aceeasi camera, evident daca i
este egal cu j valoarea este
0, iar daca j
este mai mic decat i valoarea
este egala cu a i-a valoare de
pe linia j.
Date de iesire
Fisierul de iesire croco.out
va contine pe prima linie numarul maxim de crocobauzeri pe care poate sa-i aiba
profesorul la sfarsitul anului, precum si numarul de crocobauzeri din prima
camera, separate printr-un spatiu. Pe cea de a doua linie vor fi scrise numerele
de ordine ale crocobauzerilor din prima camera, separate prin cate un spatiu.
Restrictii
2 < N < 111
0 < numarul
de crocobauzeri dintr-o camera < N
0 <= numarul
de pui ai unei perechi de crocobauzeri < 222
In
prima camera se afla crocobauzerii 1
si 2 care vor face impreuna
4 pui.
In cea de a doua camera se vor afla crocobauzerii 3,
4 si 5.
Crocobauzerii 3 si 4
vor face impreuna 4 pui,
crocobauzerii 3 si 5
vor face 0 pui, iar crocobauzerii
4 si 5
vor face 4 pui.
In total vor fi 12 pui.