Find the box

Ο Maj είναι ερευνητής ρομποτικής και εργάζεται στο Πανεπιστήμιο Lund. Έχει μάθει για ένα πολύτιμο θησαυρό στο κελάρι του πανεπιστημίου. Ο θησαυρός είναι σε ένα κουτί που βρίσκεται σε ένα άδειο δωμάτιο βαθιά κάτω από το έδαφος. Δυστυχώς, η Maj δεν μπορεί απλά να πάει και να ψάξει για το κουτί. Είναι πολύ σκοτεινά στο κελάρι και το να πάει εκεί με φως θα κινήσει υποψίες. Ο μόνος τρόπος για να βρει τον θησαυρό είναι να ελέγξει εξ αποστάσεως μια ρομποτική ηλεκτρική σκούπα που κατοικεί στο κελάρι.

Το κελάρι αναπαρίσταται ως ένα πλέγμα ~H \times W~, όπου οι γραμμές αριθμούνται από το ~0~ έως το ~H - 1~ (από πάνω προς τα κάτω) και οι στήλες αριθμούνται από το ~0~ έως το ~W - 1~ (από αριστερά προς τα δεξιά), πράγμα που σημαίνει ότι το πάνω αριστερό κελί είναι ~(0, 0)~ και το κάτω δεξί κελί είναι ~(H - 1, W - 1)~. Το κουτί με τον θησαυρό βρίσκεται σε κάποιο άγνωστο κελί, εκτός από το κελί ~(0, 0)~. Κάθε βράδυ, η ρομποτική ηλεκτρική σκούπα ξεκινάει από την πάνω αριστερή γωνία και κινείται γύρω από το κελάρι.

Κάθε βράδυ, ο Maj μπορεί να δώσει στο ρομπότ μια ακολουθία οδηγιών για το πώς πρέπει να κινηθεί, με τη μορφή μιας συμβολοσειράς, που αποτελείται από τους χαρακτήρες "<", ">", "^" και "v". Τυπικά, αν το ρομπότ στέκεται στο κελί ~(r, c)~ που είναι ελεύθερο από όλες τις πλευρές, το "<" μετακινεί το ρομπότ αριστερά προς το κελί ~(r, c - 1)~, το ">" μετακινεί το ρομπότ δεξιά προς το κελί ~(r, c + 1)~, το "^" μετακινεί το ρομπότ επάνω προς το κελί ~(r - 1, c)~ και το "v" μετακινεί το ρομπότ κάτω προς το κελί ~(r + 1, c)~.

Οι τοίχοι του κελαριού είναι συμπαγείς, οπότε αν το ρομπότ προσπαθήσει να κινηθεί εκτός του πλέγματος, δεν θα συμβεί τίποτα.

Το κουτί είναι επίσης συμπαγές και δεν μπορεί να σπρωχτεί. Στο τέλος κάθε νύχτας, το ρομπότ θα αναφέρει τη θέση του και θα επιστρέφει στην πάνω αριστερή γωνία. Ο χρόνος είναι πολύτιμος, οπότε ο Maj αποφασίζει να βρει το κουτί σε όσο το δυνατόν λιγότερες νύχτες.

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

Αυτό είναι ένα διαδραστικό πρόβλημα.

• Το πρόγραμμά σας θα πρέπει να ξεκινήσει διαβάζοντας μια γραμμή με δύο ακέραιους αριθμούς ~H~ και ~W~: το ύψος και το πλάτος του πλέγματος.
• Στη συνέχεια, το πρόγραμμά σας θα πρέπει να αλληλεπιδρά με τον βαθμολογητή. Σε κάθε γύρο αλληλεπίδρασης, θα πρέπει να εκτυπώνετε ένα ερωτηματικό "~?~", ακολουθούμενο από μια μη κενή συμβολοσειρά ~s~ που αποτελείται από τους χαρακτήρες "<", ">", "^", "v". Το μήκος αυτής της συμβολοσειράς μπορεί να είναι το πολύ ~20 000~. Στη συνέχεια, το πρόγραμμά σας θα πρέπει να διαβάσει δύο ακέραιους αριθμούς ~r, c\,(0 \le r \le H - 1,\,0 \le c \le W - 1)~, τη θέση του ρομπότ μετά την εκτέλεση των εντολών. Σημειώστε ότι το ρομπότ επιστρέφει πάντα στο ~(0, 0)~ μετά από κάθε ερώτημα.
• Όταν γνωρίζετε τη θέση του κουτιού, εκτυπώστε "~!~" ακολουθούμενo από τους δύο ακέραιους ~r_b, c_b~, τη γραμμή και τη στήλη του κουτιού ~(0 \le r_b \le H - 1,\,0 \le c_b \le W - 1)~. Μετά από αυτό, το πρόγραμμά σας πρέπει να τερματίσει χωρίς να κάνει άλλα ερωτήματα. Αυτή η τελική έξοδος δεν υπολογίζεται ως ερώτημα στον προσδιορισμό της βαθμολογίας σας.

