Problem J
Ussimured
Languages
de
en
et
is
lt
lv
no
pl
ru
sv
Sa otsid mullas kohta, kuhu panna oma vihmaussist lemmikloom Maximus. Võimalikud kohad asuvad risttahuka kujulises kastis mõõtmetega $N \times M \times K$ sentimeetrit, mis on jaotatud sentimeetrise küljepikkusega kuupideks. Igal kuubil on koordinaadid $(x,y,z)$, mis viitavad kuubi asukohale risttahuka sees ($1 \le x \le N$, $1 \le y \le M$, $1 \le z \le K$). Iga kuup on teatud mullaniiskusega $H[x,y,z]$, mis on täisarv vahemikus $1 \dots 10^9$. Erilise sensoriga saab mõõta ükskõik millise kuubi niiskust.
Maximusele meeldivad niisked kohad, seega pead ta panema kuupi, mis on vähemalt sama niiske kui naaberkuubid, muidu roomab ta minema ja sul on raske teda uuesti üles leida. Teiste sõnadega pead panema Maximuse lokaalsesse maksimumi. Täpsemini pead leidma kuubi $(x,y,z)$, mille puhul
\[ 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]). \]Niiskus kastist väljaspool on alati $0$ (sest Maximus tahab kindlasti kasti sisse jääda).
Kuna aga kuupide arv võib olla väga suur, siis ei viitsi sa kõikide kuupide niiskust mõõta. Seega saad siin ülesandes suhelda testimisprogrammiga ja küsida, kui niiske on muld teatud kuupides. Kui oled Maximusele leidnud sobiva asukoha, anna see asukoht testimisprogrammile.
Interaktsioon
Sisendi esimesel real on neli positiivset täisarvu: $N$, $M$, $K$ ja $Q$, kus $N$, $M$ ja $K$ on kasti mõõtmed ja $Q$ maksimaalne arv mõõtmisi, mida sa saad sooritada.
Pärast seda võid standardväljundisse kirjutada ülimalt $Q$ rida kujul ? x y z. Päring küsib niiskustaset kuubis $(x, y, z)$. Iga sellise rea jaoks vastab testimisprogramm reaga, millel on täisarv $H[x,y,z]$. Seda saab su programm lugeda standardsisendist.
Pärast kõiki neid ridu peab su programm kirjutama väljundisse täpselt ühe rea kujul ! x y z. See väidab, et kuup $(x, y, z)$ on eelnevale kirjeldusele vastav Maximusele sobiv asukoht. Sellele väljundile testimisprogramm ei vasta.
Kõik väärtused $x, y, z$ peavad olema vahemikes $1 \le x \le N$, $1 \le y \le M$, $1 \le z \le K$. Kui nad seda ei ole või kui mõni rida on vales formaadis või kui esitad rohkem kui $Q$ kuubi niiskuse kohta, siis vastab testimisprogramm väärtusega -1 ja lõpetab töö. Kui see juhtub, peaks ka sinu programm töö lõpetama. Kui programm jätkab tegevust, võib ta saada hindamise tulemuseks “Runtime Error” või “Time Limit Exceeded”.
Sinu programm peab pärast oma päringute väljastamist ja enne niiskustasemete lugemist väljundpuhvri tühjendama. Kui programm seda ei tee, on hindamise tulemuseks “Time Limit Exceeded”. Väljundpuhvri tühendamine käib järgmiselt:
-
Java: System.out.println() tühjendab puhvri automaatselt.
-
Python: print() tühjendab puhvri automaatselt.
-
C++: cout << endl; väljastab reavahetuse ja tühjendab seejärel puhvri; printf() kasutamise järel tühjendab puhvri fflush(stdout).
-
Pascal: Flush(Output).
Selleks, et vastava suhtlusega aidata, on antud abistav kood, mille sa võid oma programmi kopeerida. Link sellele koodile kõigis toetatud keeltes on Kattises ülesande lehel külgribal.
Testprogramm ei ole adaptiivne. See tähendab, et igas testis on muutumatud niiskustasemed, mis ei olene programmi poolt tehtud mõõtmistest.
Piirangud
Selles ülesandes on testid jagatud gruppidesse. Iga grupi eest saavad punkte ainult need programmid, mis lahendavad õigesti kõik gruppi kuuluvad testid. Sinu lõplik skoor on esitatud lahenduste skooride maksimum.
|
Grupp |
Punkte |
Piirangud |
|
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$ |
Näidisdialoog
Kattises on üks näidistest. Näites on kasti mõõtmed $3\times 1\times 1$ ja niiskus kolmes kuubikus on 10, 14, 13. Järgnevalt on toodud näidisdialoog, kus read algusega HINDAJA on Kattise väljund (s.t sinu programmi sisend) ning read algusega SINA on sinu programmi väljund.
Kuna $14$ on võrreldes naaberväärtustega ($10$ and $13$) suurem või võrdne, on asukoht $(2,1,1)$ Maximuse jaoks optimaalne ning sa kasutasid ära kolm päringut, mis oli ülesandes lubatud ($Q=3$). Seega on antud dialoogi tulemuseks Accepted.
HINDAJA: 3 1 1 3 SINA: ? 3 1 1 HINDAJA: 13 SINA: ? 2 1 1 HINDAJA: 14 SINA: ? 1 1 1 HINDAJA: 10 SINA: ! 2 1 1
