38ος ΠΔΠ Α' Φάση
Οι φούρνοι του Τάκη (ovens)
Άλλη μία μέρα σκληρής δουλειάς έφτασε στο τέλος της και ήρθε η ώρα η πιτσαρία να κλείσει. Υπάρχει όμως ένα πρόβλημα! Σήμερα ο βοηθός του Τάκη πήρε ρεπό και ο Τάκης δεν ξέρει πώς να κλείνει τους φούρνους του μόνος του.
Συγκεκριμένα, στην πιτσαρία υπάρχουν \(N\) φούρνοι, αριθμημένοι από \(1\) έως \(N\), και αντίστοιχα \(N\) διακόπτες. Ορισμένοι από τους φούρνους είναι αρχικά αναμμένοι, ενώ οι υπόλοιποι είναι αρχικά σβηστοί. Δηλώνουμε με \(a_i\) την αρχική κατάσταση του \(i\)-οστού φούρνου: \(a_i = 1\) αν είναι αναμμένος και \(a_i = 0\) αν είναι σβηστός.
Οι διακόπτες της πιτσαρίας λειτουργούν με έναν ιδιαίτερο τρόπο: αν χρησιμοποιήσουμε τον \(i\)-οστό διακόπτη αντιστρέφεται η κατάσταση του \(i\)-οστού και των επόμενων \(k_i\) φούρνων (όπου το \(k_i\) είναι ο “χαρακτηριστικός αριθμός” του \(i\)-οστού διακόπτη), δηλαδή σβήνονται όσοι από αυτούς τους φούρνους είναι αναμμένοι και ανάβουν όσοι είναι σβηστοί.
Ο Τάκης πρέπει να σβήσει όλους τους φούρνους, αλλά επειδή βιάζεται θέλει να το κάνει όσο πιο σύντομα γίνεται. Ποιο είναι το ελάχιστο δυνατό πλήθος από διακόπτες που χρειάζεται να χρησιμοποιήσει για να το πετύχει;
Δεδομένα εισόδου (stdin)
Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό \(N\): το πλήθος των φούρνων και των διακοπτών της πιτσαρίας. Η δεύτερη γραμμή περιέχει \(N\) ακέραιους αριθμούς \(a_1, a_2, \ldots, a_N\): την αρχική κατάσταση των φούρνων, όπου το \(1\) συμβολίζει αναμμένο φούρνο και το \(0\) συμβολίζει σβηστό φούρνο. Η τρίτη γραμμή περιέχει \(N\) ακέραιους αριθμούς \(k_1, k_2, \ldots, k_N\): τους χαρακτηριστικούς αριθμούς των διακοπτών.
Δεδομένα εξόδου (stdout)
Πρέπει να περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: το ελάχιστο πλήθος από διακόπτες που χρειάζεται να χρησιμοποιήσει ο Τάκης για να σβήσει όλους τους φούρνους του.
Παράδειγμα εισόδου-εξόδου
| stdin | stdout |
|---|---|
| 6 1 0 0 1 1 0 3 2 3 1 1 0 |
3 |
Εξήγηση παραδείγματος: Ο Τάκης μπορεί να σβήσει όλους τους φούρνους χρησιμοποιώντας 3 διακόπτες, ως εξής:
- Χρησιμοποιεί τον 4ο διακόπτη, που αντιστρέφει την κατάσταση του 4ου και του επόμενου ενός φούρνου. Η κατάσταση των φούρνων γίνεται [1, 0, 0, 0, 0, 0].
- Χρησιμοποιεί τον 2ο διακόπτη, που αντιστρέφει την κατάσταση του 2ου και των επόμενων δύο φούρνων. Η κατάσταση των φούρνων γίνεται [1, 1, 1, 1, 0, 0].
- Χρησιμοποιεί τον 1ο διακόπτη, που αντιστρέφει την κατάσταση του 1ου και των επόμενων τριών φούρνων. Η κατάσταση των φούρνων γίνεται [0, 0, 0, 0, 0, 0]. Επιπλέον, μπορεί να αποδειχθεί ότι ο Τάκης δεν μπορεί να σβήσει όλους τους φούρνους χρησιμοποιώντας λιγότερους από 3 διακόπτες. Επομένως, η απάντηση είναι 3.
Περιορισμοί
- \(1 \leq N \leq 200.000\),
- \(0 \leq a_i \leq 1\),
- \(0 \leq k_i \leq N−i\).
Υποπροβλήματα
- (11 βαθμοί) \(k_i = 0\), για κάθε \(i\) (όπου \(1 \leq i \leq N\))
- (17 βαθμοί) \(a_i = 1\), για κάθε \(i\) (όπου \(1 \leq i \leq N\))
- (21 βαθμοί) \(k_i \leq 10\), για κάθε i (όπου \(1 \leq i \leq N\))
- (24 βαθμοί) \(k_i = N−i\), για κάθε i (όπου \(1 \leq i \leq N\))
- (27 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί
Παρατηρήσεις
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(64\) MB.