38ος ΠΔΠ B' Φάση
Παιχνίδι συγχώνευσης 2 (mergegame2)
Το παιχνίδι συγχώνευσης που είχε δημιουργήσει ο Τάκης στην περσινή Β’ Φάση προσέλκυσε πολύ κόσμο στην πιτσαρία του, αλλά αποδείχθηκε ιδιαίτερα δύσκολο για τους νεαρούς επισκέπτες του. Έτσι, ο Τάκης αποφάσισε να δημιουργήσει ένα ευκολότερο παιχνίδι. (Σημείωση: Δε χρειάζεται να διαβάσετε ή να λύσετε το περσινό θέμα για να λύσετε αυτό, είναι ανεξάρτητα μεταξύ τους.)
Στον παίκτη δίνεται ένας πίνακας που αποτελείται από \(N\) θετικούς ακέραιους αριθμούς, \(A_1, A_2, \ldots , A_N\). Σε μία κίνηση, ο παίκτης πρέπει να επιλέξει ακριβώς δύο στοιχεία του πίνακα, έστω \(A_x\) και \(A_y\), με \(x \neq y\), τα οποία να είναι είτε και τα δύο άρτια, είτε και τα δύο περιττά. Στη συνέχεια, τα διαγράφει από τον πίνακα και:
- Αν τα στοιχεία ήταν περιττά, τοποθετεί οπουδήποτε στον πίνακα τον αριθμό \(A_x+A_y+7\), πληρώνοντας κόστος \(A_x+A_y+7\).
- Αν τα στοιχεία ήταν άρτια, τοποθετεί οπουδήποτε στον πίνακα τον αριθμό \(A_x+A_y+8\), πληρώνοντας κόστος \(A_x+A_y+8\).
Σκοπός του παίκτη είναι να καταλήξει να έχει ακριβώς ένα στοιχείο, πληρώνοντας το ελάχιστο δυνατό συνολικό κόστος. Προκειμένου να μην μπορεί πάντοτε ο παίκτης να κερδίσει, ο Τάκης έχει συμπεριλάβει περιπτώσεις όπου το να καταλήξει κανείς σε ένα στοιχείο είναι αδύνατο. Τώρα είναι σειρά σας να παίξετε το παιχνίδι.
Δεδομένα εισόδου (stdin)
Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό \(N\): το αρχικό μέγεθος του πίνακα. Η δεύτερη γραμμή περιέχει \(N\) ακέραιους αριθμούς \(A_1, A_2, \ldots , A_N\): τα αρχικά στοιχεία του πίνακα.
Δεδομένα εξόδου (stdout)
Πρέπει να περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: το ελάχιστο συνολικό κόστος που χρειάζεται να πληρώσει ένας παίκτης για να καταλήξει με ακριβώς ένα στοιχείο, ή \(−1\) αν αυτό δεν είναι εφικτό.
Παραδείγματα εισόδου-εξόδου
| stdin | stdout |
|---|---|
| 3 2 8 6 |
48 |
Εξήγηση παραδείγματος: Ο Τάκης μπορεί να πετύχει συνολικό κόστος \(48\), που αποδεικνύεται ότι είναι το βέλτιστο δυνατό, με τις εξής κινήσεις:
- \(\underline{2}\ 8\ \underline{6} \to 8\ \underline{16}\) (Κόστος: \(2+6+8=16\))
- \(\underline{8}\ \underline{16} \to 32\) (Κόστος: \(8+16+8=32\))
| stdin | stdout |
|---|---|
| 2 15 62 |
-1 |
Περιορισμοί
- \(1 \leq N \leq 200.000\).
- \(1 \leq A_i \leq 10^9\).
Υποπροβλήματα
- (12 βαθμοί) \(N = 2\).
- (21 βαθμοί) Όλα τα στοιχεία του \(A\) είναι ίσα μεταξύ τους και άρτια.
- (20 βαθμοί) \(A_i = 2^{i-1}\), για κάθε \(i\) (όπου \(1 \leq i \leq N\)).
- (22 βαθμοί) \(N \leq 5.000\).
- (25 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί.
Παρατηρήσεις
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(64\) MB.