Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | grupuri.in, grupuri.out | Sursă | preONI 2006 Runda 2 |
Autor | Mircea Bogdan Pasoi | Adăugată de | |
Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
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.in | grupuri.out |
---|---|
3 4 3 3 3 3 | 4 |
5 7 1 2 3 4 5 6 7 | 5 |
Explicatie
- Presupunand ca animalele sunt vaci, cai, oi si gaini, o distribuire in grupuri ar putea fi:
- (vaca, cal, oaie)
- (vaca, cal, gaina)
- (vaca, oaie, gaina)
- (cal, oaie, gaina)
- Vom considera acum ca tipurile de animalele sunt numerotate de la 1 la 7
- (1, 3, 5, 6, 7)
- (2, 4, 5, 6, 7)
- (2, 4, 5, 6, 7)
- (3, 4, 5, 6, 7)
- (3, 4, 5, 6, 7)