| Fişierul intrare/ieşire: | tabara.in, tabara.out | Sursă | Lot Juniori 2008 - Baraj 3 |
| Autor | Constantin Galatan | Adăugată de |  Pripoae Teodor Anton •toni2007 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Tabara
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.
Cerinta
Sa se gaseasca numarul maxim M de cabane care pot fi completate respectand restrictiile de mai sus.
Date de intrare
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.
Date de iesire
In fisierul de iesire tabara.out se va scrie pe prima linie numarul natural M.
Restrictii
- 2 ≤ n, p ≤ 50.000
- 1 ≤ c1, c2, ... cn ≤ 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
Exemplu
| tabara.in | tabara.out |
|---|---|
| 2 2 1 3 | 3 |
| 3 4 2 3 4 | 4 |
Explicatie
- 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.
- 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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici
remote content
