Fişierul intrare/ieşire:caibicol.in, caibicol.outSursăRomanian Open Contest, TIMUS 2001
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.35 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.incaibicol.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content