Jucării

jucarii

Un copil are $M$ jucării pe care, fiind copil de informatician, le-a numerotat de la 1 la $M$. El îşi ţine jucăriile în dulap, în nişte cutii, câte două jucării în fiecare cutie, cu excepţia ultimei cutii, în care stă o singură jucărie dacă $M$ este impar.

Copilul şi-a planificat ordinea în care vrea să se joace diseară cu jucăriile: $J{~1~}, J{~2~}, ..., J{~N~}$ (un vector de $N$ numere naturale între 1 şi $M$, nu neapărat distincte). Totuşi, camera este mică şi copilul poate scoate din dulap o singură cutie odată. Ori de câte ori jucăria cu care urmează să se joace este în dulap (inclusiv prima dată), el trebuie să

Copilul şi-a planificat ordinea în care vrea să se joace diseară cu jucăriile: J{~1~}, J{~2~}, . . . , J{~N~} (un vector de $N$ numere naturale între 1 şi $M$, nu neapărat distincte). Totuşi, camera este mică şi copilul poate scoate din dulap o singură cutie odată. Ori de câte ori jucăria cu care urmează să se joace este în dulap (inclusiv prima dată), el trebuie să

deschidă dulapul, să pună la loc în dulap cutia de afară (dacă există vreo cutie afară), şi abia apoi să scoată cutia cu jucăria dorită. În aşteptarea serii, copilul se hotărăşte să-şi reorganizeze jucăriile în cutii.
h2. Cerinţă

h2. Date de intrare

Fişierul de intrare $jucarii.in$ conţine pe prima linie numerele $M$ şi $N$, iar pe a doua linie valorile $J{~1~}, J{~2~}, ..., J{~N~}$, despărţite prin spaţii.

Fişierul de intrare $jucarii.in$ conţine pe prima linie numerele $M$ şi $N$, iar pe a doua linie valorile J{~1~}, J{~2~}, . . . , J{~N~}, despărţite prin spaţii.

h2. Date de ieşire

În fişierul de ieşire jucarii.out tipăriţi pe prima linie numărul minim de deschideri ale dulapului. Pe a doua linie afişaţi o aşezare optimă în cutii sub forma a $M$ numere, $A{~1~}, A{~2~}, ..., A{~M~}$, despărţite prin spaţii, cu semnificaţia că:

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

* Jucăriile cu numerele $A{~1~}$ şi $A{~2~}$ stau în prima cutie.
* Jucăriile cu numerele $A{~3~}$ şi $A{~4~}$ stau în a doua cutie.
* ...
* Dacă $M$ este par, atunci jucăriile $A{~$M-1$~}$ şi $A{~$M$~}$ stau în ultima cutie.
* Dacă $M$ este impar, atunci jucăria $A{~$M$~}$ stă singură în ultima cutie.
 
Dacă există mai multe soluţii, afişaţi-o pe oricare.
 
h2. Restricţii şi precizări
 
* $3 ≤ M ≤ 20$
* $1 ≤ N ≤ 100 000$
* $1 ≤ J{~i~} ≤ M$ pentru orice $1 ≤ i ≤ N$
 
|_. # |_. Punctaj |_. Restricţii |
| $1$ | $5$ | $M ≤ 4$, $1 ≤ N ≤ 100$|
| $2$ | $7$ | $5 &le; M &le; 7$, $100 < N &le; 3 000$ |
| $3$ | $11$ | $8 &le; M &le; 10$ |
| $4$ | $13$ | $11 &le; M &le; 13$ |
| $5$ | $15$ | $14 &le; M &le; 16$ |
| $6$ | $49$ | Fără restricţii suplimentare |

h2. Restricţii
 
* $... ≤ ... ≤ ...$

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

| 8 14
1 2 5 3 5 3 7 3 7 3 7 8 7 8
| 7
7 8 5 3 2 1 4 6

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Copilul grupează jucăriile $7$ cu $8$, $5$ cu $3$, $2$ cu $1$, $4$ cu $6$. Apoi deschide dulapul de $7$ ori, astfel:
 
* Scoate cutia $(2, 1)$, se joacă cu $1, 2$.
* Scoate cutia $(5, 3)$, se joacă cu $5, 3, 5, 3$.
* Scoate cutia $(7, 8)$, se joacă cu $7$.
* Scoate cutia $(5, 3)$, se joacă cu $3$.
* Scoate cutia $(7, 8)$, se joacă cu $7$.
* Scoate cutia $(5, 3)$, se joacă cu $3$.
* Scoate cutia $(7, 8)$, se joacă cu $7, 8, 7, 8$.

...

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