Ψάχνοντας τους ανταγωνιστές

Η πόλη στην οποία μένει ο Τάκης αποτελείται από ~N~ σπίτια, χτισμένα κατά μήκος μιας ευθείας γραμμής και αριθμημένα από το ~1~ έως και το ~N~, από τα αριστερά προς τα δεξιά. Δύο διαδοχικά σπίτια απέχουν μεταξύ τους ~1~ μονάδα απόστασης.

Στην ίδια πόλη, στα σπίτια ~A~ και ~B~, όπου ~A < B~, μένουν δύο ανταγωνιστές του Τάκη. Τις τοποθεσίες των ~A~ και ~B~ δεν τις γνωρίζει ο Τάκης, τις γνωρίζει όμως ο φίλος του ο Γιάννης.

Ο Γιάννης δεν θέλει ο φίλος του να μπλέκεται σε καυγάδες, αλλά έχει βαρεθεί την υπερβολική ησυχία της πόλης του. Για αυτό θέλει να μαρτυρήσει στον Τάκη τις κρυφές τοποθεσίες με... έμμεσο τρόπο. Ο Τάκης μπορεί να υποδείξει στον Γιάννη ένα σπίτι ~X~ και αυτός θα του απαντήσει με το άθροισμα των αποστάσεων του ~X~ από τα σπίτια ~A~ και ~B~, δηλαδή το ~|X - A| + |X - B|~. Ο Τάκης δεν έχει χρόνο για χάσιμο. Θέλει να βρει τα σπίτια των ανταγωνιστών του κάνοντας προς τον Γιάννη το πολύ ~Q~ ερωτήματα αυτού του είδους.

Πριν ο Τάκης αρχίσει να ρωτάει, ο Γιάννης του ανακοινώνει τον αριθμό των σπιτιών, δηλαδή το ~N~. Επίσης, ανάλογα με τα κέφια του, ο Γιάννης μπορεί να του αποκαλύψει και την απόσταση ~D~ μεταξύ των σπιτιών ~A~ και ~B~ (που προφανώς ισούται με ~B - A~), μπορεί όμως και να μη θέλει να του την αποκαλύψει.

Περιέργως, ο Τάκης κατάφερε να λύσει το πρόβλημα. Τώρα είναι η σειρά σας! Μπείτε στην θέση του και βρείτε τα σπίτια ~A~ και ~B~, χωρίς να ξεπεράσετε το όριο των ~Q~ ερωτημάτων ανά στιγμιότυπο.

Πρόβλημα

