domino2

Domino2

p<>. Cu piesele pe care le avem la dispoziţie putem forma un şir, dacă respectăm următoarea regulă: două piese aflate în poziţii alăturate în şir trebuie să conţină prima în dreapta şi a doua în stânga un număr egal. Această regulă o vom numi *proprietate “stânga-dreapta”*. Excepţie de la această regulă fac prima piesă pentru numărul din stânga şi ultima piesă pentru numărul din dreapta. În acest şir, o piesă nu poate să apară de două ori. Exemple:
* şir corect pentu un set complet cu $n = 3$:

      !<problema/domino2?x2.jpg!
 

      {!problema/domino2?x2.jpg!}

* şir corect care nu foloseşte toate piesele ale unui set complet cu $n = 3$:

      !<problema/domino2?x3.jpg!
 

      {!problema/domino2?x3.jpg!}

* şir incorect, cu piese ce *nu* respectă proprietatea “stânga-dreapta” (piesa a treia şi piesa a patra):

      !<problema/domino2?x4.jpg!
 

      {!problema/domino2?x4.jpg!}

* şir incorect, în care o piesă se foloseşte de două ori (piesa a treia şi piesa a cincea):

      !<problema/domino2?x5.jpg!

      {!problema/domino2?x5.jpg!}
 
h2. Cerinţă
 
Determinaţi dacă pentru un $n$ dat se poate forma un şir cu toate piesele de domino dintr-un set complet.

h2. Date de intrare

Fişierul de intrare $domino2.in$ ...

Fişierul $domino2.in$ conţine pe prima linie o singură valoare naturală $n$ cu semnificaţia de mai sus.

h2. Date de ieşire

În fişierul de ieşire $domino2.out$ ...

Fişierul $domino2.out$ va conţine pe fiecare linie cele două numere aflate pe câte o piesă din şirul cerut separate prin spaţiu. Prima linie va conţine numerele primei piese, a doua linie va conţine numerele de pe a doua piesă, etc. Numerele unei piese vor fi astfel scrise încât să respecte proprietatea “stânga-dreapta”.
Dacă nu există soluţie, pe prima linie a fişierului se afişează valoarea $-1$.
 

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ n ≤ 1500$
* Pot exista mai multe soluţii, se acceptă orice soluţie corectă

h2. Exemplu
table(example). |_. domino2.in |_. domino2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

| 3
| 1 1
1 2
2 2
2 3
3 3
3 1
|

== include(page="template/taskfooter" task_id="domino2") ==

5709