Fişierul intrare/ieşire:recon.in, recon.outSursăConcurs Shumen juniori 2010
AutorAutor NecunoscutAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.4 secLimită de memorie4608 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Recon (clasele 8-9)

Notă: limita de memorie a acestei probleme a fost micşorată faţă de original pentru a face problema mai interesantă.

Tinerii programatori Peter şi Stancho au fost angajaţi de două agenţii spaţiale. Agenţia lui Peter a proiectat o nouă staţie spaţială compusă din N module, numerotate de la 1 la N. Unele module sînt legate prin coridoare în aşa fel încît se poate ajunge de la de la oricare modul la oricare alt modul printr-o cale unică de coridoare (vezi figura). Lungimea fiecărui coridor este un întreg pozitiv. Există cel mult un coridor între oricare două module.

Şefii lui Peter ar dori să ţină secret proiectul. De aceea Peter a codat topologia staţiei dînd pentru fiecare două module distanţa dintre ele (adică suma lungimilor coridoarelor pe calea unică dintre module).

Dar Stancho are o problemă grea - el a promis şefilor săi că va decripta codarea lui Peter şi va realcătui topologia staţiei. Din păcate Stancho nu este suficient de experimentat. Ajutaţi-l.

Cerinţă

Scrieţi un program care să rezolve problema.

Date de intrare

Fişierul de intrare recon.in conţine pe prima linie un număr N de module. Urmează N - 1 linii. Pe prima linie se dau distanţele de la modului 1 la modulele 2, 3, ..., N, separate de spaţii. Pe a doua linie se dau distanţele de la modului 2 la modulele 3, 4, ..., N şi aşa mai departe. Ultima linie conţine doar distanţa de la modulul N - 1 la modulul N.

Date de ieşire

Programul trebuie să scrie N linii în fişierul de ieşire recon.out. Prima linie va conţine lista vecinilor modulului 1, adică modulele legate prin coridoare de el. Lista trebuie să înceapă cu numărul L de vecini, urmat de numerele lor de ordine, ordonate crescător. Toate numerele vor fi separate printr cîte un singur spaţiu. Pe a doua linie se fa scrie, formatată în acelaşi mod, lista vecinilor modulului 2 şi aşa mai departe. Fişierul se va termina cu lista vecinilor modulului N.

Restricţii

  • 3 ≤ N ≤ 1024
  • distanţele Dij sînt întregi pozitivi mai mici strict decit 15000

Exemplu

recon.inrecon.out
5
5 14 3 7
13 2 6
11 7
4
1 4
1 4
1 5
3 1 2 5
2 3 4
Trebuie sa te autentifici pentru a trimite solutii. Click aici