==Include(page="template/taskheader" task_id="grupuri")==
==Include(page="template/raw")==
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.
h2. Cerinta
Stiind ca Bronzarel avea N tipuri de animale, si cantitatea A[i] din fiecare tip, determinati care este numarul maxim de grupuri pe care le poate forma, pentru a le vinde la targ.
h2. Date de Intrare
Prima linie a fisierului grupuri.in va contine numerele naturale K si N. Urmatoarea linie va contine N numere naturale A[1],A[2],...A[N] reprezetand cantitatile disponibile din fiecare tip de animal. Cantitatile vor fi date in ordine crescatoare (A[i] <= A[i+1]).
h2. 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.
h2. Restrictii si observatii
S 1 <= K <= N <= 100.000
S 0 <= A[i] <= 1.000.000
S Pentru cel putin 60% din teste N <= 50
Exemple
|grupuri.in |grupuri.out |Explicatie |
|3 4 |4 |Presupunand ca animalele sunt vaci, cai, oi si gaini, o distribuire in grupuri ar putea fi: |
| | | |
|3 3 3 3 | |(vaca, cal, oaie) |
| | | |
| | |(vaca, cal, gaina) |
| | | |
| | |(vaca, oaie, gaina) |
| | | |
| | |( cal, oaie, gaina) |
|5 7 |5 |Vom considera acum ca tipurile de animalele sunt numerotate de la 1 la 7. |
| | | |
|1 2 3 4 5 6 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) |
==Include(page="template/taskheader" task_id="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*}.
h2. Cerinta
Stiind ca Bronzarel avea $N$ tipuri de animale, si cantitatea $A{~i~}$ din fiecare tip, determinati care este numarul maxim de grupuri pe care le poate forma, pentru a le vinde la targ.
h2. Date de Intrare
Prima linie a fisierului $grupuri.in$ va contine numerele naturale $K$ si {$N$}. Urmatoarea linie va contine $N$ numere naturale $A{~1~},A{~2~},...A{~N~}$ reprezetand cantitatile disponibile din fiecare tip de animal. Cantitatile vor fi date in {*ordine crescatoare*} ({$A{~i~} ≤ A{~i+1~}$}).
h2. 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.
h2. Restrictii si observatii
* $1 ≤ K ≤ N ≤ 100.000$
* $0 ≤ A{~i~} ≤ 1.000.000$
* Pentru cel putin $60%$ din teste $N ≤ 50$
h2. Exemplu
table(example). |_. grupuri.in |_. grupuri.out |
| 3 4
3 3 3 3
| 4 |
| 5 7
1 2 3 4 5 6 7
| 5 |
h3. 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$})
==Include(page="template/taskfooter" task_id="grupuri")==
==Include(page="template/taskfooter" task_id="grupuri")==
