Egy kör alakú nyakláncon N darab gyöngy van (többféle színűek). A nyakláncot az i. gyöngy után elvághatjuk (1<= i <= N).
Feladat
Írjunk programot, ami megadja, hogy hol vágjuk el a nyakláncot, hogy a K távolságon belül tőle balra levő piros, illetve tőle jobbra levő zöld gyöngyök számának különbsége abszolút értékben a lehető legkisebb legyen!
Bemenet
A bemenet első sorában a gyöngyök N száma található (1<= N <= 1000000) és a K szám (1<= K <= N/2). A következő sor N karaktert tartalmaz, közülük az i. az i. gyöngy színe. A P a piros, a Z a zöld színt jelöli, a többi betű más színt jelöl.
Kimenet
A kimenet egyetlen sorában annak a gyöngynek a sorszámát kell írni, ami mögött elvágva a láncot minimális lesz a vágástól K távolságon belül balra levő piros és jobbra levő zöld gyöngyök számának különbsége.
Példa
Bemenet |
Kimenet |
20 6 ABPPZPPHHPPZZZZZPPPP | 14
|
Tesztadatok
Címkék
A feladat forrása: NTOITV 2012 3. forduló 9-10. évfolyam
Algoritmusok:
megoldás |