| Fişierul intrare/ieşire: | caibicol.in, caibicol.out | Sursă | Romanian Open Contest, TIMUS 2001 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Caibicol
In fiecare zi, fermierul Ion isi scoate la aer toti caii, pentru ca acestia sa poata alerga si sa se poata juca. Cand caii termina cu distractia, fermierul Ion trebuie sa ii duca pe cai inapoi in grajduri. Pentru a realiza acest lucru, el ii aranjeaza intr-un sir si acestia il vor urma pana la grajduri. Deoarece caii sunt foarte obositi, fermierul Ion decide sa nu-i supuna la prea mult efort suplimentar, astfel ca inventeaza urmatorul algoritm: primii P1 cai vor intra in primul grajd, urmatorii P2 cai vor intra in al doilea grajd s.a.m.d. Nici unul din cele K grajduri nu trebuie sa ramana gol si nici un cal nu trebuie sa ramana pe afara. Acum ar fi bine sa stiti ca fermierul Ion are doar cai albi si negri, care nu se inteleg prea bine unii cu altii. Daca intr-un grajd intra x cai albi si y cai negri, atunci coeficientul de agresivitate din acel grajd este x*y. Coeficientul total de agresivitate este egal cu suma coeficientilor de agresivitate din fiecare grajd.
Determinati o modalitate de a distribui cei N cai in cele K grajduri, in asa fel incat coeficientul total de agresivitate sa fie minim.
Date de intrare
Pe prima linie a fisierului de intrare caibicol.in se afla numerele intregi N si K, separate printr-un spatiu. Urmatoarele N linii contin culorile cailor, in ordinea in care acestia sunt asezati in sir. Daca al i-lea cal este alb, atunci a i-a dintre aceste linii contine numarul 0; in caz contrar, ea va contine numarul 1.
Date de iesire
In fisierul de iesire caibicol.out veti afisa coeficientul total de agresivitate minim posibil.
Restrictii
- 1 ≤ N ≤ 500
- 1 ≤ K ≤ N
Exemplu
| caibicol.in | caibicol.out |
|---|---|
| 6 3 1 1 0 1 0 1 | 2 |
Explicatie
Primii 2 cai vor intra in primul grajd, urmatorii 3 cai vor intra in al doilea grajd, iar ultimul cal va intra in al 3-lea grajd.
