Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | romania.in, romania.out | Sursă | Algoritmiada 2016 - Runda 2, Seniori |
| Autor | Andrei Popa, Eugenie Daniel Posdarascu | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Romania
Fie P un poligon convex regulat cu N vârfuri numerotate în ordine trigonometrică. Ai trasat la un moment dat K diagonale orientate ale acestui poligon, cu proprietatea că oricare două dintre ele nu se intersectează decât, eventual, în capete. În cele ce urmează îl vom numi pe x "sursă" a diagonalei x -> y. Nu ai păstrat desenul întreg, dar ţi-ai notat sursa fiecărei diagonale pe o foaie. Acum te întrebi dacă poţi recupera diagonalele având doar aceste informaţii.
Date de intrare
Fişierul de intrare romania.in va conţine pe prima sa linie numerele N şi K având semnificaţia din enunţ. A doua linie conţine K numere, reprezentând lista de vârfuri care sunt surse ale diagonalelor.
Date de ieşire
În fişierul de ieşire romania.out se vor afla K linii, fiecare conţinând o pereche x y seminficând faptul că ai ales diagonala orientată dinspre vârful x spre vârful y. Dacă nu există soluţie, fişierul va conţine doar valoarea -1.
Restricţii
- 3 ≤ N ≤ 100.000
- Pentru teste in valoare de 40 de puncte N ≤ 1.500
- 1 ≤ K ≤ N - 3
- Vârfurile din fişierul de intrare sunt numere naturale din intervalul [1, N].
- Reamintim că se numeşte diagonală a poligonului orice segment care uneşte două vârfuri neconsecutive ale acestuia.
- Se acceptă orice soluţie corectă.
- Dacă vă întrebaţi de ce această problemă se numeşte România: nu mai ştim nici noi.
Exemplu
table(example). |_. romania.in |_. romania.out |
| 5 2
1 4
|
1 3
4 1
|
