Questo è un problema interattivo.
Dopo il grande successo ottenuto dal 2018 al 2024, la Nanjing University of Aeronautics and Astronautics (NUAA) ospiterà per l'ottava volta consecutiva la fase regionale di Nanchino dell'International Collegiate Programming Contest (ICPC).
Il team Power of Two e il team Three Hold Two hanno vinto il titolo di campione per la Tsinghua University nel 2018 e nel 2019. Nel 2020, 2021 e 2022, il team Inverted Cross della Peking University ha conquistato tre titoli consecutivi, mentre nel 2023 un altro team della Peking University, Reborn as a Vegetable Dog, ha vinto il titolo. Nel 2024, il team Afterlife della Zhejiang University si è classificato al primo posto.
Quest'anno partecipano alla gara circa $335$ squadre. Verranno assegnate al massimo $33$ medaglie d'oro, $66$ medaglie d'argento e $99$ medaglie di bronzo (si noti che questi numeri sono solo indicativi). Non vediamo l'ora di assistere alle straordinarie prestazioni dei partecipanti! Desideriamo inoltre esprimere la nostra gratitudine per il duro lavoro svolto da tutto lo staff e dai volontari per questa gara. Grazie a tutti per il vostro grande contributo a questa competizione!
Foto scattata durante il 2023 ICPC Asia Nanjing Regional Contest
Nella gara del 2018, il problema K, Kangaroo Puzzle, richiedeva ai concorrenti di costruire una sequenza di operazioni per il gioco:
Il puzzle è una griglia con $n$ righe e $m$ colonne ($1 \le n, m \le 20$), e ci sono alcuni (almeno $2$) canguri nella griglia. L'obiettivo del giocatore è controllarli per farli riunire nella stessa cella. In alcune celle sono presenti dei muri e i canguri non possono entrare nelle celle con i muri. Le altre celle sono vuote. I canguri possono spostarsi da una cella vuota a una cella vuota adiacente in quattro direzioni: su, giù, sinistra e destra.
All'inizio c'è esattamente un canguro in ogni cella vuota, e il giocatore può controllare i canguri premendo i pulsanti
U,D,L,Rsulla tastiera. I canguri si muoveranno simultaneamente in base al pulsante premuto.Il concorrente deve costruire una sequenza di operazioni di al più $5 \times 10^4$ passi composta esclusivamente da
U,D,L,Rper raggiungere l'obiettivo.
Nella gara del 2020, il problema A, Ah, It’s Yesterday Once More, richiedeva ai concorrenti di costruire una mappa di input per violare (hackerare) il seguente codice relativo al problema descritto in precedenza:
#include <bits/stdc++.h>
using namespace std;
string s = "UDLR";
int main()
{
srand(time(NULL));
for (int i = 1; i <= 50000; i++) putchar(s[rand() % 4]);
return 0;
}Inoltre, nella gara del 2021 (Problema A, Oops, It’s Yesterday Twice More), nella gara del 2022 (Problema A, Stop, Yesterday Please No More), nella gara del 2023 (Problema A, Cool, It’s Yesterday Four Times More) e nella gara del 2024 (Problema A, Hey, Have You Seen My Kangaroo?), ogni anno abbiamo avuto un problema legato ai canguri! Vorremmo presentarvi tutti questi problemi, ma se lo facessimo ogni anno, nella gara del 3025 potremmo ritrovarci con un testo di 500 pagine per un singolo problema. Pertanto, questa volta li omettiamo. Del resto, potreste averli già visti nella gara di prova.
Ora, nella gara del 2025, come tutti si aspettavano, il problema dei canguri è tornato! Non sappiamo perché gli autori dei problemi siano così ossessionati dai canguri, ma il problema è il seguente:
Vi viene data una griglia con $n$ righe e $m$ colonne. C'è una buca nella cella situata sulla $i_h$-esima riga e sulla $j_h$-esima colonna. Tutte le altre celle sono vuote e in ciascuna di esse si trova un canguro.
Allo stesso modo, i canguri vengono controllati premendo il pulsante U, D, L, R sulla tastiera. Tutti i canguri si muoveranno simultaneamente in base al pulsante premuto. Nello specifico, per qualsiasi canguro situato nella cella sulla $i$-esima riga e $j$-esima colonna, indicata con $(i, j)$:
- Pulsante
U: si sposterà in $(i - 1, j)$. - Pulsante
D: si sposterà in $(i + 1, j)$. - Pulsante
L: si sposterà in $(i, j - 1)$. - Pulsante
R: si sposterà in $(i, j + 1)$.
Se un canguro finisce nella buca (cioè $i = i_h$ e $j = j_h$) oppure esce dalla griglia, viene rimosso dalla griglia.
Il problema è che i valori esatti di $i_h$ e $j_h$ non sono noti. Il vostro compito è trovare la posizione della buca con al più $(n + m + 10)$ interrogazioni (query). Per ciascuna interrogazione, potete premere un pulsante (U, D, L oppure R). L'interattore stamperà come risposta un intero $t$, che indica il numero di canguri rimasti dopo aver premuto il pulsante.
Si noti che l'interattore non è adattivo, il che significa che la risposta per ciascun caso di test è predeterminata.
Input
Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 100$) che indica il numero di casi di test. Per ciascun caso di test:
La prima riga contiene due interi $n$ e $m$ ($3 \le n, m \le 30$) che indicano il numero di righe e di colonne della griglia.
Protocollo di interazione
Per effettuare un'interrogazione, stampate una riga. Stampate prima ? seguito da uno spazio, poi una lettera maiuscola dell'alfabeto inglese (U, D, L oppure R). Dopo aver effettuato il flush dell'output, il vostro programma dovrà leggere un singolo intero $t$ che indica la risposta alla vostra interrogazione. Ricordate che potete effettuare al più $(n + m + 10)$ interrogazioni per ciascun caso di test.
Se volete indovinare la posizione della buca, stampate una riga. Stampate prima ! seguito da uno spazio, poi due interi $i_h$ e $j_h$ ($1 \le i_h \le n$, $1 \le j_h \le m$) separati da uno spazio che indicano la posizione. Dopo aver effettuato il flush dell'output, il vostro programma dovrà continuare elaborando il caso di test successivo, oppure terminare immediatamente se non ci sono altri casi di test. Si noti che il tentativo finale non conta come interrogazione.
Per effettuare il flush dell'output, potete usare:
fflush(stdout)(se usateprintf) oppurecout.flush()(se usatecout) in C e C++.System.out.flush()in Java e Kotlin.sys.stdout.flush()in Python.
Esempi
2
3 4
7
3
4 3
8
5? L
? D
! 2 3
? U
? R
! 1 1