Fișierul intrare/ieșire recon.in, recon.out Sursă Concurs Shumen juniori 2010
Autor autor necunoscut Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.4 sec Limită de memorie 4608 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip full
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in recon.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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii