| Fişierul intrare/ieşire: | arbore12.in, arbore12.out | Sursă | ad-hoc |
| Autor | Ciprian Oprisa | Adăugată de |  Ciprian Oprisa •cypry |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Arbore din permutare
Jack şi-a vândut vaca, dar în loc de boabe de fasole fermecate a primit o permutare. Vânzătorul i-a promis că dacă plantează permutarea, din ea va creşte un arbore. În această lume magică, o permutare este o secvenţă de N numere distincte de la 1 la N iar un arbore este un graf neorientat, conex, şi fără cicluri. Mai mult, un arbore care creşte din permutarea P are proprietatea că pentru orice muchie (a, b), cu a < b, a apare în permutare înaintea lui b.
Jack este curios dacă din permutarea primită de la vânzător poate creşte într-adevăr un arbore. Dacă da, daţi un exemplu de arbore care poate creşte din această permutare.
Date de intrare
Pe prima linie a fişierului arbore12.in se află numărul de teste T. Fiecare test este format din două linii. Pe prima linie este numărul de elemente al permutării N, iar pe următoarea linie este o permutare a numerelor 1..N.
Date de ieşire
În fişierul de ieşire arbore12.out afişaţi pentru fiecare test o linie care conţine "da" sau "nu", indicând dacă pentru permutarea dată se poate construi un arbore cu proprietăţile cerute. Dacă da, pe următoarele N-1 linii se va scrie câte o muchie a arborelui, de forma "A B", unde A şi B sunt numere întregi de la 1 la N. Dacă există mai mulţi arbori care se pot construi pe baza permutării date, orice soluţie validă va fi acceptată.
Restricţii
- 1 ≤ T ≤ 30
- 2 ≤ N ≤ 10000
Exemplu
| arbore12.in | arbore12.out |
|---|---|
| 2 4 2 1 4 3 3 3 1 2 | da 2 4 2 3 1 4 nu |
Explicaţie
Pentru permutarea 2, 1, 4, 3, o soluţie posibilă este arborele format din muchiile (2, 4), (2, 3) şi (1, 4). Cum 2 apare în permutare înaintea lui 4 şi 3, iar 1 apare înaintea lui 4, permutarea este validă. Din permutarea 3, 1, 2 nu se poate construi un arbore deoarece nodul 3 nu se poate conecta nici cu nodul 1 nici cu nodul 2, apărând în permutare înaintea acestora.
