Problem E
Sliekas raizes
Languages
de
en
et
is
lt
lv
no
pl
ru
sv
Jūs meklējat vietu augsnē, kur novietot savu mājdzīvnieku, slieku Maximus. Jūs ierobežojāt meklēšanas platību uz paralēlskaldni, kura izmērs ir $N \times M \times K$ centimetri, ko jūs esat sadalījis trīs dimensionālā režģī ar viena kubikcentimetra šūnām, šūnas ir marķētas ar $(x, y, z)$ pēc to pozīcijas iekš režģa ($1 \le x \le N$, $1 \le y \le M$, $1 \le z \le K$). Katrai šūnai ir noteikts mitruma daudzums $H[x,y,z]$, kas ir vesels skaitlis $1 \dots 10^9$ diapazonā. Jūs varat nomērīt mitruma daudzumu jebkurā šūnā ar speciālu sensoru.
Maximus mīl mitras vietas, tādēļ jums viņš jānovieto šūnā, kurā mitruma daudzums ir vismaz tikpat liels kā tās kaimiņu šūnās, citādi viņš dodas prom, un jums būs problēmas viņu atrast. Citiem vārdiem sakot, jums jānovieto Maximus lokālajā maksimumā. Precīzāk, jums jāatrod tāda šūna $(x,y,z)$, ka
\[ 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]), \]kur šūnas mitruma daudzums ir $0$, ja tā atrodas ārpus paralēlskaldņa, jo Maximus ļoti vēlas palikt tājā iekšā.
Tomēr šūnu ir ļoti daudz, tāpēc jūs nevēlaties mērīt mitruma daudzumu visās šūnās. Tādēļ šajā uzdevumā jums ir atļauts komunicēt ar vērtēšanas programmu un uzdot tai jautājumus par mitruma daudzumu noteiktā šūnā. Kad jūs atrodat piemērotu šūnu sliekai Maximus, iesniedziet šūnas pozīciju vērtēšanas programmai.
Komunikācija
Pirmā ievaddatu rinda satur četrus pozitīvus veselus skaitļus: $N$, $M$, $K$ un $Q$, kur $N$, $M$ un $K$ ir paralēlskaldņa dimensijas un $Q$ ir maksimālais mērījumu skaits, ko jūs varat veikt.
Pēc tam varat izvadīt ne vairāk kā $Q$ rindas formā “? x y z“ uz standarta izvadu. Tādas formas rinda apraksta mitruma mērīšanas pieprasījumu šūnā $(x, y, z)$. Katrai šādai rindai vērtēšanas programma atbildē izvadīs vienu rindu ar veselu skaitli $H[x,y,z]$, ko jūsu programma var nolasīt no standarta ievada.
Pēc visām šīm rindām jūsu programmai jāizvada tieši viena rinda formā “! x y z“ un jābeidz darbība. Tas apgalvos, ka šūna $(x, y, z)$ ir piemērota sliekai Maximus pēc augstāk minētajiem kritērijiem. Vērtēšanas programma neatbildēs uz šo izvadu.
Visām $x, y, z$ vērtībām jāievēro nosacījums $1 \le x \le N$, $1 \le y \le M$, $1 \le z \le K$. Ja nosacījumu neievēro, vai ja kāda rinda izvadīta nekorektā formā, vai ja tiek prasīts mitruma daudzums vairāk kā $Q$ šūnām, vērtēšanas programma atbildēs ar -1 un pabeigs darbu. Ja tas tā notiek, tad jūsu programmai arī jāpabeidz darbība. Ja tā turpina darboties, tā var saņemt nepareizu vērtējumu Runtime Error vai Time Limit Exceeded.
Jums jānodrošina, ka programma sinhronizē (flush) izvada datu plūsmu pirms tā nolasa vērtēšanas programmas atbildi, citādi saņemsiet vērtējumu Time Limit Exceeded. Atbalstītajās valodās to var izdarīt sekojošā veidā:
-
Java: System.out.println() sinhronizē automātiski.
-
Python: print() sinhronizē automātiski.
-
C++: cout << endl; sinhronizē, papildus izvada jaunas rindas simbolu. Ja lietojat printf, fflush(stdout).
-
Pascal: Flush(Output).
Lai palīdzētu komunicēt ar vērtēšanas programmu, mēs nodrošinam programmas kodu, kuru jūs pēc savas izvēles varat iekopēt savā programmā. Saiti uz programmu kodiem visām atbalstītajām valodām (C++, Pascal, Java, Python) varat atrast testēšanas sistēmas uzdevumu lapas sānjoslā. Nodrošinātais programmas kods arī lieto ātras ievada/izvada operācijas, kas var būt noderīgas Python un Java risinājumos (it īpaši pēdējās divās testu grupās).
Vērtēšanas programma neadaptēsies, t.i., katrā testā būs fiksētas mitruma daudzuma vērtības, kuras nav atkarīgas no programmas veiktajiem mērījumiem.
Ierobežojumi
Jūsu risinājums tiks testēts uz vairākām testu grupām, par katru no tām var iegūt punktus. Katra testu grupa satur vienu vai vairākus testus. Lai iegūtu punktus par testu grupu, jums ir pareizi jāatrisina visi testi šajā grupā. Jūsu beigu vērtējums par uzdevumu būs starp visiem iesūtījumiem lielākais.
|
Grupa |
Punkti |
Ierobežojumi |
|
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$ |
Parauga dialoga protokols
Kattis testēšanas sistēmā ir viens parauga tests. Šajā parauga testā paralēlskaldņa izmēri ir $3\times 1\times 1$ un mitruma daudzums tā trīs šūnās ir {10, 14, 13}. Zemāk ir parauga dialogs, kur rindas ar sākumu JUDGE ir izvads no vērtēšanas programmas (t.i. ievads jūsu programmā), un rindas ar sākumu YOU ir jūsu programmas izvads.
Tā kā $14$ tiešām ir lielāks vai vienāds ar kaimiņu šūnu vērtībām ($10$ un $13$), tad šūna $(2,1,1)$ ir piemērota sliekai Maximus, un jūs izmantojāt trīs mērījumus, kas bija maksimāli atļautais mērījumu skaits ($Q=3$). Tādēļ šāds dialogs saņems vērtējumu Accepted parauga testā.
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
