Problem E
Mask-omsorg
Languages
de
en
et
is
lt
lv
no
pl
ru
sv
Du letar efter en plats i jorden att lägga din tama mask, Maximus. Du begränsar ditt letande till ett rätblock med dimensionerna $N \times M \times K$ centimeter, vilket du har delat in i ett tredimensionellt rutnät av kubikcentimeter-celler, benämnda $(x,y,z)$ enligt deras position i rutnätet ($1 \le x \le N$, $1 \le y \le M$, $1 \le z \le K$). Varje cell har en viss fuktighet $H[x,y,z]$ som är ett heltal mellan $1$ och $10^9$. Du kan mäta fuktigheten i valfri cell med en speciell sensor.
Maximus älskar fuktiga platser, så du måste placera honom i en cell som är minst lika fuktig som dess angränsande celler, annars kravlar han iväg och du får problem att hitta honom. Med andra ord ska du placera Maximus i ett lokalt maximum. Mer preciserat: du ska finna en cell $(x,y,z)$, sådan att
\[ H[x,y,z] \ge \max (H[x+1,y,z], H[x-1,y,z], H[x,y+1,z], H[x,y-1,z], H[x,y,z+1], H[x,y,z-1]), \]där ett värde anses som $0$ om det är utanför rätblocket (eftersom Maximum absolut vill stanna inom detta).
Antalet celler kan dock vara väldigt stort, så du vill inte mäta fuktigheten i alla celler. Därför kan du i den här uppgiften interagera med Kattis och fråga efter fuktigheten i vissa celler. När du har hittat en lämplig placering åt Maximus, ange denna plats till Kattis.
Interaktivitet
Den första raden av indata innehåller fyra positiva heltal: $N$, $M$, $K$ och $Q$, där $N$, $M$ och $K$ är rätblockets dimensioner och $Q$ är det maximala antalet mätningar du får göra.
Efter detta kan du skriva högst $Q$ rader på formen “? x y z” till standard output. Detta frågar efter värdet på fuktigheten i cellen $(x, y, z)$. För varje sådan rad, skriver Kattis som svar en enda rad med heltalet $H[x,y,z]$, vilket kan läsas från standard input av ditt program.
Efter alla dessa rader, måste ditt program skriva ut exakt en rad på formen “! x y z”, och direkt avslutas. Detta påstår att celllen $(x, y, z)$ är en lämplig plats för Maximus enligt kriteriet ovan. Kattis ger inget svar på den här raden.
Alla värden på $x, y, z$ måste uppfylla $1 \le x \le N$, $1 \le y \le M$, $1 \le z \le K$. Om de inte gör det, eller om någon rad har ogiltigt format, eller om du frågar efter mer än $Q$ värden, så svarar Kattis med -1 och avslutas. Om detta händer ska ditt program också avsluta. Om det fortsätter köra, kan det få bedömningen Runtime Error eller Time Limit Exceeded.
Du måste se till att flusha standard output innan du läser Kattis svar, annars kommer körningen bedömas som Time Limit Exceeded. Så här fungerar detta i de olika språken:
-
Java: System.out.println() flushar automatiskt.
-
Python: print() flushar automatiskt.
-
C++: cout << endl; flushar, utöver att skriva ny rad. Om du använder printf, fflush(stdout).
-
Pascal: Flush(Output).
För att hjälpa till att hantera den här interaktionen, tillhandahåller vi hjälpkod som du kan kopiera in i ditt program. Länk till den koden för alla supportade språk (C++, Pascal, Java, Python) finns i sidebaren till Kattis problemsida. Denna hjälpkod använder också snabba input/output-rutiner, vilket kan vara viktigt om du skriver i Java eller Python (endast relevant för de två sista testgrupperna).
Kattis kommer att vara icke-adaptiv; d.v.s. varje testfall kommer att ha en fix uppsättning fuktighetsvärden som inte beror på vilka mätningar programmet efterfrågar.
Begränsningar
Din lösning kommer att testas på en uppsättning testgrupper, var och en värd en viss poäng. Varje testgrupp innehåller flera testfall. För att få poäng för en testgrupp måste du klara alla testfallen i gruppen. Din slutgiltiga poäng på problemet kommer att vara den maximala poängen av en enda submission.
|
Grupp |
Poäng |
Gränser |
|
1 |
10 |
$M = K = 1$, $N = 1\, 000\, 000$, $Q = 10\, 000$ |
|
2 |
22 |
$M = K = 1$, $N = 1\, 000\, 000$, $Q = 35$ |
|
3 |
12 |
$K = 1$, $N = M = 200$, $Q = 4\, 000$ |
|
4 |
19 |
$K = 1$, $N = M = 1\, 000$, $Q = 3\, 500$ |
|
5 |
14 |
$N = M = K = 100$, $Q = 100\, 000$ |
|
6 |
23 |
$N = M = K = 500$, $Q = 150\, 000$ |
Exempel dialog
På Kattis finns det ett sample testfall. I detta testfall har rätblocket dimensionerna $3\times 1\times 1$ och luftfuktigheten i dessa tre celler är {10, 14, 13}.
Nedan är ett exempel på dialog, där raderna som föregås av JUDGE är utskriften från Kattis, dvs indatan till ditt program, och raderna som föregås av YOU är ditt programs utskrift.
Eftersom $14$ är minst lika stort som de närliggande cellernas värden ($10$ och $13$), är positionen $(2, 1, 1)$ en lämplig plats för Maximus, och du använde 3 mätningar, vilket var det maximala antalet mätningar ($Q=3$). Därför blir följande dialog accepterad på sample.
JUDGE: 3 1 1 3 YOU: ? 3 1 1 JUDGE: 13 YOU: ? 2 1 1 JUDGE: 14 YOU: ? 1 1 1 JUDGE: 10 YOU: ! 2 1 1
