Volei

Echipa de volei UNSTPB se așează în linie, la diferite distanțe unii de alții.

Un jucător cu puterea $k$ poate face următoarea acțiune: lansează mingea $k$ poziții la dreapta sau la stânga, aceasta oprindu-se la primul jucător pe care-l atinge. Daca la prima cădere nu atinge un jucător, atunci aceasta va sări din $k$ în $k$ pătrățele, până atinge pe cineva sau iese afară.

Jucătorul care primește mingea, având altă putere $k$, poate s-o dea în stânga sau dreapta, în același mod.

Știm jucătorul care are inițial mingea. Presupunem că se simulează toate cazurile (pentru fiecare jucător, când lansează mingea primită, în stânga, apoi în dreapta). Câți jucători vor fi avut mingea în cel puțin unul dintre cazuri?

Cerință

Aveți la dispoziție un program C++ (aici sau în secțiunea „Atașamente” din lateral) care implementează problema anterioară, dar acesta conține câteva bug-uri. Corectați programul.

Indicație

Se folosește un algoritm de fill, unde utilizăm un vector $v$ de $1$ și $0$, astfel:

• dacă $v_i$ ajunge $1$, atunci jucătorul $i$ a fost atins la un moment dat;
• dacă $v_i$ rămâne $0$, atunci jucătorul $i$ nu a fost atins niciodată.

La început, $v_{start} = 1$, iar restul elementelor sunt $0$. Avem două cazuri:

• mingea e aruncată la stânga, din $k$ în $k$;
• mingea e aruncată la dreapta, din $k$ în $k$.

Dacă jucătorul $i$ este atins într-unul dintre cazuri, atribuim $v_i = 1$, și apelăm recursiv funcția de fill pentru jucătorul $i$.

Se repetă procesul până când nu se mai poate atinge un jucător nou.

Date de intrare

Se citeste $n$ de la tastatură.

Pe următoarele $n$ linii se află câte o pereche $a_i \ b_i$ de numere naturale, unde $a$ reprezintă poziția jucătorului $i$, iar $b$ este puterea acestuia.

După, se citește $start$, indicele jucătorului care are mingea la început.

Date de ieșire

Se va afișa numărul de jucători care primesc mingea la un moment dat, în oricare dintre cazuri.

Restricții și precizări

• $1 \le n \le 1\ 000$
• $1 \le a_i \le 1\ 000\ 000\ 000$
• $1 \le b_i \le 1\ 000$
• $1 \le start \le n$
• Se garantează ca jucătorii sunt deja sortați în ordinea în care sunt așezați în linie, începând de la poziția cea mai mică.
• În numărare se consideră și jucătorul inițial
• Nu există doi jucători pe aceeași poziție.

Exemplul 1

stdin

8
1 1
2 10
4 3
5 2
7 4
9 5
11 9
12 1000
4

stdout

6

Explicație

Așezarea jucătorilor în linie arată astfel ($\textcolor{red}{\text{x}}$ este pentru loc unde nu e vreun jucător):

$1\ 10 \textcolor{red}{\text{ x }} 3\ 2 \textcolor{red}{\text{ x }} 4 \textcolor{red}{\text{ x }} 5 \textcolor{red}{\text{ x }} 9\ 1000$

• Jucătorul (de poziție) 4 (de putere $3$) îi atinge pe $1$ și pe $7$.
• Jucătorul $1$ îl atinge pe $2$.
• Jucătorul $7$ îl atinge pe $11$.
• Jucătorul $2$ îl atinge $12$.
• Jucătorul $11$ îl atinge pe $2$.
• Jucătorul $12$ nu atinge pe nimeni.

În total, au fost atinși $5$ jucători.

Exemplul 2

stdin

3
4000 7
293644 8
8661523 11
1

stdout

2

Explicație

• Jucătorul $4000$ lansează mingea în dreapta, și sare din $7$ în $7$, până se oprește la jucătorul $8661523$.
• Jucătorul $8661523$ nu poate da mingea nimănui.
• Jucătorul $293644$ NU primește mingea.