stive

Stive

== include(page="template/taskheader" task_id="stive") ==

Poveste si cerinta...

Pe o masa se afla $N$ stive (numerotate de la $1$ la $N$). Stiva $i$ contine $i$ jetoane ( $1 ≤ i ≤ n$ ). La o mutare se poate alege o multime de stive si se pot extrage din fiecare stiva care face parte din multimea aleasa acelasi numar de jetoane.
 
h2. Cerinta
 
Sa se determine o secventa cu numar minim de mutari care sa goleasca toate cele $N$ stive.

h2. Date de intrare

Fisierul de intrare $stive.in$ ...

Fisierul de intrare $stive.in$ contine pe prima linie numarul natural $N$.

h2. Date de iesire

In fisierul de iesire $stive.out$ ...

Fisierul de iesire $stive.out$ va contine pe prima linie un numar natural $MIN$ reprezentand minim de mutari efectuate. Pe urmatoarele $MIN$ linii sunt descrise mutarile, cate o mutare pe o linie. Linia ce descrie o mutare are forma:
 
* $nr s1 s2 ... snr x$
unde $nr$ reprezinta numarul de stive din multimea selectata la mutarea respectiva; $s1, s2, ..., snr$ sunt stivele selectate, iar $x$ reprezinta numarul de jetoane extrase din fiecare stiva $s1, s2, ..., snr$. Valorile de pe aceeasi linie sunt separate prin spatii.

h2. Restrictii

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

* $1 ≤ n ≤ 30.000$

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

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

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

|
h3. Explicatie

...

* Configuratia initiala a stivelor este $1 2 3$
* La prima mutare sunt selectate $2$ stive ( $2$ si $3$) si se extrag cate $2$ jetoane din fiecare. Se obtine configuratia: $1 0 1$
* La ultima mutare se aleg stivele $1$ si $3$, se extrage cate un singur jeton din fiecare si astfel au fost golite toate stivele.
 

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

3342