35ος ΠΔΠ Καμπ (κοινά)
ODDSUM (oddsum)
Πρόβλημα:
Δίνεται ένας πίνακας αποτελούμενος από \(N\) ακέραιους αριθμούς: \(A_1, A_2, \ldots, A_N\).
Μπορείτε να επιλέξετε
όσους από αυτούς τους αριθμούς θέλετε. Το ζητούμενο είναι το άθροισμα αυτών που θα επιλέξετε να είναι
περιττός αριθμός και να είναι το μέγιστο δυνατό.
Αρχεία εισόδου (oddsum.in):
Στην πρώτη γραμμή της εισόδου θα υπάρχει ένας θετικός ακέραιος \(T\), το πλήθος των ερωτημάτων. Σε καθένα από τα επόμενα \(T\) ερωτήματα, θα υπάρχει στην πρώτη γραμμή ένας φυσικός αριθμός \(N\): το πλήθος των στοιχείων του πίνακα. Η δεύτερη γραμμή θα περιέχει ακριβώς \(N\) ακέραιους ακεραίους \(A_1, A_2, \ldots, A_N\), χωρισμένους ανά δύο με ένα κενό διάστημα.
Αρχεία εξόδου (oddsum.out):
Η έξοδος θα πρέπει να περιέχει \(T\) γραμμές. Κάθε γραμμή θα περιέχει έναν ακέραιο αριθμό, που δηλώνει το μέγιστο δυνατό περιττό άθροισμα κάποιων επιλεγμένων αριθμών του αρχικού πίνακα, για το αντίστοιχο ερώτημα. Αν καμία επιλογή αριθμών δεν μπορεί να δώσει περιττό άθροισμα, τότε η γραμμή πρέπει να περιέχει τη λέξη “IMPOSSIBLE”.
Παράδειγμα αρχείων εισόδου - εξόδου:
| oddsum.in | oddsum.out |
|---|---|
| 3 4 -2 2 -3 1 3 2 -5 -3 5 2 4 6 8 4 |
3 -1 IMPOSSIBLE |
Εξήγηση παραδείγματος: Το παράδειγμα έχει τρία ερωτήματα.
Στο πρώτο ερώτημα, μπορούμε να επιλέξουμε τους αριθμούς \(2\) και \(1\), με άθροισμα \(3\).
Στο δεύτερο ερώτημα, το καλύτερο που μπορούμε να κάνουμε είναι να επιλέξουμε τους αριθμούς \(2\) και \(−3\), με άθροισμα \(−1\).
Τέλος, στο τρίτο ερώτημα, καμία επιλογή αριθμών δεν οδηγεί σε άθροισμα που να είναι περιττός αριθμός.
Περιορισμοί:
- \(1 \le T \le 10\).
- \(1 \le N \le 1.000.000\) και το άθροισμα των \(N\) όλων των ερωτημάτων δε θα υπερβαίνει το \(2.000.000\).
- Η απόλυτη τιμή του αθροίσματος οποιουδήποτε υποσυνόλου των αριθμών του πίνακα \(A\) δε θα υπερβαίνει το \(1.000.000.000\).
Sybtasks:
- Για περιπτώσεις ελέγχου συνολικής αξίας \(20\%\), θα είναι \(N \le 20\).
- Για περιπτώσεις ελέγχου συνολικής αξίας \(50\%\), θα είναι \(N \le 1.000\).
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(64\) MB.