Βεβαιωθείτε ότι έχετε καθαρίσει την τυπική έξοδο μετά την έκδοση ενός ερωτήματος, αλλιώς το πρόγραμμά σας μπορεί να κριθεί ως Υπέρβαση Χρονικού Ορίου. Στην Python, η print() ξεπλένει αυτόματα. Στη C++, η cout << endl; επίσης ξεπλένει εκτός από την εκτύπωση μιας νέας γραμμής- αν χρησιμοποιείτε την printf, χρησιμοποιήστε την fflush(stdout).

Ο βαθμολογητής είναι μη προσαρμοστικός, πράγμα που σημαίνει ότι η θέση του κουτιού καθορίζεται πριν από την έναρξη της αλληλεπίδρασης.

Περιορισμοί

• ~1 \le H,W \le 50~
• Το κουτί δεν θα βρίσκεται ποτέ στο σημείο ~(0, 0)~. Αυτό σημαίνει ότι ~H + W \geq 3~
• Κάθε ερώτημα μπορεί να αποτελείται το πολύ από ~20 000~ εντολές
• Μπορείτε να εκδώσετε το πολύ ~2 500~ ερωτήματα (η εκτύπωση της τελικής απάντησης δεν μετράει ως ερώτημα)

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

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

~score = min (\frac{100 \times \sqrt{2}}{\sqrt{Q}}, 100)\,\,points~

όπου ~Q~ είναι ο μέγιστος αριθμός ερωτημάτων που χρησιμοποιούνται σε κάθε περίπτωση δοκιμής. Η εκτύπωση της τελικής απάντησης δεν λογίζεται ως ερώτημα. Η βαθμολογία στρογγυλοποιείται στον πλησιέστερο ακέραιο αριθμό.

Ειδικότερα, για να λάβετε ~100~ βαθμούς, το πρόγραμμά σας πρέπει να επιλύει κάθε περίπτωση δοκιμής χρησιμοποιώντας το πολύ ~Q = 2~ ερωτήματα. Ο παρακάτω πίνακας δείχνει ορισμένες τιμές του ~Q~ και τη σχετική βαθμολογία.

Βαθμολογία

~Q~	2	3	4	5	~\cdots~	20	~\cdots~	50	~\cdots~	2500
Score	~100~	~82~	~71~	~63~	~\cdots~	~32~	~\cdots~	~20~	~\cdots~	~3~

Εργαλείο δοκιμών

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

Παράδειγμα χρήσης (με ~H = 4~, ~W = 5~ και το κρυφό κουτί στη θέση ~r = 2~, ~c = 3~):

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

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

Παράδειγμα

Εξετάστε το παράδειγμα της δοκιμαστικής περίπτωσης. Το πλέγμα έχει ύψος ~H = 4~ και πλάτος ~W = 5~ και το κουτί βρίσκεται στη θέση ~(r, c) = (2, 3)~. Το παρακάτω σχήμα δείχνει τη διαδρομή του ρομπότ όταν ακολουθεί τις οδηγίες του πρώτου ερωτήματος "? vv>>>>> <^^^^^>", το οποίο έχει ως αποτέλεσμα το ρομπότ να καταλήξει στη θέση ~(r, c) = (0, 2)~. Πριν από το δεύτερο ερώτημα, το ρομπότ θα επιστρέψει και πάλι στην επάνω αριστερή γωνία ~(0, 0)~. Στη συνέχεια, η λύση εκδίδει ένα άλλο ερώτημα "? >>>>>>>>vvvvvvvvvvvvvvv" για το οποίο το ρομπότ καταλήγει στην κάτω δεξιά γωνία ~(r, c) = (3, 4)~. Τώρα η λύση αποφασίζει να μαντέψει την απάντηση, γράφοντας \("! 2 3"\), η οποία είναι η σωστή θέση του κουτιού.

///ΕΙΚΟΝΑ////