| Fişierul intrare/ieşire: | salturi.in, salturi.out | Sursă | Grigore Moisil 2018, 9 |
| Autor | Alex Cociorva, Mircea Popoveniuc, Razvan Salajan | Adăugată de |  Grigore Moisil •grigore.moisil |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Salturi
Pe vremuri, oraşul Târgu Mureş avea N turnuri de diverse înălţimi numerotate de la 1 la N. Cronicile existente amintesc de faptul că cetatea a găzduit cel mai mare concurs între N pitici în arta săritului din turn în turn, iar regulile competiţiei au fost următoarele:
- fiecare pitic i va porni de pe turnul i;
- un pitic aflat pe un turn k poate sări doar pe turnuri cu indici strict mai mici decât k;
- piticii pot sări doar pe turnuri strict mai înalte decât turnul pe care se află;
- dacă există mai multe turnuri pe care poate să sară, un pitic va sări pe turnul cu indicele cel mai mare;
- când un pitic nu mai găseşte vreun turn pe care să poată sări, el se va opri;
- scorul obţinut de fiecare pitic este egal cu numărul de turnuri pe care el le-a parcurs.
După sute de ani de la încheierea competiţiei, înălţimile turnurilor au fost uitate. Totuşi, cronicarii au consemnat scorurile pentru fiecare pitic.
Dându-se scorurile obţinute de fiecare pitic i din cei N pitici, să se afle înălţimile celor N turnuri de pe vremuri. Se considera corectă orice soluţie pentru care, respectându-se regulile competiţiei, piticii obţin scorurile date. Dacă scorurile nu sunt valide pentru nici o configuraţie de înălţimi de turnuri, atunci se va afişa -1.
Se doreşte să se afle răspunsurile pentru T astfel de probleme.
Date de intrare
Fişierul de intrare salturi.in conţine pe prima linie numărul natural T reprezentând numărul de teste din fişierul de intrare. Urmează apoi T teste. Fiecare test este descris pe câte două linii din fişier dupa cum urmează: pe prima linie se află numărul natural N reprezentând numărul de pitici ce au participat la competiţie; pe următoarea linie se află N numere naturale separate prin spaţiu cu semnificaţia că al i-lea număr reprezintă scorul obţinut de piticul i.
Date de ieşire
Fişierul de ieşire salturi.out trebuie să conţină T linii: pe linia k se află răspunsul pentru testul k. Dacă există soluţie pentru testul k, atunci linia k trebuie să conţină N numere naturale separate prin spaţiu cu semnificaţia că al i-lea număr reprezintă înălţimea turnului i. Dacă nu există soluţie pentru testul al k-lea, atunci linia k trebuie să conţină valoarea -1.
Restricţii
- 1 <= T <= 5.
- 1 <= N ≤ 250 000. Suma N-urilor dintr-un fişier este maxim 500 000.
- Scorurile obţinute de pitici sunt numere naturale între 1 şi N.
- Înălţimile turnurilor de pe vremuri sunt numere naturale între 1 şi 109.
- Pentru teste în valoare de 30 de puncte, 1 <= N <= 1 000.
- Problema va fi evaluată pe teste în valoare de 90 de puncte.
- Exemplul va reprezenta teste în valoare de 10 puncte "din oficiu".
Exemplu
| salturi.in | salturi.out |
|---|---|
| 2 5 1 1 2 1 2 4 1 3 2 1 | 3 4 2 6 3 -1 |
Explicaţie
Se dau T=2 teste în fişier.
Pentru primul test, N=5. Dacă înălţimile turnurilor sunt 3 4 2 6 3, piticii vor sări în felul următor:
Piticul 1 (iniţial pe turnul 1 de înălţime 3) nu are unde să sară. Scorul lui va fi 1.
Piticul 2 (iniţial pe turnul 2 de înălţime 4) nu are unde să sară. Scorul lui va fi 1.
Piticul 3 (iniţial pe turnul 3 de înălţime 2) va sări pe turnul 2 (de înălţime 4), iar apoi nu mai are unde să sară. Scorul lui va fi 2.
Piticul 4 (iniţial pe turnul 4 de înălţime 6) nu are unde să sară. Scorul lui va fi 1.
Piticul 5 (iniţial pe turnul 5 de înălţime 3) va sări pe turnul 4 (de înălţime 6), iar apoi nu mai are unde să sară. Scorul lui va fi 2.
Se obţin scorurile 1 1 2 1 2, deci soluţia este una validă.
Se poate observa că înălţimile turnurilor nu sunt unice, aşadar pot fi afişate şi alte soluţii.
Pentru al doilea test, N=4. Nu se poate obţine nici o configuraţie de înălţimi de turnuri pentru care să se poată obţine scorurile date, aşadar se afişează -1.
