== 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, {$c{~1~}$}, {$c{~2~}$}, ... {$c{~n~}$} separate prin cate un spatiu. Valoarea {$c{~i~}$} 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 ≤ 50.000$
* {$1 ≤ c{~1~}, c{~2~}, ... c{~n~} ≤ 50.000$}
* 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
...
# Codificand cele doua regiuni cu x si y, se pot completa maxim 3 cabane in felul urmator: [ {$x{~1~}$}, {$y{~1~}$} ], [ {$p{~1~}$}, {$y{~2~}$} ], [ {$p{~2~}$}, {$y{~3~}$} ] . {$x{~1~}$} reprezinta singurul copil din regiunea $1$, {$y{~1~}$}, {$y{~2~}$}, {$y{~3~}$} reprezinta cei trei copii din regiunea $2$, iar {$p{~1~}$}, {$p{~2~}$} sunt cei doi profesori.
# Daca cele 3 regiuni sunt $x$, $y$, $z$, atunci se pot completa $4$ cabane in felul urmator: [ {$x{~1~}$}, {$Y{~1~}$}, {$Z{~1~}$} ], [ {$x{~2~}$}, {$p{~1~}$}, {$z{~2~}$} ], [ {$p{~2~}$}, {$y{~2~}$}, {$z{~3~}$} ], [ {$p{~3~}$}, {$y{~3~}$}, {$z{~4~}$} ]. {$x{~1~}$}, {$x{~2~}$} identifica cei doi copii din regiunea $1$, etc. Profesorul {$p{~4~}$} nu va fi cazat.
== include(page="template/taskfooter" task_id="tabara") ==
