tabara

Tabara

== 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") ==

3339