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.

Dacă Mario cade pe o distanță mai mare decât H, atunci își pierde toată energia și nu mai poate continua jocul.

Cerința

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 mario.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 platforme;
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 mario.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 și precizări

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 2⁶³

Exemplu

mario.in

mario.out

Explicație

Turnul se află la înălțimea 14 față de sol și are abscisa 8. Mario poate coborî liber cel mult 7 de unități.

Există 4 platforme:

o platformă e situată la înălțimea 9 față de sol și are extremitățile în 8 și 15
Altă platformă se află la înălțimea 2 față de sol și are extremițățile în 10 și 13.
Următoarea platformă se află la o înălțime de 12 și are extremitatea stângă în 6 iar cea dreaptă în 11.
Ultima platformă se află la 4 unități față de sol și are extremitățile în 2 și 10.

Sunt 3 drumuri distincte pe care Mario poate coborî din turn până la sol.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Mario:

#include <stdio.h>
#include <stdlib.h>
using namespace std;
struct segment {
    int h;
    int x1, x2;
    long long nr_drumuri;
}platforma[20010];

int N, hM,xM,H;

void citire()
{
    FILE *f=fopen("mario.in","r");
    fscanf(f,"%d %d %d",&hM,&xM,&H);
    fscanf(f,"%d",&N);
    for (int i=0;i<N;i++)
        fscanf(f, "%d %d %d",&platforma[i].h,&platforma[i].x1,&platforma[i].x2);
    platforma[N].h=0;
    platforma[N].x1=0;
    platforma[N].x2=200001;
    N++;
    fclose(f);
}
void afisare()
{
    long long d;
    FILE *f=fopen("mario.out","w");
    fprintf(f,"%lld
", platforma[N-1].nr_drumuri);
    fclose(f);
}
int compare (const void * a, const void * b)
{
  segment *segmentA = (segment *)a;
  segment *segmentB = (segment *)b;
  return (segmentB->h-segmentA->h );
}

void cade(int h,int x,long long nr_drumuri)
{
    int i=0;
    while (i<N && (h-platforma[i].h>H || h-platforma[i].h<=0 || x<platforma[i].x1 || x>platforma[i].x2))
        i++;
    if (i<N)
        platforma[i].nr_drumuri+=nr_drumuri;
}

void calcul()
{
    cade(hM,xM,1);
    for (int i=0;i<N-1;i++)
    {
        if (platforma[i].nr_drumuri)
        {
            cade(platforma[i].h,platforma[i].x1,platforma[i].nr_drumuri);
            cade(platforma[i].h,platforma[i].x2,platforma[i].nr_drumuri);
        }
    }
}

int main()
{
    citire();
    qsort(platforma,N,sizeof(segment),compare);
    calcul();
    afisare();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #696 Mario

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #696 Mario de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #696 Mario