Guessing Game

Στην παλιά πόλη του Lund, υπάρχει ένας δρόμος με ~N~ σπίτια στη σειρά, με δείκτες ~0~ έως ~N - 1~. Η Ελένη ζει σε ένα από αυτά τα σπίτια και οι φίλες της, Αγγελική και Μαριλένα, θέλουν να βρουν ποιο από αυτά είναι. Αντί απλά να πει στους φίλες της πού βρίσκεται το σπίτι της, η Ελένη αποφασίζει να παίξει ένα παιχνίδι μαζί τους. Πριν ξεκινήσει το παιχνίδι, η Αγγελική και η Μαριλένα γνωρίζουν μόνο τον αριθμό των σπιτιών στο δρόμο. Σε αυτό το σημείο, η Αγγελική και η Μαριλένα μπορούν να επιλέξουν έναν θετικό ακέραιο ~K~ και να συμφωνήσουν σε μια στρατηγική. Οποιαδήποτε επικοινωνία στη συνέχεια απαγορεύεται.

Το ίδιο το παιχνίδι αποτελείται από δύο φάσεις. Στην πρώτη φάση, η Ελένη επιλέγει τη σειρά με την οποία θα επισκεφτεί τα σπίτια, έτσι ώστε το δικό της σπίτι να είναι το τελευταίο που θα επισκεφθεί. Στη συνέχεια οδηγεί την Αγγελική στα σπίτια, ένα προς ένα με αυτή τη σειρά, χωρίς να πει στην Αγγελική τη σειρά εκ των προτέρων. Για κάθε σπίτι που δεν είναι το σπίτι της Ελένης, η Αγγελική έχει τη δυνατότητα να γράψει με κιμωλία έναν ακέραιο αριθμό μεταξύ ~1~ και ~K~ στην εξώπορτα του σπιτιού. Για το τελευταίο σπίτι που επισκέπτονται, το σπίτι της Ελένης, η ίδια Ελένη γράφει στην πόρτα έναν ακέραιο αριθμό μεταξύ ~1~ και ~K~.

Στη δεύτερη φάση του παιχνιδιού, η Μαριλένα περπατάει κατά μήκος του δρόμου από το σπίτι ~0~ προς το σπίτι ~N - 1~ και διαβάζει όλους τους αριθμούς που είναι γραμμένοι στις πόρτες από την Αγγελική και την Ελένη. Τώρα θέλει να μαντέψει σε ποιο σπίτι μένει η Ελένη. Έχει δύο ευκαιρίες να μαντέψει σωστά και αν τα καταφέρει κερδίζει μαζί με την Αγγελική το παιχνίδι. Διαφορετικά, κερδίζει το παιχνίδι η Ελένη.

Μπορείτε να σχεδιάσετε μια στρατηγική, με την οποία η Αγγελική και η Μαριλένα θα κερδίσουν εγγυημένα το παιχνίδι;

Η στρατηγική σας θα βαθμολογηθεί με βάση την τιμή του ~K~ (όσο μικρότερη, τόσο καλύτερη).

Υλοποίηση

Αυτό είναι ένα πρόβλημα πολλαπλών εκτελέσεων, που σημαίνει ότι το πρόγραμμά σας θα εκτελεστεί πολλές φορές. Την πρώτη φορά που θα εκτελεστεί, θα εφαρμόσει τη στρατηγική της Αγγελικής. Μετά από αυτή, θα εφαρμόσει τη στρατηγική της Μαριλένας.

Η πρώτη γραμμή της εισόδου θα περιέχει δύο ακέραιους ~P~ και ~N~, όπου ~P~ είναι, είτε ~1~, είτε ~2~ (πρώτη ή δεύτερη φάση) και ~N~ ο αριθμός των σπιτιών. Εκτός από το παράδειγμα εισόδου (που δεν χρησιμοποιείται για βαθμολόγηση), το ~N~ θα είναι πάντα ίσο με ~100.000~.

Η παρακάτω είσοδος εξαρτάται από τη φάση:

Φάση 1

Το πρόγραμμά σας θα πρέπει να ξεκινά με την εκτύπωση του αριθμού ~K~ σε μία μόνο γραμμή ~(1 \le K \le 1.000.000)~. Στη συνέχεια, ~N - 1~ φορές, θα πρέπει να διαβάζει μια γραμμή που περιέχει ένα δείκτη ~i\,(0 \le i < N)~ και να εκτυπώνει μια γραμμή με έναν ακέραιο αριθμό ~A_i\,(1 \le A_i \le K)~, όπου ~A_i~ είναι ο αριθμός που γράφει η Αγγελική στην πόρτα του σπιτιού ~i~. Κάθε δείκτης ~i~, εκτός από τον δείκτη του σπιτιού της Ελένης, θα εμφανίζεται ακριβώς μία φορά, σε κάποια σειρά που αποφασίζεται από τον βαθμολογητή.

