Fişierul intrare/ieşire:tabara.in, tabara.outSursăLot Juniori 2008 - Baraj 3
AutorConstantin GalatanAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.intabara.out
2 2
1 3
3
3 4
2 3 4
4

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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content