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 apparireM 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 numeroM=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
Dati in Input
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.
Dati in Output
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.
Assunzioni
- 0 <= M < 231
- 1 <= N <= 1 000 000
- 1 <= S < 231, maledetto Stregatto!
- 0 <= I < 231, dove I è il numero di rose in una pianta.
Esempi
| input.txt | output.txt | |
|---|---|---|
| 1 | 9 20 2 3 0 4 0 3 1 0 1 0 1 0 0 0 5 0 4 0 0 2 |
18 |
| 2 | 0 5 0 0 0 0 0 |
15 |
Nota
Una sequenza può essere composta anche da una sola pianta, se quest’ultima contiene esattamente M rose.