38ος ΠΔΠ Α' Φάση
Χαμένα κουτιά (missing)

Μετά από μια πρόσφατη παραγγελία, ο Τάκης έχει στην αποθήκη του \(N\) σφραγισμένα κουτιά σε σειρά. Κάθε κουτί περιέχει (πέραν από κονσέρβες με ανανά) ένα χαρτί με έναν αριθμό από το \(1\) έως και το \(N\). Αρχικά, ο αριθμός στο χαρτί του πρώτου κουτιού είναι το \(1\), του δεύτερου κουτιού είναι το \(2\) και ούτω καθεξής.

Ο Γιάννης αποφάσισε να κάνει μια πλάκα στον Τάκη. Πήρε κάποια από τα κουτιά, έστω \(K\) κουτιά, και τα μετακίνησε στη δική του αποθήκη. Έπειτα, τακτοποίησε τα υπόλοιπα \(M\) κουτιά που έμειναν στην αποθήκη του Τάκη (προφανώς \(K+M=N\)), έτσι ώστε να μην φαίνεται με το μάτι ποια κουτιά λείπουν.

Μόλις ο Τάκης επέστρεψε στην αποθήκη του, αμέσως κατάλαβε ότι κάτι πήγαινε στραβά. Γνωρίζοντας καλά τον Γιάννη, είναι σίγουρος, και μπορείτε να είστε και εσείς, ότι δεν άλλαξε τη σχετική σειρά των κουτιών που άφησε στην αποθήκη και δεν πήρε το \(N\)-οστό κουτί, επειδή ήταν πολύ πιο βαρύ από τα υπόλοιπα.

Με βάση αυτές τις υποθέσεις και τη βοήθειά σας, θέλει να καταλάβει ποια κουτιά λείπουν από την αποθήκη του. Για αυτόν τον σκοπό, μπορείτε να ζητήσετε από τον Τάκη να ανοίξει οποιοδήποτε κουτί, να σας πει τον αριθμό που περιέχει και να το ξανασφραγίσει. Προκειμένου να διατηρήσει τα κουτιά σε όσο γίνεται καλύτερη κατάσταση, ο Τάκης είναι διατεθειμένος να το κάνει συνολικά το πολύ \(Q\) φορές.

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

Στην αρχή της εκτέλεσης του προγράμματός σας πρέπει να διαβάσετε από την τυπική είσοδο (stdin) τον ακέραιο αριθμό \(M\): το πλήθος των κουτιών που έμειναν στην αποθήκη του Τάκη.

Στη συνέχεια, μπορείτε να κάνετε το πολύ \(Q\) ερωτήματα και σε καθένα να ζητήσετε από τον Τάκη να σας πει τον αριθμό ενός κουτιού. Για να κάνετε ένα ερώτημα, πρέπει να εκτυπώσετε στην τυπική έξοδο (stdout) μία γραμμή που να περιέχει ένα ερωτηματικό (τον χαρακτήρα “?”), ένα κενό διάστημα και έναν ακέραιο αριθμό: τη θέση του κουτιού. Οι θέσεις είναι αριθμημένες από το \(1\) έως το \(M\). Στη συνέχεια, πρέπει να διαβάσετε από την τυπική είσοδο (stdin) τον αριθμό που είδε ο Τάκης μέσα στο κουτί.

Αν τυπώσετε κάποιο μη έγκυρο ερώτημα ή ξεπεράσετε το όριο των Q ερωτημάτων, στην τυπική είσοδο, αντί για απάντηση, θα λάβετε τον αριθμό \(−1\) και θα πρέπει να τερματίσετε το πρόγραμμά σας άμεσα. Διαφορετικά υπάρχει περίπτωση το σύστημα να εμφανίσει λάθος ένδειξη αποτυχίας, π.χ. Χρονική Υπέρβαση Ορίου.

Όταν έχετε βρει τους αριθμούς των κουτιών που λείπουν, πρέπει να εκτυπώσετε στην τυπική έξοδο (stdout) μία γραμμή που να περιέχει ένα θαυμαστικό (τον χαρακτήρα “!”) ακολουθούμενο από ένα κενό διάστημα, τον αριθμό \(K\) και τους \(K\) ζητούμενους αριθμούς σε αύξουσα

σειρά. Προσέξτε ότι η απάντηση δεν προσμετράται ως ερώτημα. Στο τέλος κάθε εκτύπωσης, είτε πρόκειται για ερώτημα είτε για την απάντηση, θα πρέπει να αδειάζετε τον buffer της τυπικής εξόδου χρησιμοποιώντας την κατάλληλη από τις παρακάτω εντολές:

fflush(stdout);
std::cout.flush(); 
std::cout << std::flush;

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

stdin	stdout
3 4 3	? 2 ? 1 ! 3 1 2 5

Εξήγηση: Ας υποθέσουμε ότι τα τρία κουτιά που άφησε ο Γιάννης στον Τάκη έχουν τους αριθμούς [3, 4, 6] (αυτό δεν το γνωρίζει ακόμα η λύση μας). Ζητάμε από τον Τάκη να ανοίξει το δεύτερο κουτί, αυτός μας απαντάει ότι περιέχει τον αριθμό 4 και το ξανασφραγίζει. Έπειτα, του υποδεικνύουμε το πρώτο κουτί, μας ενημερώνει ότι περιέχει τον αριθμό 3 και το ξανασφραγίζει. Σε αυτό το σημείο, θεωρούμε ότι βρήκαμε ότι λείπουν τρεις αριθμοί και συγκεκριμένα οι 1, 2 και 5. Προσέξτε ότι με βάση αυτά τα ερωτήματα δεν θα μπορούσαμε να είμαστε σίγουροι για την απάντηση και απλά την μαντέψαμε.

Περιορισμοί

\(1 \leq M < N \leq 5.000\),
\(0 < N−M \leq 50\),
Ο βαθμολογητής δεν είναι προσαρμοστικός (adaptive).

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

(13 βαθμοί) \(Q = 5.000\).
(29 βαθμοί) \(Q = 420\), \(N−M = 1\)
(18 βαθμοί) \(Q = 420\), οι αριθμοί των κουτιών που λείπουν από την αποθήκη του Τάκη σχηματίζουν συνεχές διάστημα
(17 βαθμοί) \(Q = 660\)
(23 βαθμοί) \(Q = 420\)

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