E' ben nota l'antipatia umorale della Regina di Cuori per certi numeri: per esempio, odia il numero 13; non solo, anche il 17 non è molto amato da Sua Maestà. Ahimè, questi non sono gli unici casi poiché ci sono diversi numeri M che non sono tollerati dalla Regina e a farne le spese sono i poveri giardinieri. Il problema è che, ogni mattina, la Regina si alza e indica ai giardinieri qual è il numero M che le è antipatico quel giorno.
Lungo il dritto viale che porta alla regale dimora, c'è un filare di N piante di rose. Purtroppo, la Regina conta le rose mentre passeggia nel viale e non sopporta che una sequenza di una o più piante consecutive contenga un totale di M rose: ha fatto tagliare diverse teste per questioni meno gravi.
I giardinieri sono terrorizzati dal fatto che lo Stregatto ci abbia messo lo zampino, alterando il numero di rose in modo da far apparire M rose. Aiutali a individuare il numero S di sequenze le cui piante totalizzano M rose nel filare. Notare che alcune piante possono contenere zero rose.
Per esempio, con un filare di N=20 piante, contenenti
rispettivamente 2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0,
0, 2 rose, il numero
M=9 appare in S=18 sequenze:
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
Il file input.txt è composto da due righe.
La prima riga contiene due interi M e N separati da uno spazio: M è il numero antipatico alla Regina di Cuori quel giorno, e N è il numero di piante lungo il filare che costeggia il viale.
La seconda riga contiene N interi positivi separati da uno spazio: l'I-esimo intero indica il numero di rose nella I-esima pianta nel filare.
Il file output.txt è composto da una sola riga che contiene l'intero positivo S, a indicare il numero di sequenze di piante nel filare che totalizzano M rose.
| File input.txt | File output.txt |
9 20 2 3 0 4 0 3 1 0 1 0 1 0 0 0 5 0 4 0 0 2 | 18 |
| File input.txt | File output.txt |
0 5 0 0 0 0 0 | 15 |