Η ΣΚΥΤΑΛΟΔΡΟΜΙΑ

Τρεις φίλοι, ο Ανδρέας, ο Βασίλης και ο Γιώργος, πρόκειται να τρέξουν σε έναν αγώνα σκυταλοδρομίας μεγάλης απόστασης. Ο αγώνας γίνεται κατά μήκος ενός δρόμου που περνάει από πολλά χωριά και οι τρεις φίλοι γνωρίζουν ότι η διαδρομή αποτελείται από N τμήματα (από την αφετηρία μέχρι το πρώτο χωριό, από το πρώτο μέχρι το δεύτερο, κ.ο.κ., μέχρι τον τερματισμό που βρίσκεται στο Ν-οστό χωριό) και επίσης γνωρίζουν το μήκος κάθε τμήματος σε μέτρα. Σύμφωνα με τους κανόνες του αγώνα, οι αλλαγές σκυτάλης πρέπει να γίνονται σε κάποιο χωριό της διαδρομής και οι τρεις φίλοι πρέπει εκ των προτέρων να αποφασίσουν πού ακριβώς θα τις κάνουν.

Οι φίλοι, που ξέρουν ποιος είναι καλύτερος δρομέας και τις αντοχές του καθενός, έχουν συμφωνήσει στα ακόλουθα:

1. Η σειρά που θα τρέξουν είναι: Ανδρέας, Βασίλης, Γιώργος.
2. Η συνολική απόσταση που θα τρέξει ο Βασίλης δεν μπορεί να είναι μεγαλύτερη από εκείνη που θα τρέξει ο Ανδρέας και, ομοίως, η συνολική απόσταση που θα τρέξει ο Γιώργος δεν μπορεί να είναι μεγαλύτερη από εκείνη που θα τρέξει ο Βασίλης.
3. Οι τρεις φίλοι θέλουν να μοιράσουν τη συνολική διαδρομή δίκαια, τηρουμένων των παραπάνω. Δηλαδή, ο Γιώργος (που θα τρέξει τελευταίος και λιγότερο) πρέπει να διανύσει όσο μεγαλύτερη απόσταση είναι δυνατόν. Αφού εξασφαλιστεί αυτό, ο Βασίλης πρέπει επίσης να διανύσει όσο μεγαλύτερη απόσταση είναι δυνατόν.
4. Αν τα παραπάνω δεν μπορούν να τηρηθούν, ο Γιώργος ή και ο Βασίλης ενδέχεται να μην τρέξουν καθόλου.

Με αυτούς τους περιορισμούς, βοηθήστε τους τρεις φίλους να βρουν την απόσταση που θα διανύσει καθένας.

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του IOI (PASCAL, C, C++, Java) το οποίο θα διαβάζει το πλήθος των τμημάτων της διαδρομής και το μήκος καθενός, και θα εκτυπώνει την απόσταση που θα διανύσει καθένας από τους τρεις φίλους.

Αρχεία εισόδου:

Τα αρχεία εισόδου με όνομα fairdiv.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή υπάρχει ένας ακέραιος αριθμός: το πλήθος N των τμημάτων της διαδρομής. Στη δεύτερη γραμμή υπάρχουν Ν ακέραιοι αριθμοί, χωρισμένοι ανά δύο με ένα κενό διάστημα: τα μήκη ~A_1~, ~A_2~, ~\cdots~ ~A_N~ των τμημάτων της διαδρομής.

Αρχεία εξόδου:

Τα αρχεία εξόδου με όνομα fairdiv.out είναι αρχεία κειμένου με την εξής δομή. Περιέχουν ακριβώς μία γραμμή η οποία περιέχει τρεις ακέραιους αριθμούς χωρισμένους ανά δύο με ένα κενό διάστημα. Ο πρώτος αριθμός είναι η συνολική απόσταση που θα διανύσει ο Ανδρέας, ο δεύτερος είναι η συνολική απόσταση που θα διανύσει ο Βασίλης και ο τρίτος είναι η συνολική απόσταση που θα διανύσει ο Γιώργος.

