Zoccolo, Carta, Forbici (Argento)#10548
Probabilmente avete sentito parlare del gioco «Sasso, Forbici, Carta». 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 uno zoccolo, un foglio di carta, oppure un paio di forbici. Lo zoccolo batte le forbici (poiché lo zoccolo può schiacciare le forbici), le forbici battono la carta (poiché le forbici possono tagliare la carta), e la carta batte lo zoccolo (poiché lo zoccolo può essere tagliato dalla carta). Per esempio, se la prima mucca mostra «zoccolo» e la seconda — «carta», allora la seconda mucca vince. 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 partite al gioco «Zoccolo, Carta, Forbici». Bessie, essendo un'esperta di 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, durante tutte le partite è disposta a cambiare gesto al massimo una volta. Per esempio, può mostrare «zoccolo» nelle prime partite, e poi passare a «carta» nelle restanti n - x partite.
Data la sequenza di gesti che FJ mostrerà, determinate il numero massimo di partite che Bessie può vincere.
La prima riga contiene n~(1 \le n \le 10^5). Le successive righe contengono i gesti del Fattore John — ognuno di essi è , oppure .
Stampate il numero massimo di partite che Bessie può vincere, se può cambiare il proprio gesto al massimo una volta.
Esempio 1