== include(page="template/taskheader" task_id="tabara") ==
Poveste si cerinta...
Intr-o tabara la munte s-au intalnit copii veniti din $n$ regiuni diferite ale tarii. Tabara are in dotare suficiente cabane identice cu cate $n$ paturi. Directorul taberei a stabilit, pentru o cat mai buna socializare, urmatoarele reguli:
* in fiecare cabana trebuie sa fie cazate exact $n$ persoane, dintre care cel putin $n-1$ trebuie sa fie copii si cel mult un profesor;
* copiii cazati in fiecare cabana trebuie sa provina din regiuni diferite ale tarii;
* nici un copil sau profesor nu poate fi cazat in mai multe cabane.
h2. Cerinta
Sa se gaseasca numarul maxim $M$ de cabane care pot fi completate respectand restrictiile de mai sus.
h2. Date de intrare
Fisierul de intrare $tabara.in$ ...
Fisierul de intrare $tabara.in$ contine pe prima linie doua numere naturale $n$ si $p$, unde $n$ este numarul de regiuni, iar $p$ este numarul de profesori. Pe linia a doua, se gasesc $n$ numere naturale, $c1$, $c2$, ... $cn$ separate prin cate un spatiu. Valoarea $ci$ reprezinta numarul copiilor venii din regiunea $i$.
h2. Date de iesire
In fisierul de iesire $tabara.out$ ...
In fisierul de iesire $tabara.out$ se va scrie pe prima linie numarul natural $M$.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $2 ≤ n, p ≤ 50000$
* $1 ≤ c1, c2, ... cn ≤ 50000$
* Este posibil ca dupa completarea celor $M$ cabane, nu toti elevii si/sau profesorii sa fie cazati
* Numarul total de persoane care trebuie cazate nu va depasi pe nici un test $2.000.000.000$
h2. Exemplu
table(example). |_. tabara.in |_. tabara.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2 2
1 3
| 3
|
| 3 4
2 3 4
| 4
|
h3. Explicatie
...
* 1. Codificand cele doua regiuni cu x si y, se pot completa maxim 3 cabane in felul urmator: [ $x1$, $y1$ ], [ $p1$, $y2$ ], [ $p2$, $y3$ ] . $x1$ reprezinta singurul copil din regiunea $1$, $y1$, $y2$, $y3$ reprezinta cei trei copii din regiunea $2$, iar $p1$, $p2$ sunt cei doi profesori.
* 2. Daca cele 3 regiuni sunt $x$, $y$, $z$, atunci se pot completa $4$ cabane in felul urmator: [ $x1$, $y1$, $z1$ ], [ $x2$, $p1$, $z2$ ], [ $p2$, $y2$, $z3$ ], [ $p3$, $y3$, $z4$ ]. $x1$, $x2$ identifica cei doi copii din regiunea $1$, etc. Profesorul $p4$ nu va fi cazat.
== include(page="template/taskfooter" task_id="tabara") ==
