Fişierul intrare/ieşire:mario2.in, mario2.outSursăLot Juniori Deva 2013, baraj 1
AutorCristina IordaicheAdăugată deamaliarebAmalia Rebegea amaliareb
Timp execuţie pe test0.1 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Mario2

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.

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

Date de intrare

Din fişierul mario2.in se va citi:
- de pe prima linie trei numere naturale hM, xM ş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 (hp, 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.

Date de ieşire

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

Restricţii

  • 1 ≤ N ≤ 10 000
  • 0 < H, hp, hM ≤ 20 000 (hM > hp)
  • 0 < xM, 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 263
  • x1 < x2

Exemplu

mario2.inmario2.out
14 8 7
4
9 8 15
2 10 13
12 6 11
4 2 10
3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?