30ος ΠΔΠ B' Φάση Γυμνασίου
Τα κάλαντα (kalanta)

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

Πρόβλημα

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

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

Τα αρχεία εισόδου με όνομα kalanta.in είναι αρχεία κειμένου με την εξής δομή: Η πρώτη γραμμή έχει έναν ακέραιο αριθμό \(N\). Τον αριθμό των σπιτιών (\(1 \leq N \leq 1.000.000\)). Η δεύτερη γραμμή περιέχει \(N\) θετικούς ακέραιους αριθμούς \(x_i\), χωρισμένους μεταξύ τους με ένα κενό διάστημα. Κάθε αριθμός \(x_i\) (\(1 \leq x_i \leq 1.000\)) αντιστοιχεί στο ποσό των χρημάτων που θα πάρουν τα παιδιά από το \(i\)-οστό σπίτι.

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

Τα αρχεία εξόδου με όνομα kalanta.out είναι αρχεία κειμένου με την εξής δομή: Έχουν ακριβώς μία γραμμή που περιέχει ακριβώς έναν αριθμό: την ελάχιστη (κατ’ απόλυτο) τιμή της διαφοράς των συνολικών χρημάτων που μπορούν να πάρουν τα δύο παιδιά.

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

1^o

kalanta.in	kalanta.out
8 7 5 1 3 8 9 11 8	0

Παράδειγμα 1ο

Σε αυτό το παράδειγμα, ο Κόκκινος και η Πράσινη μπορούν να μοιράσουν τα σπίτια με τέτοιο τρόπο ώστε να πάρουν ακριβώς τα ίδια χρήματα (δηλαδή η ελάχιστη δυνατή τιμή της διαφοράς είναι μηδέν). Αυτό μπορεί να γίνει αν ο Κόκκινος επισκεφτεί τα σπίτια από το δεύτερο (\(5\)) μέχρι και το έκτο (\(9\)) και η Πράσινη τα υπόλοιπα. Τότε, και τα δύο παιδιά θα έχουν πάρει συνολικά \(26\)€.

2^o

kalanta.in	kalanta.out
9 10 14 75 90 3 5 40 4 8	27

Παράδειγμα 2ο

Σε αυτό το παράδειγμα, τα παιδιά δεν μπορούν να μοιράσουν τα σπίτια με τέτοιο τρόπο ώστε να πάρουν τα ίδια χρήματα συνολικά. Το καλύτερο που μπορούν να κάνουν είναι αυτό που φαίνεται στο παραπάνω σχήμα. Ο Κόκκινος θα επισκεφθεί τα σπίτια από το τέταρτο (\(90\)) μέχρι και το έβδομο (\(40\)) και θα πάρει συνολικά \(90+3+5+40=138\)€. Η Πράσινη θα επισκεφθεί τα υπόλοιπα σπίτια και θα πάρει \(4+8+10+14+75=111\)€. Η διαφορά τους είναι \(138-111=27\)€ και αυτή είναι η ελάχιστη δυνατή διαφορά.

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

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