0696 - Mario: Difference between revisions
Pagină nouă: == 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... |
No edit summary |
||
Line 35: | Line 35: | ||
;marioout.txt | ;marioout.txt | ||
:3 | :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 == | == Exemplu 2 == | ||
;marioin.txt | ;marioin.txt |
Latest revision as of 15:21, 6 January 2024
Enunt[edit | edit source]
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[edit | edit source]
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[edit | edit source]
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[edit | edit source]
Î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[edit | edit source]
- 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[edit | edit source]
- marioin.txt
- 14 8 7
- 4
- 9 8 15
- 2 10 13
- 12 6 11
- 4 2 10
- marioout.txt
- 3
Explicație[edit | edit source]
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[edit | edit source]
- marioin.txt
- 0 0 0
- marioout.txt
- Nu au fost respectate cerintele impuse.
Rezolvare[edit | edit source]
<syntaxhighlight lang="python" line>
- 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")
</syntaxhighlight>