Δίκαιη Μοιρασιά

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

Πρόβλημα:

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

Είσοδος:

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

Έξοδος:

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

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

1ο

STDIN

8
7 5 1 3 8 9 11 8

STDOUT

0

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

2ο

STDIN

9
10 14 75 90 3 5 40 4 8

STDOUT

27

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

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

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