Numeri antipatici

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
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.

Notice: This work is licensed under a BY-NC-SA. Permalink: Numeri antipatici

Comments are closed.