37ος ΠΔΠ B' Φάση
Παιχνίδι συγχώνευσης (mergegame)

Προκειμένου να προσελκύσει νέους πελάτες, ο Τάκης δημιούργησε το παρακάτω παιχνίδι για έναν παίκτη, του οποίου οι νικητές λαμβάνουν κουπόνια για δωρεάν σκορδόψωμα.

Στον παίκτη δίνεται μια ακολουθία που αποτελείται από \(N\) ακέραιες δυνάμεις του \(2\). Ως ακέραια δύναμη του \(2\) ορίζουμε κάθε αριθμό της μορφής \(2^m\), με \(m\) μη αρνητικό ακέραιο. Το παιχνίδι τελειώνει όταν στην ακολουθία απομένει ακριβώς \(1\) στοιχείο. Σκοπός του παίκτη είναι να μεγιστοποιήσει το τελικό στοιχείο. Για να το πετύχει αυτό, έχει στην διάθεσή του δύο διαφορετικά είδη κινήσεων:

Κίνηση Διαγραφής: Να επιλέξει κάποιο στοιχείο της ακολουθίας και να το διαγράψει (π.χ. 1 8 4 \(\rightarrow\) 1 4).
Κίνηση Συγχώνευσης: Να επιλέξει δύο ίσα γειτονικά στοιχεία, δηλαδή που έχουν την ίδια τιμή και βρίσκονται σε διαδοχικές θέσεις, να τα διαγράψει και να τοποθετήσει το άθροισμά τους στην θέση τους (π.χ. 1 8 8 4 \(\rightarrow\) 1 16 4).

Διαβάζοντας τις εκφωνήσεις του ΠΔΠ πεινάσατε και χρειάζεστε επειγόντως ένα σκορδόψωμο. Βρείτε το μέγιστο δυνατό στοιχείο που μπορεί να απομείνει στο τέλος του παιχνιδιού αν παίξετε βέλτιστα, για να κερδίσετε και εσείς ένα κουπόνι (ή και όχι, δεν υποσχόμαστε τίποτα…).

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του ΠΔΠ (PASCAL, C, C++, Java) το οποίο θα διαβάζει τα δεδομένα εισόδου από το αρχείο mergegame.in και θα εκτυπώνει τα αποτελέσματα στο αρχείο mergegame.out.

Δεδομένα εισόδου (mergegame.in):

Η πρώτη γραμμή περιέχει τον αριθμό του υποπροβλήματος (βλ. παρακάτω). Η δεύτερη γραμμή περιέχει έναν ακέραιο αριθμό \(N\): το αρχικό πλήθος στοιχείων της ακολουθίας. Η τρίτη γραμμή αποτελείται από \(N\) ακέραιους αριθμούς \(e_1, e_2, \dots , e_N\), χωρισμένους ανά δύο με κενό διάστημα: τους εκθέτες των στοιχείων της ακολουθίας, όταν γραφτούν ως δύναμη με βάση το \(2\) (π.χ. αν το πρώτο στοιχείο είναι το \(32768\) (\(2^{15}\)), θα ισχύει \(e_1=15\)).

Δεδομένα εξόδου (mergegame.out):

Πρέπει να περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: τον εκθέτη, αν γραφτεί ως δύναμη με βάση το \(2\), του μέγιστου στοιχείου που είναι δυνατό να προκύψει στο τέλος του παιχνιδιού. Μπορεί να αποδειχθεί ότι το στοιχείο αυτό είναι ακέραια δύναμη του \(2\), άρα και ο ζητούμενος εκθέτης είναι ακέραιος αριθμός.

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

mergegame.in	mergegame.out
3 7 1 0 1 2 0 0 3	4

Εξήγηση: Μετατρέπουμε τους εκθέτες που δίνονται στις αντίστοιχες δυνάμεις και τώρα μπορούμε να χρησιμοποιήσουμε τις παρακάτω κινήσεις:

2 1 2 4 1 1 8 → 2 2 4 1 1 8
2 2 4 1 1 8 → 2 2 4 2 8
2 2 4 2 8 → 4 4 2 8
4 4 2 8 → 8 2 8
8 2 8 → 8 8
8 8 → 16

Μάλιστα, δεν υπάρχει τρόπος να δημιουργήσουμε στοιχείο μεγαλύτερο από το 16. Άρα, η απάντηση είναι το \(16=2^4\) και τυπώνουμε τον αριθμό 4, τον αντίστοιχο εκθέτη.

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

\(1\leq N \leq 100.000\).
\(0 \leq e_i \leq 1.000.000.000\).

Υποπροβλήματα:

(9 βαθμοί) \(e_1\leq e_2\leq \dots \leq e_N\), δηλαδή οι εκθέτες βρίσκονται σε αύξουσα σειρά
(11 βαθμοί) Για την επίτευξη της βέλτιστης απάντησης απαιτούνται είτε μόνο διαγραφές, είτε μόνο συγχωνεύσεις
(16 βαθμοί) \(N\leq 500\)
(19 βαθμοί) \(N\leq 10.000\) και ο μέγιστος εκθέτης δεν υπερβαίνει το \(5.000\)
(27 βαθμοί) \(N\leq 10.000\)
(18 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί

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