Fişierul intrare/ieşire:romania.in, romania.outSursăAlgoritmiada 2016 - Runda 2, Seniori
AutorAndrei Popa, Eugenie Daniel PosdarascuAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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

romania.inromania.out
5 2
1 4
1 3
4 1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?