Φάση 2

Το πρόγραμμά σας θα πρέπει να διαβάσει μια γραμμή με ~N~ ακέραιους, ~A_0, A_1, ..., A_{N-1}~.

Στη συνέχεια, θα πρέπει να εκτυπώσει μια γραμμή με δύο ακέραιους, ~s_1~ και ~s_2~ ~(0 \le s_i < N)~, τους υποθετικούς δείκτες. Οι ~s_1~ και ~s_2~ επιτρέπεται να είναι ίσοι.

Λεπτομέρειες υλοποίησης

Σημειώστε ότι κατά την εκτέλεση του προγράμματός σας στη Φάση 2, το πρόγραμμα επανεκκινείται. Αυτό σημαίνει ότι δεν μπορείτε να αποθηκεύσετε τις πληροφορίες σε ορισμένες μεταβλητές μεταξύ των εκτελέσεων.

Μετά από κάθε γραμμή που εκτυπώνετε, βεβαιωθείτε ότι καθαρίζετε την τυπική έξοδο, αλλιώς το πρόγραμμά σας μπορεί να κριθεί Time Limit Exceeded.

Στην Python, η print() καθαρίζει αυτόματα. Στη C++, η cout << endl; επίσης καθαρίζει, εκτός από την εκτύπωση μιας νέας γραμμής - αν χρησιμοποιείτε την printf, χρησιμοποιήστε την fflush(stdout).

Ο βαθμολογητής γι' αυτό το πρόβλημα μπορεί να είναι προσαρμοστικός (adaptive), που σημαίνει ότι μπορεί να αλλάξει τη συμπεριφορά του ανάλογα με την έξοδο του προγράμματός σας, ώστε να αποτρέψει το πέρασμα ευρετικών (heuristic solutions) λύσεων. Μπορεί να εκτελέσει δοκιμαστικά τη Φάση 1, να δει την έξοδό σας και στη συνέχεια να εκτελέσει κανονικά τη Φάση 1 χρησιμοποιώντας πληροφορίες που άντλησε από την προηγούμενη εκτέλεση.

Το πρόγραμμά σας πρέπει να είναι ντετερμινιστικό, δηλαδή να συμπεριφέρεται το ίδιο αν εκτελεστεί δύο φορές με την ίδια είσοδο. Αν θέλετε να χρησιμοποιήσετε στο πρόγραμμά σας τυχαιότητα, φροντίστε να χρησιμοποιήσετε μια προκαθορισμένη αρχικοποίηση της γεννήτριας τυχαίων αριθμών. Αυτό μπορεί να γίνει περνώντας μια σταθερά στο srand (στη C++) ή στο random.seed (στην Python), ή, αν χρησιμοποιείτε τις γεννήτριες τυχαίων αριθμών της C++11, καθορίζοντας την αρχικοποίηση κατά την κατασκευή της γεννήτριας τυχαίων αριθμών. Συγκεκριμένα, δεν μπορείτε να χρησιμοποιείτε srand (time(NULL)) στην C++. Εάν ο βαθμολογητής εντοπίσει ότι το πρόγραμμά σας δεν είναι ντετερμινιστικό, θα κρίνει Wrong Answer.

Εάν το άθροισμα των χρόνων εκτέλεσης των (μέχρι ~3~) ξεχωριστών εκτελέσεων του προγράμματός σας υπερβαίνει το χρονικό όριο, η υποβολή σας θα κριθεί Time Limit Exceeded.

Βαθμολoγία

Η λύση σας θα δοκιμαστεί σε διάφορες δοκιμαστικές περιπτώσεις. Εάν η λύση σας αποτύχει σε οποιαδήποτε από αυτές τις δοκιμαστικές περιπτώσεις (π.χ. δίνοντας λανθασμένες απαντήσεις (Wrong Answers) ή σταματήσει βίαια (Run-Time Error), υπερβαίνοντας το Χρονικό Όριο (Time Limit Exceeded), κ.λπ,) θα λάβετε ~0~ βαθμούς και το κατάλληλο πόρισμα.

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

Έστω ~K_{max}~ η μέγιστη τιμή του ~K~ που χρησιμοποιείται για κάθε δοκιμαστική περίπτωση.

