0696 - Mario

Enunt

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 marioin.txt 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 marioout.txt 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 263

Exemplu 1

marioin.txt

14 8 7

4

9 8 15

2 10 13

12 6 11

4 2 10

marioout.txt

3

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.

Exemplu 2

marioin.txt

0 0 0

marioout.txt

Nu au fost respectate cerintele impuse.

Rezolvare

#0696 - Mario
def read_input(file_name):
    try:
        with open(file_name, 'r') as file:
            hM, xM, H = map(int, file.readline().split())
            N = int(file.readline())
            platforms = [list(map(int, file.readline().split())) for _ in range(N)]

            return hM, xM, H, N, platforms
    except Exception as e:
        print(f"Nu au fost respectate cerintele impuse: {str(e)}")
        return None

def write_output(file_name, result):
    with open(file_name, 'w') as file:
        if result is not None:
            file.write(str(result) + "\n")

def count_paths(hM, xM, H, N, platforms):
    dp = [0] * (hM + 1)
    dp[hM] = 3

    platforms.sort(key=lambda x: x[0])

    for h in range(hM, 0, -1):
        for platform in platforms:
            hp, x1, x2 = platform
            if h <= hp and xM >= x1 and xM <= x2:
                for i in range(h - 1, max(0, h - H) - 1, -1):
                    dp[i] += dp[h]

    return sum(dp)

def main(input_file, output_file):
    result = read_input(input_file)
    if result is not None:
        hM, xM, H, N, platforms = result
        result = count_paths(hM, xM, H, N, platforms)
        write_output(output_file, result)

if __name__ == "__main__":
    main("marioin.txt", "marioout.txt")