35ος ΠΔΠ Καμπ (κοινά)
SUMIJ (sumij)
Πρόβλημα:
Δίνεται ένας πίνακας αποτελούμενος από \(N\) ακέραιους αριθμούς: \(A_1, A_2, \ldots, A_N\). Ζητείται να βρεθούν δύο θέσεις \(i\) και \(j\) στον πίνακα (\(1 \le i \lt j \le N\)) τέτοιες ώστε \(A_i + A_{i+1} + \ldots + A_j = i + j\). Αν υπάρχουν περισσότερα ζεύγη \(i\) και \(j\) που να ικανοποιούν τα παραπάνω, ζητείται το ζεύγος που έχει τη μεγαλύτερη διαφορά \(j − i\). Αν υπάρχουν περισσότερα ζεύγη με ίση μέγιστη διαφορά, ζητείται αυτό που έχει τη μικρότερη τιμή του \(i\).
Αρχεία εισόδου (sumij.in):
Στην πρώτη γραμμή της εισόδου θα υπάρχει ένας θετικός ακέραιος \(T\), το πλήθος των ερωτημάτων.
Σε καθένα από τα επόμενα \(T\) ερωτήματα, θα υπάρχει στην πρώτη γραμμή ένας φυσικός αριθμός \(N\):
το πλήθος των στοιχείων του πίνακα.
Η δεύτερη γραμμή θα περιέχει ακριβώς \(N\) ακέραιους ακεραίους \(A_1, A_2, \ldots, A_N\),
χωρισμένους ανά δύο με ένα κενό διάστημα.
Αρχεία εξόδου (sumij.out):
Η έξοδος θα πρέπει να περιέχει \(T\) γραμμές. Κάθε γραμμή θα περιέχει δύο αριθμούς χωρισμένους μεταξύ τους με ένα κενό διάστημα, που δηλώνουν το ζητούμενο ζεύγος θέσεων \(i\) και \(j\) για το αντίστοιχο ερώτημα. Αν δεν υπάρχει ζεύγος που να ικανοποιεί τους περιορισμούς της εκφώνησης, τότε η γραμμή πρέπει να περιέχει τη λέξη “IMPOSSIBLE”.
Παράδειγμα αρχείων εισόδου - εξόδου:
| sumij.in | sumij.out |
|---|---|
| 3 10 5 2 8 3 3 5 1 8 5 7 11 1 7 7 1 -4 8 9 7 9 4 5 6 1 2 -2 5 2 4 |
6 8 IMPOSSIBLE 2 5 |
Εξήγηση παραδείγματος: Το παράδειγμα έχει τρία ερωτήματα.
Στο πρώτο ερώτημα, το μοναδικό τμήμα του πίνακα που έχει τη ζητούμενη ιδιότητα είναι αυτό μεταξύ των
θέσεων \(i = 6\) και \(j = 8\), το οποίο έχει άθροισμα \(5 + 1 + 8 = 14 = i + j\).
Στο δεύτερο ερώτημα, κανένα τμήμα
του πίνακα δεν έχει τη ζητούμενη ιδιότητα.
Τέλος, στο τρίτο ερώτημα, υπάρχουν τρία τμήματα του πίνακα
που έχουν τη ζητούμενη ιδιότητα:
- για \(i = 1\) και \(j = 2\) είναι \(1 + 2 = 3 = i + j\),
- για \(i = 2\) και \(j = 5\) είναι \(2 − 2 + 5 + 2 = 7 = i + j\) και
- για \(i = 3\) και \(j = 6\) είναι \(−2 + 5 + 2 + 4 = 9 = i + j\). Μεταξύ των τριών, το πρώτο έχει \(j − i = 1\) ενώ τα άλλα δύο έχουν \(j − i = 2\). Μεταξύ των δύο που έχουν τη μέγιστη τιμή \(j − i\), η ζητούμενη απάντηση είναι αυτή που έχει τη μικρότερη τιμή του \(i\), δηλαδή το \(i = 2, j = 5\).
Περιορισμοί:
- \(1 \le T \le 5\).
- \(1 \le N \le 1.000.000\) και το άθροισμα των \(N\) όλων των ερωτημάτων δε θα υπερβαίνει το \(2.000.000\).
- \(−1.000 \le A_i \le 1.000\) για κάθε \(i\).
Subtasks:
- Για περιπτώσεις ελέγχου συνολικής αξίας \(30\%\), θα είναι \(N \le 1.000\).
- Για περιπτώσεις ελέγχου συνολικής αξίας \(60\%\), θα είναι \(N \le 10.000\).
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(64\) MB.