Baltic Olympiad in Informatics 2018 - day 1

Start

2018-04-28 07:00 UTC

Baltic Olympiad in Informatics 2018 - day 1

End

2018-04-28 12:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -225 days 23:21:05

Time elapsed

5:00:00

Time remaining

0:00:00

Problem C
Ussimured

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.

Interactivity

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.

Constraints

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

Group

Points

Limits

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