Ανάλογα με το ~K_{max}~:

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~10~	~K_{max} > 99.998~
~2~	~10 + [40 \times (1 - K_{max} / 10^5)]~	~10\,000 < K_{max} \le 99.998~
~3~	~46 + [31 \times (4 - log_{10}(K))_{max}))/(4 - log_{10}(30))]~	~30 < K_{max} \le 10.000~
~4~	~107 - K_{max}~	~7 < K_{max} \le 30~
~5~	~100~	~K_{max} \le 7~

Η συνάρτηση βαθμολόγησης παρουσιάζεται στο παρακάτω σχήμα.

Το παράδειγμα της δοκιμαστικής περίπτωσης αγνοείται στην αξιολόγηση και η λύση σας δεν είναι απαραίτητο να λειτουργήσει γι' αυτό.

Εργαλείο Ελέγχου

Για να διευκολύνουμε τον έλεγχο της λύσης σας, σας παρέχουμε ένα απλό εργαλείο που μπορείτε να κατεβάσετε. Δείτε τα "συνημμένα" στο κάτω μέρος της σελίδας με τα προβλήµατα στο Kattis. Η χρήση του εργαλείου είναι προαιρετική και μπορείτε να το αλλάξετε. Σημειώστε ότι το επίσημο πρόγραμμα βαθμολόγησης στο Kattis είναι διαφορετικό από το εργαλείο ελέγχου.

Παράδειγμα χρήσης (με ~N = 4~, ~s = 2~, όπου ~s~ είναι ο αριθμός που γράφτηκε στο τελευταίο σπίτι στη σειρά επίσκεψης):

Για προγράμματα Python, ας υποθέσουμε, solution.py (συνήθως εκτελείται ως pypy3 solution.py):

python3 testing_tool.py pypy3 solution.py <<<"4 2"

Για προγράμματα C++, πρώτα μεταγλωττίστε (π.χ. με g++ -g -O2 -std=gnu++17 -static solution.cpp -o solution.out) και στη συνέχεια εκτελέστε:

python3 testing_tool.py ./solution.out <<<"4 2"

Το εργαλείο ελέγχου θα επισκεφθεί τα σπίτια με τυχαία σειρά. Για να χρησιμοποιήσετε μια συγκεκριμένη σειρά, τροποποιήστε το εργαλείο ελέγχου στο σημείο που λέει "MODIFY HERE".

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

Το υποδειγματική δοκιμαστική περίπτωση δε λαμβάνεται υπόψη για τη βαθμολόγηση και η λύση σας δεν χρειάζεται να λειτουργεί γι' αυτήν. Ας υποθέσουμε ότι έχουμε ~N = 4~ και ότι η Ελένη ζει στο σπίτι ~1~. Έστω \($Α$\) η λίστα των αριθμών που είναι γραμμένοι στα σπίτια. Αρχικά, ~A = [0, 0, 0, 0, 0]~, όπου ~0~ σημαίνει ότι κανένας αριθμός δεν είναι γραμμένος στο αντίστοιχο σπίτι.

Στην πρώτη εκτέλεση του κώδικά σας:

• ~N = 4~ δίνεται. Η λύση σας απαντά με ~K = 3~.
• ~A_2~ ζητείται. Η λύση σας απαντά με ~3~. ~A~ τώρα είναι ~[0, 0, 3, 0]~.
• ~A_0~ ζητείται. Η λύση σας απαντά με ~1~. ~A~ τώρα είναι ~[1, 0, 3, 0]~.
• ~A_3~ ζητείται. Η λύση σας απαντά με ~2~. ~A~ τώρα είναι ~[1, 0, 3, 2]~.

Τέλος, ο βαθμολογητής θέτει ~A_1 = 2~, έτσι ώστε το ~A = [1, 2, 3, 2]~ στο τέλος. Αυτό σηματοδοτεί το τέλος της πρώτης φάσης.

Στη Φάση 2 του κώδικά σας, στη λύση σας περνάει η λίστα ~1\,2\,3\,3\,2~.

Απαντά με ~1\,3~.

Καθώς μία από τις μαντεψιές είναι ο σωστός δείκτης του σπιτιού (~1~), η Αγγελική και η Μαριλένα κερδίζουν το παιχνίδι.

Έξοδος Βαθμολογητή	Δική σας έξοδος
~1\,4~
	~3~
~2~
	~3~
~0~
	~1~
~3~
	~2~
~2\,4~
~1\,2\,3\,2~
	~1\,3~