37ος ΠΔΠ Γ' Φάση
Ο μετρητής του παππού (counter)
[ Μονάδες]
Σε ένα σύντομο διάλειμμα από την πιτσαρία του, ο Τάκης αποφάσισε να επισκεφτεί το γραφείο του παππού του και να θυμηθεί τις παλιές καλές στιγμές μαζί του. Μπαίνοντας στο γραφείο, παρατήρησε ένα μισάνοιχτο συρτάρι γεμάτο με χαρτιά. Πάνω πάνω στο συρτάρι, βρισκόταν ο ακόλουθος κώδικας:
όπου \(\leftarrow\) είναι ο τελεστής ανάθεσης (= σε C/C++/Java, := σε Pascal) και το \(\lfloor a/ b \rfloor\) συμβολίζει το πηλίκο της ακέραιας διαίρεσης των \(a\) και \(b\) (\(a/ b\) σε C/C++/Java, \(a \texttt{ div } b\) σε Pascal).
Ο κώδικας είναι γραμμένος σε μορφή ψευδοκώδικα, αλλά μπορείτε να τον βρείτε στο HelleniCO σε Pascal, C, C++ και Java. Είστε ελεύθεροι να τον χρησιμοποιήσετε στις λύσεις σας, δείτε όμως προσεκτικά τα σχόλια.
Ο Τάκης, όπως ελπίζουμε και εσείς, αναγνώρισε αμέσως την μορφή του. Πρόκειται για την πασίγνωστη “Δυαδική Αναζήτηση”. Αντί, όμως, να επιστρέφει το αν η τιμή \(x\) εμφανίζεται στον πίνακα, η συνάρτηση επιστρέφει την τιμή του μετρητή \(\mathit{counter}\) στο τέλος της εκτέλεσης.
Εκτός του κώδικα, ο Τάκης βρήκε στο συρτάρι μια ακολουθία \(A\) αποτελούμενη από \(N\) ακέραιους αριθμούς, ταξινομημένους σε γνησίως αύξουσα σειρά (\(A_i \lt A_{i+1}\), για κάθε \(i\), με \(1\le i\lt N\)). Αυτή είναι και η ακολουθία \(A\) που εμφανίζεται στον κώδικα.
Μη μπορώντας να καταλάβει το γιατί ο κώδικας του παππού του επιστρέφει τον μετρητή, στον Τάκη δημιουργήθηκαν \(Q\) απορίες της μορφής “Ποιο είναι το άθροισμα των τιμών των μετρητών που επιστρέφει η συνάρτηση, αν την καλέσω για κάθε τιμή από \(L\) έως και \(R\) ακριβώς μία φορά;”. Στο γραφείο δεν υπάρχει υπολογιστής και ο Τάκης πρέπει να γυρίσει γρήγορα στη δουλειά του, για αυτό και θα χρειαστεί την βοήθεια σας για να δώσει απάντηση στις απορίες του.
Πρόβλημα:
Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του ΠΔΠ (PASCAL, C, C++, Java) το οποίο θα διαβάζει τα δεδομένα εισόδου από το αρχείο counter.in και θα εκτυπώνει τα αποτελέσματα στο αρχείο counter.out.
Δεδομένα εισόδου (counter.in):
Η πρώτη γραμμή περιέχει τον αριθμό του υποπροβλήματος (βλ. παρακάτω). Η δεύτερη γραμμή περιέχει δύο ακέραιους αριθμούς \(N\) και \(Q\): το πλήθος των στοιχείων της ακολουθίας \(A\) και το πλήθος των αποριών του Τάκη. Η τρίτη γραμμή αποτελείται από \(N\) ακέραιους αριθμούς \(A_1, A_2, \ldots , A_N\): τις τιμές των στοιχείων της ακολουθίας \(A\). Ακολουθούν \(Q\) γραμμές, καθεμία από τις οποίες περιέχει \(2\) ακέραιους αριθμούς \(L_i\) και \(R_i\): τα άκρα του διαστήματος της \(i\)-οστής απορίας.
Δεδομένα εξόδου (counter.out):
Πρέπει να αποτελείται από \(Q\) γραμμές, καθεμία από τις οποίες να περιέχει ακριβώς έναν ακέραιο αριθμό: την απάντηση της \(i\)-οστής απορίας του Τάκη, δηλαδή το άθροισμα των μετρητών που επιστρέφει η συνάρτηση του παππού, αν κληθεί ακριβώς μία φορά για κάθε τιμή από \(L_i\) έως και \(R_i\) (χρησιμοποιώντας την ακολουθία \(A\) της εισόδου).
Παραδείγματα εισόδου - εξόδου:
| counter.in | counter.out |
|---|---|
| 6 6 3 6 8 9 10 12 15 12 12 5 9 10 11 |
2 11 6 |
Εξήγηση: Η ακολουθία που βρήκε ο Τάκης είναι η \(A = [6, 8, 9, 10, 12, 15]\). Η πρώτη απορία περιέχει μόνο την τιμή \(12\), η δεύτερη τις τιμές 5, 6, 7, 8 και 9 και η τρίτη τις τιμές 10 και 11. Όσον αφορά την πρώτη απορία, ο μετρητής που επιστρέφεται για την τιμή \(12\) είναι ίσος με \(2\), αφού:
- \(l=1, r=6 \rightarrow \mathit{counter}=1, m=3, A[3]=9\lt 12 \rightarrow\) Το \(l\) γίνεται \(4\).
- \(l=4, r=6 \rightarrow \mathit{counter}=2, m=5, A[5]=12 \rightarrow\) Επιστρέφει \(\mathit{counter}\).
Για την τρίτη απορία, οι μετρητές που επιστρέφονται για τις τιμές 10 και 11 είναι 3 και 3. Άρα, η απάντηση της τρίτης απορίας είναι \(3+3=6\).
Περιορισμοί:
- \(1\leq N\leq 200.000\).
- \(1\leq Q \leq 200.000\).
- \(-10^{12}\leq A_i \leq 10^{12}\).
- Η ακολουθία \(A\) είναι ταξινομημένη σε γνησίως αύξουσα σειρά.
- \(-10^{12}\leq L_i \leq R_i \leq 10^{12}\).
Υποπροβλήματα:
- (8 βαθμοί) \(L_i= R_i\), για κάθε \(i, (1\le i\le Q)\).
- (12 βαθμοί) Τα διαστήματα των αποριών περιέχουν μόνο τιμές που εμφανίζονται στον πίνακα \(A\), δηλαδή για κάθε \(i\) με \((1\le i\le Q)\) και για κάθε \(x\) με \((L_i\le x\le R_i)\), υπάρχει κάποιο \(j\) με \((1 \le j \le N)\) τέτοιο ώστε \(A_j = x\).
- (15 βαθμοί) \(A_{i+1}= A_i+1\), για κάθε \(i\) με \((1\le i\le N)\).
- (18 βαθμοί) \(N=2^K-1\), για κάποιον θετικό ακέραιο \(K\).
- (22 βαθμοί) \(Q=1\).
- (25 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί.
Παρατηρήσεις:
Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
Μέγιστος χρόνος εκτέλεσης: 1 sec.
Μέγιστη διαθέσιμη μνήμη: 64 MB.