IOI'94 - Giorno 1 - Problema 1: Il triangolo
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 (Figura 1)
La Figura 1 mostra un triangolo. Scrivete un programma che calcoli
la più grande somma di numeri ottenibile seguendo un percorso che
parta dalla cima del triangolo e termini da qualche parte sulla sua base.
-
Ad ogni passo si può procedere diagonalmente in basso o a destra
o a sinistra.
-
Il triangolo ha un numero di righe >1 ma <=100.
-
I numeri del triangolo sono interi compresi fra 0 e 99.
Dati di input
I dati sono contenuti nel file INPUT.TXT. Sulla prima riga compare
il numero di righe del triangolo, e sulle righe successive compaiono le
varie righe del triangolo stesso. Nel nostro esempio, INPUT.TXT
è come segue:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Dati di output
La massima somma è un intero scritto sul file OUTPUT.TXT
file. Nel nostro esempio:
30