26ος ΠΔΠ Γ' Φάση
Άθροισμα ζευγών (sumpair)
[30 Μονάδες]
Δίνεται μία ακολουθία \(N\) ακέραιων αριθμών. Θέλουμε να μπορούμε να απαντάμε στο ερώτημα «υπάρχει ζεύγος όρων της ακολουθίας με άθροισμά είναι ίσο με \(X\);» για οποιονδήποτε ακέραιο αριθμό \(X\).
Πρόβλημα
Nα γραφεί ένα πρόγραμμα σε μια από τις γλώσσες του ΙΟΙ το οποίο θα διαβάζει την ακολουθία των \(N\) αριθμών και στη συνέχεια θα απαντά σε μία σειρά τέτοιων ερωτημάτων, για διαφορετικές τιμές του \(X\). Αν η απάντηση είναι «ναι», τότε το πρόγραμμά σας πρέπει να τυπώνει τη λέξη «true», διαφορετικά τη λέξη «false».
Aρχεία εισόδου
Τα αρχεία εισόδου με όνομα sumpair.in είναι αρχεία κειμένου αποτελούμενα από τρεις γραμμές: Στην πρώτη γραμμή έχουν δύο ακέραιους χωρισμένους με ένα κενό διάστημα: το πλήθος \(N\) των αριθμών της ακολουθίας (\(1 \leq N \leq 1.000.000\)) και το πλήθος \(Q\) των ερωτημάτων (\(1 \leq Q \leq 1.000\)). Στη δεύτερη γραμμή έχουν \(N\) ακέραιους (η απόλυτη τιμή των οποίων δε θα υπερβαίνει το \(10^9\)), χωρισμένους ανά δύο με ένα κενό διάστημα: τους όρους της ακολουθίας. Στην τρίτη γραμμή έχουν \(Q\) ακέραιους χωρισμένους ανά δύο με ένα κενό διάστημα: τα ερωτήματα προς απάντηση.
Aρχεία εξόδου
Τα αρχεία εξόδου με όνομα sumpair.out είναι αρχεία κειμένου αποτελούμενα από \(Q\) γραμμές. Η \(i\)-οστή γραμμή περιέχει την απάντηση στο \(i\)-οστό ερώτημα: μία από τις λέξεις «true» ή «false».
Παράδειγμα αρχείων εισόδου - εξόδου
1o
| sumpair.in | sumpair.out | Εξήγηση |
|---|---|---|
| 12 5 2 42 5 -6 5 7 10 29 0 21 29 15 17 30 42 -4 58 |
true false true true true |
2+15 = 7+10 = 17 δεν προκύπτει 30 42+0 = 42 2+(-6) = -4 29+29 = 58 |
Μορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με ένα χαρακτήρα newline.
Μέγιστος χρόνος εκτέλεσης: \(2\) sec.
Μέγιστη διαθέσιμη μνήμη: \(16\) MB.