Problem E
Hemlig vandring
Languages
en
sv
I den exotiska och varma staden Mänhettan bor Harry och hans virrige kompis Tobias. Staden är ett $N \times N$-rutnät med koordinater $(x,y)$ där $0 \le x,y < N$. Det finns hus på alla rutor där både $x$ och $y$ är udda tal. Rutan längst upp till vänster är $(0,0)$, rutan längst ner till vänster är $(N-1,0)$, och rutan längst ner till höger är $(N-1,N-1)$.
Tobias bor i ett av dessa hus, och hans skola ligger i ett annat. De ligger inte på samma rad eller kolumn, eftersom Harry har varit hemma hos Tobias och inte kunnat se skolan genom fönstret.
Tobias får röra sig mellan två rutor som delar en sida, och detta tar exakt en minut. Varje dag går han den kortaste vägen till skolan och skickar meddelanden som ”On my way now!” och ”Just arrived!”, vilket innebär att Harry vet exakt hur lång tid det tar för Tobias att röra sig från hans hus till skolan.
Trots att Harry har varit hemma hos Tobias och vet om en ruta är ett hus, har han glömt både var Tobias bor och var skolan är lokaliserad.
För att lista ut denna information, kan Harry varje dag få magiskt trolla fram väggar på valfria rutor som inte innehåller hus. Den dagen tar det $t$ minuter för Tobias att ta sig från sitt hus till skolan, eller $t = -1$ om han fastnar helt. Efter den dagen försvinner alla väggar som Harry hade trollat fram.
Din uppgift är att hjälpa Harry att bestämma vilket hus Tobias bor i och vilket hus hans skola ligger i genom att använda så få dagar som möjligt. Harry får spendera upp till 365 dagar på sig, men du får fler poäng ju färre dagar du använder.
Interaktion
Det här är ett interaktivt problem.
-
Ditt program ska först läsa in en rad med ett tal $N$ $(5 \le N \le 75, N \text{ är ett udda tal.})$, höjden och bredden av rutnätet. Därefter ska ditt program läsa in $N$ rader, med $N$ karaktärer på vardera rad som beskriver rutnätet. Tecknet H innebär att rutan är ett hus, medan . innebär att den är tom.
-
Sen ska ditt program interagera med gradern. För att ta reda på antalet minuter $t$ som Tobias behöver längs en kortaste väg kan du ställa en fråga genom att placera ut väggar. Detta görs genom att du först skriva ut en rad med ett frågetecken ”?”. På de följande $N$ raderna skriver du ett $N \times N$ rutnät som är en kopia av det ursprungliga, med valfria tomma rutor . ersatta av # (väggar).
Därefter läser programmet in ett heltal $t$ ($-1 \le t \le N^2$), det minsta antalet minuter Tobias behöver för att ta sig från sitt hus till skolan om han får passera hus (H) och tomma rutor (.), men inte väggar (#).
-
När du vill skriva ut ett svar ska du skiva ut en rad med utropstecken ”!”, följt med 4 heltal $x_1, y_1, x_2, y_2$ där $(x_1,y_1)$ och $(x_2, y_2)$ är koordinaterna av Tobias hus samt skolan i valfri ordning. Formatet för det du skriver ut ska vara ”! $x_1$ $y_1$ $x_2$ $y_2$”. För att att ditt svar ska accepteras, måste antingen Tobias hus vara $(x_1,y_1)$ och skolan vara vid $(x_2,y_2)$, eller Tobias hus vara $(x_2,y_2)$ och skolan vara vid $(x_1,y_1)$.
Efter detta ska ditt program avslutas.
Gradern är icke-anpassningsbar, vilket innebär att positionerna av Tobias hus och skolan är bestämda innan interaktionen startar.
Se till att flusha outputen efter varje fråga, annars kan du få Time Limit Exceeded. I Python sker detta automatiskt så länge input() används för att läsa in raderna. I C++ flushar cout << endl;, men annars kan detta göras med exempelvis cout << flush; eller fflush(stdout);, och i Java med System.out.flush();.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poäng |
Gränser |
|
$1$ |
$5$ |
$N = 5$ |
|
$2$ |
$9$ |
$N \leq 9$ |
|
$3$ |
$11$ |
Tobias hus är på ruta $(1,1)$ (huset längst upp till vänster). |
|
$4$ |
$\text{upp till } 75$ |
Inga ytterligare begränsningar. |
I den sista testgruppen beror din poäng på antalet dagar som används enligt följande formel:
\[ score = \begin{cases} 75, & \text{om } Q \le 5,\\ 63, & \text{om } 5 < Q \le 6,\\ 55 \cdot \left( 10/55 \right)^{ (Q-10)/85}, & \text{om } 6 < Q \le 10,\\ 53 \cdot \left( 8/53 \right)^{ (Q-10)/64}, & \text{om } 10 < Q \le 75,\\ 4 \cdot \left(1/4\right)^{ (Q-160)/205}, & \text{om } 75 < Q \le 365,\\ 0, & \text{om } Q > 365. \end{cases} \]där $Q$ är det maximala antalet dagar som användes för något testfall. Poängen avrundas till närmaste heltal.
För att få full poäng i denna grupp måste alltså Harry klara alla testfall på högst $5$ dagar.
Följande är en tabell över poängsättningen för olika värden på $Q$:
|
Q |
Points |
|
5 |
75 |
|
6 |
63 |
|
10 |
55 |
|
11 |
51 |
|
30 |
29 |
|
75 |
8 |
|
160 |
4 |
|
300 |
2 |
|
365 |
1 |
|
366 |
0 |
Längre ner på sidan finns även en fil points.txt som innehåller poängsättningen för alla möjliga värden på $Q$.
Det finns även en testing_tool.py som kan användas för att testa din lösning lokalt.
| Read | Sample Interaction 1 | Write |
|---|
5 ..... .H.H. ..... .H.H. .....
? ..... .H#H. .###. .H#H. .....
8
? ..#.. .H#H. #..## .H#H. ..#..
-1
! 1 1 3 3
| Read | Sample Interaction 2 | Write |
|---|
9 ......... .H.H.H.H. ......... .H.H.H.H. ......... .H.H.H.H. ......... .H.H.H.H. .........
? #...##..# .H#H#H#H. .#######. .H#H.H#H. ..#.#..#. .H#H.H#H. .###.###. .H#H.H#H. ....#...#
14
? ......... .H.H.H.H. ......... .H.H.H.H. ......... .H.H.H.H. ......... .H.H.H.H. .........
6
! 5 7 3 3
