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:

Dati di output

La massima somma è un intero scritto sul file OUTPUT.TXT file. Nel nostro esempio:

Struttura dati fondamentale e algoritmo

L'idea iniziale è quella di memorizzare il triangolo in un array. Notate che la prima riga del triangolo contiene 1 elemento, la seconda 2 elementi e così via.
Quindi, il primo elemento della r-esima riga è preceduto da 1+2+...+(r-1) elementi, e quindi ha indice r(r-1)/2+1=(r^2-r+2)/2. Il suo ultimo elemento ha indice
(r^2-r+2)/2+r-1=(r^2+r)/2.
Chiamiamo "figli dell'elemento di indice i" gli elementi (se ci sono) che si trovano sulle due diagonali scendendo di un livello. Questi determinano due sottotriangoli: naturalmente la soluzione ottima si ottiene prendendo le soluzioni ottime dei sottotriangoli, scegliendo il massimo e aggiungendo il valore dell'elemento.

Questo lo si può fare all'indietro a partire dalla penultima riga:

procedure maxsomma;
(* Calcola le massime somme "sul posto" *)
var r,i: byte;
        index: word;
begin
    index:=trunc((sqr(nr-1)+nr-1)/2); (* Indice ult. elemento penultima riga *)
    for r:=nr-1 downto 1 do
        for i:=r downto 1 do
            begin
                (* Calcolo il valore max relativo all'i-esimo elem. della riga r, il cui indice e' index *)
                t[index]:=t[index]+max(t[index+r],t[index+r+1]);
                dec(index)
            end
end;