Zoccolo, Carta, Forbici (Oro)#10551
Probabilmente avete sentito parlare del gioco "Sasso, carta, forbici". Alle mucche piace giocare a un gioco simile, che chiamano "Zoccolo, carta, forbici".
Le regole del gioco "Zoccolo, carta, forbici" sono semplici. Due mucche giocano l'una contro l'altra. Contano fino a tre, dopodiché mostrano contemporaneamente un gesto che rappresenta zoccolo, carta o forbici. Lo zoccolo batte le forbici (perché lo zoccolo può schiacciare le forbici), le forbici battono la carta (perché le forbici possono tagliare la carta) e la carta batte lo zoccolo (perché lo zoccolo può essere avvolto dalla carta). Ad esempio, se la prima mucca mostra "zoccolo" e la seconda mostra "carta", allora vince la seconda mucca. Naturalmente, il gioco può anche finire in pareggio se entrambe le mucche mostrano lo stesso gesto.
Il Fattore John vuole giocare con la sua migliore mucca Bessie a partite del gioco "Zoccolo, carta, forbici". Bessie, essendo un'esperta in questo gioco, riesce a prevedere ogni gesto di FJ prima che lui lo mostri. Sfortunatamente, Bessie, essendo una mucca, è anche molto pigra. Perciò tende a mostrare lo stesso gesto più volte di seguito. Inoltre, per tutte le partite, è disposta a cambiare gesto al massimo volte. Ad esempio, se k = 2, potrebbe mostrare "zoccolo" nelle prime partite, poi passare a "carta" per un po', e poi passare di nuovo a "zoccolo" nelle partite rimanenti.
Data la sequenza di gesti che FJ mostrerà, determinate il numero massimo di partite che Bessie può vincere.
Nella prima riga sono contenuti n~(1 \le n \le 10^5) e k~(0 \le k \le 20). Nelle successive righe sono contenuti i gesti di FJ — ciascuno di essi è uguale a oppure .
Stampate il numero massimo di partite che Bessie può vincere, se può cambiare il proprio gesto al massimo volte.
Esempio 1