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 ale acestui poligon, cu proprietatea că oricare două dintre ele nu se intersectează decât, eventual, în capete. Nu ai păstrat desenul întreg, dar ţi-ai notat capetele acestor diagonale pe o foaie. Revenind la ea, constaţi că din motive care nu pot ţine decât de faptul că locuiai cam departe de şcoală ai scris aceste capete într-o ordine aleatoare. Poţi recupera cele K diagonale?
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 2 * K numere, reprezentând lista de vârfuri notată pe foaie.
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 dintre vârfurile x şi y în soluţie.
Restricţii
- 3 ≤ N ≤ 100.000
- Pentru teste in valoare de 40 de puncte N ≤ 1.500
- 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
| romania.in | romania.out |
|---|---|
| 5 2 1 1 4 3 | 1 4 1 3 |
