33ος ΠΔΠ Γ’ Φάση
Ο πόλεμος των τσιφλικάδων (landfight)
Δύο μεγαλογαιοκτήμονες (τσιφλικάδες) είναι η αιτία μεγάλου πονοκεφάλου για το βασιλιά. Τσακώνονται μεταξύ τους για να αποκτήσουν περισσότερα χωράφια και η ιστορία αυτή δε θα έχει καλή έκβαση. Ο βασιλιάς αναλαμβάνει να βρει λύση στη διαμάχη τους και ζητά τη βοήθεια σας.
Στο δρόμο που ενώνει τα δύο τσιφλίκια υπάρχουν N χωράφια. Γνωρίζουμε τα οικονομικά στοιχεία κάθε χωραφιού και τα αναπαριστούμε με ακέραιους αριθμούς x1,x2,…xN. Μερικά χωράφια βγάζουν κέρδος, οπότε xi>0, άλλα έχουν ζημιά, οπότε xi<0 και κάποια δεν έχουν ούτε κέρδος ούτε ζημιά, οπότε xi=0 . Οι τσιφλικάδες προφανώς προτιμούν να έχουν στην κατοχή τους χωράφια που βγάζουν κέρδος, παρά χωράφια με ζημιά.
Ο βασιλιάς θέλει να δώσει στον ένα τσιφλικά τα L χωράφια που είναι κοντινότερα στο τσιφλίκι του, ξεκινώντας δηλαδή από το ένα άκρο του δρόμου και στον άλλο τσιφλικά τα R χωράφια που είναι κοντινότερα στο δικό του τσιφλίκι, ξεκινώντας δηλαδή από το άλλο άκρο του δρόμου. Φυσικά οι τιμές των L και R θα πρέπει να είναι μη αρνητικές και τέτοιες ώστε L+R≤N . Ο βασιλιάς θέλει να μην αδικήσει κανέναν τσιφλικά, επομένως το άθροισμα των xi των L χωραφιών που δίνει στον έναν θα πρέπει να ισούται με το άθροισμα των xi των R χωραφιών που δίνει στον άλλον. Επίσης θέλει να αφήσει όσο γίνεται λιγότερα χωράφια αδιάθετα.
Ποια είναι η ελάχιστη δυνατή τιμή του N−(L+R) που μπορεί να επιτευχθεί;
Πρόβλημα:
Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του IOI (PASCAL, C, C++, Java) το οποίο θα διαβάζει την τιμή του N και την ακολουθία των αριθμών xi και θα εκτυπώνει την απάντηση στο παρακάτω ερώτημα.
Αρχεία Εισόδου:
Τα αρχείο εισόδου με όνομα landfight.in είναι αρχείο κειμένου με την εξής δομή: Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό N : το πλήθος των χωραφιών. Η επόμενη γραμμή περιέχει N ακέραιους αριθμούς xi , χωρισμένους ανά δύο με ένα κενό διάστημα: τα οικονομικά στοιχεία των χωραφιών.
Αρχεία Εξόδου:
Το αρχείο εξόδου με όνομα landfight.out είναι αρχείο κειμένου που περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: την απάντηση στο παραπάνω ερώτημα.
Παραδείγματα Αρχείων Εισόδου – Εξόδου:
1o
| landfight.in | landfight.out |
|---|---|
| 7 3 2 5 7 1 6 4 |
2 |
Εξήγηση: Μπορούμε να δώσουμε L=3
“>L=3 χωράφια στον αριστερό τσιφλικά, με άθροισμα 3+2+5=10
“>3+2+5=10 και R=2
“>R=2 χωράφια στον δεξιό τσιφλικά, πάλι με άθροισμα 6+4=10
“>6+4=10. Έτσι μένουν αδιάθετα δύο χωράφια.
2o
| landfight.in | landfight.out |
|---|---|
| 10 5 -2 3 -7 -4 -1 3 -5 6 0 |
0 |
Εξήγηση: Μπορούμε να δώσουμε L=4
“>L=4 χωράφια στον αριστερό τσιφλικά, με άθροισμα 5−2+3−7=−1
“>5−2+3−7=−1 και R=6
“>R=6 χωράφια στον δεξιό τσιφλικά, πάλι με άθροισμα −4−1+3−5+6+0=−1
“>−4−1+3−5+6+0=−1. Έτσι δε μένει αδιάθετο κανένα χωράφι.
3o
| landfight.in | landfight.out |
|---|---|
| 5 1 2 3 4 5 |
5 |
Εξήγηση: Δεν υπάρχει κανένας τρόπος να δώσουμε L χωράφια στον έναν και R χωράφια στον άλλο, έτσι ώστε τα αθροίσματα των xi να είναι ίσα. Επομένως και τα 5 χωράφια θα μείνουν αδιάθετα.
Περιορισμοί:
1≤N≤1.000.000 ,
Το άθροισμα των απολύτων τιμών όλων των xi δε θα υπερβαίνει το 10^9
Για περιπτώσεις ελέγχου συνολικής αξίας 20%, θα είναι 1≤N≤1.000
Για περιπτώσεις ελέγχου συνολικής αξίας 50%, θα είναι 1≤N≤30.000
Για περιπτώσεις ελέγχου συνολικής αξίας 70%, θα είναι xi>0
Μορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με έναν χαρακτήρα newline.
Μέγιστος χρόνος εκτέλεσης: 1 sec.
Μέγιστη διαθέσιμη μνήμη: 64 MB.
Computer Science teacher