Περιορισμοί:

• ~1~ ~\le~ ~N~ ~\le~ ~1~.~000~.~000~
• ~0~ ~\le~ ~A_i~ ~\le~ ~1~.~000~

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

1o

STDIN (fairdiv.in)

10
78 43 72 17 66 63 20 58 1 56

STDOUT (fairdiv.out)

193 146 135

2o

STDIN (fairdiv.in)

5
17 42 3 42 17

STDOUT (fairdiv.out)

59 45 17

3o

STDIN (fairdiv.in)

5
10 20 30 40 100

STDOUT (fairdiv.out)

100 100 0

4o

STDIN (fairdiv.in)

4
10 10 10 40

STDOUT (fairdiv.out)

70 0 0

Εξήγηση των παραδειγμάτων:

Στο πρώτο παράδειγμα, οι φίλοι θα τρέξουν ως εξής:

• Ανδρέας: ~78~ + ~43~ + ~72~ = ~193~
• Βασίλης: ~17~ + ~66~ + ~63~ = ~146~
• Γιώργος: ~20~ + ~58~ + ~1~ + ~56~ = ~135~

Προσέξτε ότι η συνολική απόσταση που θα διανύσει ο Γιώργος δεν υπερβαίνει αυτήν που θα διανύσει ο Βασίλης, η οποία δεν υπερβαίνει αυτήν που θα διανύσει ο Ανδρέας. Δηλαδή ~193~ ~\ge~ ~146~ ~\ge~ ~135~. Προσέξτε επίσης ότι ο Γιώργος δεν μπορεί να διανύσει μεγαλύτερη απόσταση: αν τρέξει επιπλέον το τμήμα με μήκος ~63~, δηλαδή συνολική απόσταση ~63~ + ~20~ + ~58~ + ~1~ + ~56~ = ~198~, τότε δεν υπάρχει τρόπος οι άλλοι δύο φίλοι να μοιραστούν την υπόλοιπη διαδρομή έτσι ώστε να τηρούνται τα συμφωνημένα μεταξύ τους. Στο δεύτερο παράδειγμα, οι φίλοι μοιράζονται τη συνολική απόσταση ως εξής: ~17~ + ~42~ ~\ge~ ~3~ + ~42~ ~\ge~ ~17~. Προσέξτε ότι το τμήμα μήκους ~3~ θα το τρέξει ο Βασίλης, εφόσον αυτό είναι δυνατόν.

Στο τρίτο παράδειγμα, το τελευταίο τμήμα της διαδρομής είναι πολύ μεγάλο. Αν το τρέξει ο Γιώργος, τότε δεν υπάρχει τρόπος οι άλλοι δύο φίλοι να μοιραστούν σωστά την υπόλοιπη διαδρομή. Η μόνη λύση λοιπόν είναι ο Γιώργος να μην τρέξει καθόλου.

Τέλος, στο τελευταίο παράδειγμα τα μήκη των τμημάτων είναι τέτοια ώστε ο Ανδρέας θα τρέξει μόνος του όλη τη διαδρομή.

Παρατηρήσεις:

Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.

Μέγιστος χρόνος εκτέλεσης: 1 sec.
Μέγιστη διαθέσιμη μνήμη: 64 MB.
Επικεφαλίδες στον πηγαίο κώδικα: Στην αρχή του πηγαίου κώδικά σας, θα πρέπει να χρησιμοποιήσετε τις παρακάτω επικεφαλίδες.

(* USER: username
LANG: PASCAL
TASK: fairdiv *)

για κώδικα σε PASCAL

/* USER: username
LANG: C
TASK: fairdiv */

για κώδικα σε C

/* USER: username
LANG: C++
TASK: fairdiv */

για κώδικα σε C++

/* USER: username
LANG: Java
TASK: fairdiv */

για κώδικα σε Java

# USER: username
# LANG: Python
# TASK: fairdiv

για κώδικα σε Python

---