25ος ΠΔΠ Γ' Φάση
Τρίγωνο (triangle)

[30 Μονάδες]

Δίνεται ένα τρίγωνο αριθμών της μορφής του παρακάτω σχήματος.

Παράδειγμα

Φανταστείτε ότι ξεκινάμε από την πάνω κορυφή του τριγώνου και κατεβαίνουμε προς τα κάτω, μέχρι τη βάση, αθροίζοντας αριθμούς. Σε κάθε βήμα μπορούμε να πηγαίνουμε είτε διαγώνια κάτω και αριστερά, ή διαγώνια κάτω και δεξιά. Για παράδειγμα, μπορούμε να ακολουθήσουμε το μονοπάτι \(7\), \(3\), \(1\), \(4\), \(2\) και, αθροίζοντας τους αριθμούς σε αυτό, να πάρουμε άθροισμα \(17\).

Πρόβλημα

Nα αναπτύξετε ένα πρόγραμμα σε μία από τις γλώσσες του ΙΟΙ το οποίο, αφού διαβάσει τους αριθμούς που αποτελούν το τρίγωνο, να υπολογίζει το μέγιστο άθροισμα των αριθμών που συναντάμε ξεκινώντας από την πάνω κορυφή του τριγώνου και καταλήγοντας σε κάποιο σημείο της κάτω βάσης του.

Aρχεία εισόδου

Τα αρχεία εισόδου με όνομα triangle.in είναι αρχεία κειμένου με την εξής δομή: Η πρώτη γραμμή περιέχει έναν ακέραιο \(N\) (\(1 \leq N \leq 1.000\)), που παριστάνει το πλήθος των γραμμών του τριγώνου. Οι επόμενες \(N\) γραμμές περιέχουν τους ακέραιους αριθμούς κάθε μίας γραμμής του τριγώνου, από αριστερά προς τα δεξιά, χωρισμένους ανά δύο με ένα κενό διάστημα. Οι αριθμοί αυτοί θα είναι μεταξύ \(0\) και \(99\).

Aρχεία εξόδου

Τα αρχεία εξόδου με το όνομα triangle.out είναι αρχεία κειμένου με την εξής δομή: Έχουν μία γραμμή με ακριβώς έναν αριθμό, το μέγιστο άθροισμα που μπορεί να επιτευχθεί.

Παράδειγμα αρχείων εισόδου - εξόδου

triangle.in	triangle.out
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5	30

Εξήγηση: Η είσοδος αντιστοιχεί στο τρίγωνο του σχήματος της προηγούμενης σελίδας. Το μέγιστο άθροισμα είναι \(30\) και προκύπτει από το μονοπάτι \(7\), \(3\), \(8\), \(7\), \(5\).