Το πρόβλημα αυτό είναι διαδραστικό (interactive). Αν δεν έχετε ξανασυναντήσει τέτοιου είδους πρόβλημα, συμβουλευτείτε τον οδηγό στην ιστοσελίδα του ΠΔΠ (http://www.pdp.gr/). Από την ίδια ιστοσελίδα μπορείτε επίσης να κατεβάσετε το συμπιεσμένο αρχείο grader.zip που περιέχει ένα πρότυπο πρόγραμμα για να σας βοηθήσει να καταλάβετε το πώς λειτουργεί η αλληλεπίδραση, καθώς και έναν υποδειγματικό βαθμολογητή, μαζί με εντολές για να κάνετε compile και να τρέξετε τον κώδικά σας στον δικό σας υπολογιστή.

Αλληλεπίδραση:

Γράψτε ένα πρόγραμμα με το οποίο ο Τάκης θα αλληλεπιδρά με τον Γιάννη και θα προσπαθεί να λύσει ένα ή περισσότερα στιγμιότυπα του παραπάνω προβλήματος, ανεξάρτητα μεταξύ τους, με ενδεχομένως διαφορετικά ~N~, ~A~, ~B~, αλλά με το ίδιο ~Q~. Ο Γιάννης είτε θα αποκαλύπτει την απόσταση ~D~ των δύο σπιτιών σε όλα τα στιγμιότυπα του προβλήματος, είτε δε θα την αποκαλύπτει σε κανένα.

Είναι απαραίτητο να συμπεριλάβετε στον κώδικα σας τη γραμμή:

• #include "findinglib.h" (σε C++ ή C)
• uses findinglib; (σε Pascal)
• findinglib grader = new findinglib(); (σε Java)

Με αυτόν τον τρόπο αποκτάτε πρόσβαση στις παρακάτω συναρτήσεις, μέσω των οποίων μπορείτε να αλληλεπιδράσετε με τον Γιάννη:

• int getSubtask();
• int getN();
• int getD();
• int query(int X);
• bool answer(int A, int B);

Οι συναρτήσεις αυτές λειτουργούν ως εξής:

1. H συνάρτηση ~getSubtask()~ επιστρέφει τον αριθμό του υποπροβλήματος (βλ. παρακάτω), ο οποίος θα είναι ίδιος για όλα τα στιγμιότυπα μιας περίπτωσης ελέγχου.
2. Η συνάρτηση ~getN()~ επιστρέφει το πλήθος των σπιτιών, ~N~.
3. Η συνάρτηση ~getD()~ επιστρέφει την απόσταση των σπιτιών ~A~ και ~B~, αν ο Γιάννης θέλει να την αποκαλύψει, διαφορετικά ~-1~.
4. Η συνάρτηση ~query(X)~ επιστρέφει την απάντηση που δίνει ο Γιάννης όταν ο Τάκης του υποδεικνύει το σπίτι ~X~, δηλαδή το άθροισμα των αποστάσεων των ~A~, ~B~ από το σπίτι ~X~. Προφανώς, πρέπει να είναι ~1 \le X \le N~.
5. Η συνάρτηση ~answer(A,\;B)~ πρέπει να καλείται στο τέλος κάθε στιγμιοτύπου του προβλήματος, όταν ο Τάκης έχει εντοπίσει τα κρυφά σπίτια ~A~, ~B~. Πρέπει να είναι ~1 \le A < B \le N~. Η συνάρτηση επιστρέφει ~true~ αν θα υπάρξει και επόμενο ανεξάρτητο στιγμιότυπο του προβλήματος (με διαφορετικά ~N~, ~A~, ~B~), ή ~false~ αν το πρόγραμμά σας πρέπει να σταματήσει την εκτέλεσή του.

Για το συγκεκριμένο πρόβλημα δεν χρησιμοποιούνται αρχεία εισόδου και εξόδου. Η επικοινωνία του προγράμματος σας με τον grader γίνεται μόνο μέσω των παραπάνω συναρτήσεων.

Παράδειγμα αλληλεπίδρασης:

Το πρόγραμμά σας καλεί	Η συνάρτηση επιστρέφει	Περιγραφή
~getN()~	~5~	Υπάρχουν ~5~ σπίτια, αριθμημένα από ~1~ έως ~5~.
~getD()~	~2~	Ας υποθέσουμε ότι τα κρυφά σπίτια βρίσκονται στις θέσεις ~2~ και ~4~ (φυσικά αυτό δεν το γνωρίζει ακόμα το πρόγραμμά σας). Η απόσταση των κρυφών σπιτιών είναι ~2~ και ο Γιάννης αποφασίζει να την αποκαλύψει.
~query(2)~	~2~	Η συνολική απόσταση των δύο σπιτιών από τη θέση ~2~ είναι ~0 + 2 = 2~.
~query(3)~	~2~	Η συνολική απόσταση των δύο σπιτιών από τη θέση ~3~ είναι ~1 + 1 = 2~.
~answer(2,4)~	~true~	Ο Τάκης μαντεύει σωστά πού βρίσκονται τα δύο σπίτια. Θα ακολουθήσει κι άλλο στιγμιότυπο.
~getN()~	~8~	Στο νέο στιγμιότυπο, υπάρχουν ~8~ σπίτια.
~getD()~	~3~	Ας υποθέσουμε ότι τα κρυφά σπίτια βρίσκονται αυτή τη φορά στις θέσεις ~1~ και ~4~. Η απόσταση των κρυφών σπιτιών είναι ~3~ και ο Γιάννης πάλι την αποκαλύπτει.
~query(8)~	~11~	Η συνολική απόσταση των δύο σπιτιών από τη θέση ~8~ είναι ~7 + 4 = 11~.
~query(5)~	~5~	Η συνολική απόσταση των δύο σπιτιών από τη θέση ~5~ είναι ~4 + 1 = 5~.
~answer(1,4)~	~false~	Ο Τάκης πάλι μαντεύει σωστά πού βρίσκονται τα δύο σπίτια. Δεν θα ακολουθήσει άλλο στιγμιότυπο.

Περιορισμοί

• ~3 \le N \le 1000~
• Το άθροισμα των ~N~ σε όλα τα στιγμιότυπα μίας περίπτωσης ελέγχου δεν θα ξεπερνά το ~100.000~.
• ~1 \le A < B \le N~
• Αν παραβιάσετε το πρωτόκολλο επικοινωνίας, το πρόγραμμά σας θα τερματιστεί και θα θεωρηθεί ότι απέτυχε η περίπτωση ελέγχου. Ενδεικτικά και χάριν παραδείγματος, τα παρακάτω θεωρούνται παραβιάσεις του πρωτοκόλλου επικοινωνίας:

1. Κλήση της ~query~ ή της ~answer~ με παραμέτρους εκτός των ορίων που αναφέρονται.
2. Κλήση της ~query~ περισσότερες από ~Q~ φορές σε κάποιο στιγμιότυπο.
3. Κλήση της ~answer~ με λάθος τιμές των ~A~ και ~B~.
4. Κλήση οποιασδήποτε συνάρτησης αφότου η ~answer~ επιστρέψει ~false~.
5. Χρήση οποιασδήποτε εντολής εισόδου/εξόδου.

Υποπροβλήματα:

Στα τρία πρώτα υποπροβλήματα, ο Γιάννης θα αποκαλύπτει την απόσταση ~D~ των σπιτιών ~A~ και ~B~.

1. (4 βαθμοί) ~D = 1~, ~Q = 1000~
2. (6 βαθμοί) ~Q = 1000~
3. (20 βαθμοί) ~Q = 1~

Στα υπόλοιπα υποπροβλήματα, ο Γιάννης δε θα αποκαλύπτει την απόστασή τους.

1. (6 βαθμοί) ~Q = 1000~
2. (9 βαθμοί) ~Q = 37~
3. (12 βαθμοί) ~Q = 21~
4. (17 βαθμοί) ~Q = 11~
5. (26 βαθμοί) ~Q = 2~

Παρατηρήσεις:

• Μέγιστος χρόνος εκτέλεσης: ~1~ sec.
• Μέγιστη διαθέσιμη μνήμη: ~16~ MB.