== include(page="template/taskheader" task_id="mario2") ==
Poveste şi cerinţă...
Jocurile cu Mario sunt jocuri on-line pentru copii de toate vârstele. Acum, Mario-personajul din joc, are nevoie de ajutorul vostru pentru a ajunge din turnul castelului unde se află, la sol, unde îl aşteaptă cu nerăbdare prinţesa Peach.
Coborârea din turn se face cu ajutorul unor platforme orizontale, de diferite lungimi, fiecare dintre ele aflându-se la o anumită înălţime faţă de sol. Deplasarea din turn spre sol se va face astfel:
- Mario îşi dă drumul în cădere liberă din turn şi cade sub efectul greutăţii sale;
- dacă în cădere, el ajunge pe o platformă, se va deplasa pe suprafaţa acesteia spre unul din capetele din stânga sau din dreapta ale acesteia, urmând ca de acolo să procedeze la fel, lăsându-se din nou în cădere liberă spre sol. Se considera ca ajunge pe o platforma daca o intalneste in macar un punct, chiar si extremitate.
Dacă Mario cade pe o distanţă *mai mare decât $H$*, atunci îşi pierde toată energia şi nu mai poate continua jocul.
h2. Cerinţă
Cunoscând poziţia în care se află Mario şi modul de aşezare al platformelor (date în coordonate carteziene), determinaţi *numărul drumurilor distincte* pe care le poate parcurge Mario pentru a ajunge la prinţesă.
h2. Date de intrare
Fişierul de intrare $mario2.in$ ...
Din fişierul $mario2.in$ se va citi:
- de pe prima linie trei numere naturale {$h{~M~}$}, {$x{~M~}$} şi $H$ reprezentând în ordine: înălţimea la care se află Mario faţă de sol, abscisa poziţiei sale şi înălţimea maximă pe care o poate parcurge în cădere;
- de pe cea de-a doua linie un număr natural $N$ ce reprezintă numărul de paltforme;
- de pe următoarele $N$ linii câte trei numere naturale $(h{~p~}, x1, x2)$ cu semnificaţia: la înălţimea $hp$ faţă de sol se află o platformă orizontală cu extremitatea stângă în $x1$ şi extremitatea dreaptă în $x2$.
h2. Date de ieşire
În fişierul de ieşire $mario2.out$ ...
În fişierul $mario2.out$ se va scrie pe prima linie un singur număr natural reprezentând numărul drumurilor distincte pe care le poate parcurge Mario până la prinţesă.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 10 000$
* $0 < H, h{~p~}, h{~M~} ≤ 20 000 (h{~M~} > h{~p~})$
* $0 < x{~M~}, x1, x2 ≤ 200 000$
* dacă există mai multe platforme la aceeaşi înălţime se garantează că ele nu se suprapun în niciun punct;
* numărul drumurilor este întotdeauna mai mare decât $0$ şi mai mic decât $2^63^$
* $x1 < x2$
h2. Exemplu
table(example). |_. mario2.in |_. mario2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
| 14 8 7
4
9 8 15
2 10 13
12 6 11
4 2 10 | 3 |
== include(page="template/taskfooter" task_id="mario2") ==
