Cerința
Dându-se n
fracții ireducitibile sortate crescător și un număr k
să se determine numărul de subșiruri de exact k
elemente în care diferența dintre două fracții consecutive este egală cu 1
. De asemenea, prima fracție din subșir trebuie să nu fie supraunitara.
Date de intrare
Fișierul de intrare fractii3.in
conține pe prima linie numerele n
și k
, iar pe următoarele n
linii câte două numere a
și b
, reprezentând numărătorul și numitorul unei fracții.
Date de ieșire
Fișierul de ieșire fractii3.out
va conține pe prima linie numărul S
, reprezentând numărul de subșiruri.
Restricții și precizări
1 ≤ k ≤ n ≤ 1.000.000
1 ≤ a, b ≤ 10.000
0 <
\({a \over b}\)≤ k
- Fracțiile sunt sortate și nu vor exista două fracții consecutive cu aceeași valoare.
- Pentru
20%
din punctaj,n ≤ 10
Exemplu:
fractii3.in
6 3 1 3 1 2 7 8 4 3 3 2 5 2
fractii3.out
1
Explicație
Doar subșirul format din fracțiile \({1 \over 2}, {3 \over 2}, {5 \over 2}\) este valid.