.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » jokes

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
jokes


Timp maxim de executie/test:
0.5 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2005: cuc, prime, radio, text2, honest, police, comori, patrate3, fisc, ref, pcod, zmeu, loc, nr01, scor2, judete, strict, convert, bile3, cod2, depou, auto2, tree, cat, nr3, chimie2, compress, jobs, leaves, zid, politics, onu2, ploaia, grazing, pstring, cartonase2, exp, cartoane, sir3, program, scoici, playlist, sqr, cai1, farfurii, joc1, trafic, carte, set, barbie, labirint, firma1, vile, game, donald, ambigram, dans, albinuta, rlcs, stea, submatrix, cub1, ham, sponsori, young, pizza1, albine, lot, atac1, monede1, count, exam, herbert, sudoku, bio, metro
De acelaşi autor: light, sort, iepuras, pahare, turist, arthur, pento, cod2, game, ambigram, trecere, paianjen, zumzi, cifru3, pamant, pixy, triburi, culori1, cifre5, arc
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, 2ndesc, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Despre sortare: harta, index, sort, concurs, baby, patrate2, repeat, turist, bacan, toys, scor2, chimie2, politics, submat, scoici, ham, trecere, multiplu, paralel, tvshow, sirag1, tabara, munte, sport, puncte1, sume1, schi, granita, tren3, sant1, volei1, poze, maroco, dreptc, dist1, tir1, control, mosia, popas, reactivi, siruri1, coach, anag, matrice4, sume2, urgenta, basm, vot, balcon, joc14, cerc, k1, segm, calorii, ordonare, greutati, arctir, macheta, poligon4, centrala, robot4, lcdr, maxviz, sdmin, qtri, arme, flori1, parc1, mijloc, bile6, proiecte, patru, drept2, subsecvente, cursa1, eoliene, vintage, dreapta, riglef, rebus1, rascoala, zimeria, praslea, aperm, unudoi, gropi1, piscina, restaurare, cabana, culori3
surse trimise | ajutor