caibicol

Cai bicolorati

== include(page="template/taskheader" task_id="caibicol") ==

Poveste si cerinta...

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 $P{~1~}$ cai vor intra in primul grajd, urmatorii $P{~2~}$ 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.

h2. 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$.

h2. Date de iesire

...

In fisierul de iesire $caibicol.out$ veti afisa coeficientul total de agresivitate minim posibil.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 500$
* $1 ≤ K ≤ N$

h2. Exemplu
table(example). |_. caibicol.in |_. caibicol.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|6 3
1
1
0
1
0
1
|2

|
h3. 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.

== include(page="template/taskfooter" task_id="caibicol") ==

2297