27ος ΠΔΠ B' Φάση Λυκείου
Η μοιρασιά (share)
Τρία αδέρφια πρόκειται να εργαστούν στο μαγαζί του πατέρα τους για ένα χρονικό διάστημα. Το μαγαζί πηγαίνει καλά και κάθε μέρα παράγει κέρδος το οποίο τα τρία αδέρφια μπορούν να προβλέψουν. Τα αδέρφια έχουν συμφωνήσει ότι θα μοιράσουν το συνολικό χρονικό διάστημα σε τρία διαδοχικά τμήματα, όχι απαραίτητα ίσης διάρκειας, και ότι κάθε ένας θα εργάζεται στο μαγαζί κατά τη διάρκεια ενός από αυτά τα τμήματα και θα εισπράτει το αντίστοιχο κέρδος για λογαριασμό του.
Θέλουν όμως να κάνουν τη μοιρασιά δίκαια, έτσι ώστε να μην εισπράξει κάποιος από τους τρεις πολύ περισσότερο κέρδος από κάποιον άλλο. Συγκεκριμένα, θέλουν να ελαχιστοποιήσουν το κέρδος που θα εισπράξει ο πιο ευνοημένος από τους τρεις.
Πρόβλημα
Nα γραφεί πρόγραμμα σε μια από τις γλώσσες του ΙΟΙ το οποίο δοθέντος του πλήθους \(N\) των ημερών που τα τρία αδέρφια θα εργαστούν, καθώς και του προβλεπόμενου κέρδους κάθε μίας από αυτές τις μέρες, θα βρίσκει το ελάχιστο κέρδος που μπορεί να εισπράξει ο πιο ευνοημένος από τα τρία αδέρφια.
Aρχεία εισόδου
Τα αρχεία εισόδου με όνομα share.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή έχουν έναν ακέραιο αριθμό \(N\) (\(3 \leq N \leq 1.000.000\)), το πλήθος των ημερών. Ακολουθούν \(N\) γραμμές με τα προβλεπόμενα κέρδη για κάθε μία από αυτές τις μέρες, που είναι ακέραιοι αριθμοί \(V_i\) (\(1 \leq V_i \leq 100.000.000\)). Θεωρήστε δεδομένο ότι το συνολικό κέρδος (δηλαδή το άθροισμα όλων των \(V_i\)) δε θα υπερβαίνει το \(1.000.000.000\).
Aρχεία εξόδου
Τα αρχεία εξόδου με όνομα share.out είναι αρχεία κειμένου με την εξής δομή: Έχουν μια μόνο γραμμή που περιέχει ακριβώς έναν ακέραιο αριθμό, το ελάχιστο κέρδος που μπορεί να εισπράξει το πιο ευνοημένο από τα τρία αδέρφια.
Παραδείγματα αρχείων εισόδου - εξόδου
1o:
| share.in | share.out |
|---|---|
| 8 5 6 1 4 9 3 1 2 |
13 |
Εξήγηση: στην πιο δίκαιη δυνατή μοιρασιά, ο πρώτος αδερφός θα εργαστεί τρεις μέρες και θα εισπράξει κέρδος \(5+6+1=12\), ο δεύτερος θα εργαστεί δύο μέρες και θα εισπράξει κέρδος \(4+9=13\), και ο τρίτος θα εργαστεί τις υπόλοιπες τρεις μέρες και θα εισπράξει κέρδος \(3+1+2=6\). Ο πιο ευνοημένος θα είναι φυσικά ο δεύτερος.
2o:
| share.in | share.out |
|---|---|
| 10 1 1 8 1 1 3 4 9 5 2 |
15 |
Εξήγηση: στην πιο δίκαιη δυνατή μοιρασιά, ο πρώτος αδερφός θα εργαστεί έξι μέρες και θα εισπράξει κέρδος \(1+1+8+1+1+3=15\), ο δεύτερος θα εργαστεί δύο μέρες και θα εισπράξει κέρδος \(4+9=13\), και ο τρίτος θα εργαστεί τις υπόλοιπες δύο μέρες και θα εισπράξει κέρδος \(5+2=7\). Ο πιο ευνοημένος θα είναι τώρα ο πρώτος.
Μέγιστος χρόνος: \(1\) sec.