Fişierul intrare/ieşire:grupuri.in, grupuri.outSursăpreONI 2006 Runda 2
AutorMircea Bogdan PasoiAdăugată de
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Grupuri

Inainte sa se apuce de informatica, Bronzarel avea alta ocupatie, si anume era negustor de animale. Fiindca a renuntat la acesta profesie pentru cea de informatician, trebuie acum sa-si vanda animalele. La targ, el nu poate vinde doar un animal, ci trebuie sa le vanda pe grupuri, fiecare grup fiind format din fix K animale de tipuri distincte.

Cerinta

Stiind ca Bronzarel avea N tipuri de animale, si cantitatea Ai din fiecare tip, determinati care este numarul maxim de grupuri pe care le poate forma, pentru a le vinde la targ.

Date de Intrare

Prima linie a fisierului grupuri.in va contine numerele naturale K si N. Urmatoarea linie va contine N numere naturale A1,A2,...AN reprezetand cantitatile disponibile din fiecare tip de animal. Cantitatile vor fi date in ordine crescatoare (Ai ≤ Ai+1).

Date de Iesire

Pe prima linie din fisierul grupuri.out se va scrie o singura valoare reprezentand numarul maxim de grupuri care se pot forma.

Restrictii si observatii

  • 1 ≤ K ≤ N ≤ 100.000
  • 0 ≤ Ai ≤ 1.000.000
  • Pentru cel putin 60% din teste N ≤ 50

Exemplu

grupuri.ingrupuri.out
3 4
3 3 3 3
4
5 7
1 2 3 4 5 6 7
5

Explicatie

  1. Presupunand ca animalele sunt vaci, cai, oi si gaini, o distribuire in grupuri ar putea fi:
    1. (vaca, cal, oaie)
    2. (vaca, cal, gaina)
    3. (vaca, oaie, gaina)
    4. (cal, oaie, gaina)
  2. Vom considera acum ca tipurile de animalele sunt numerotate de la 1 la 7
    1. (1, 3, 5, 6, 7)
    2. (2, 4, 5, 6, 7)
    3. (2, 4, 5, 6, 7)
    4. (3, 4, 5, 6, 7)
    5. (3, 4, 5, 6, 7)
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content