Hide

Problem B
Mineraaliesiintymät

Languages da de en et fi lt lv pl uk
/problems/boi23.mineraldeposits/file/statement/fi/img-0001.jpg
Kulunut mutapinta paljastaa uusia mineraaleja. Kuva: Michael D. Turnbull. Lisenssi CC BY-SA.

Hoidat signaalinkäsittelyä ulkoavaruuden kaivosyhtiössä, ja avaruusaluksesi lähestyy parhaillaan asteroidia. Alustavat skannaukset näyttävät, että asteroidilla on $k$ mineraaliesiintymää, mutta niiden tarkat sijainnit ei ole tiedossa.

Asteroidin pinta voidaan nähdä kokonaislukukoordinaattisena ruudukkona, jossa $i$:s mineraaliesiintymä sijaitsee tuntemattomissa koordinaateissa $(x_ i, y_ i)$, joille pätee $-b \le x_ i \le b$ and $-b\le y_ i \le b$ jollakin kokonaisluvulla $b$, joka vastaa alustavan skannauksen kokoa.

Selvittääksesi mineraaliesiintymien tarkat sijainnit, voit lähettää luotaimia asteroidin pinnalle. Luotaimet lähetetään useiden luotainten aalloissa.

Sanotaan, että lähetät pinnalle $d$:n luotaimen aallon koordinaatteihin $(s_ j, t_ j)$, kun $1\leq j\leq d$. Kun luotain saapuu koordinaatteihinsa, se mittaa Manhattan-etäisyyden jokaiseen $k$:sta mineraaliesiintymästä ja lähettää etäisyydet takaisin alukselle. Kaikki etäisyystiedot saapuvat samaan aikaan, eikä ole mahdollista selvittää, mikä luotain palautti mitkäkin etäisyydet. Luotainaalto palauttaa siis $k \cdot d$ kokonaislukuetäisyyttä

\[ |x_ i-s_ j| + |y_ i - t_ j|, \qquad \text {missä } i \in \{ 1,\ldots ,k\} \text { ja } j \in \{ 1,\ldots ,d\} \, . \]

Tehtäväsi on minimoida pinnalle lähetettävien luotainaaltojen määrä.

Interaktio

Tämä on interaktiivinen tehtävä. Interaktio alkaa sillä, että luet yhden rivin, joka sisältää kolme kokonaislukua $b$, $k$ ja $w$: ruudukon raja $b$, mineraaliesiintymien määrä $k$ ja suurin mahdollinen määrä luotainaaltoja $w$.

Tämän jälkeen voit tehdä yhteensä $w$ kyselyä, joista jokainen vastaa yhden luotainaallon lähettämistä. Kysely koostuu merkistä ?, jota seuraa $2d$ välilyönneillä erotettua kokonaislukua, esimerkiksi “? $s_1$ $t_1$ $\cdots $ $s_ d$ $t_ d$”, jossa luotainten määrälle $d$ täytyy päteä $1\leq d\leq 2000$. Arvot $(s_ i,t_ i)$ tulkitaan $i$:nnen luotaimen koordinaatteina ja niille täytyy päteä $-10^8 \leq s_ i \leq 10^8$ ja $-10^8 \leq t_ i \leq 10^8$. Vastaus on yksi rivi, joka sisältää $k \cdot d$ kokonaislukua ei-vähenevässä järjestyksessä: kaikkien mineraaliesiintymä-luotain-parien väliset Manhattan-etäisyydet. Kaikissa aalloissa lähetettyjen luotainten kokonaismäärä ei saa ylittää $2\cdot 10^4.$

Interaktio loppuu riviin, joka koostuu merkistä ! ja $k$:sta pisteestä $x_1, y_1, x_2, y_2, \ldots x_ k, y_ k$, välilyönneillä erotettuina. Tämän tulee olla tulosteen viimeinen rivi.

Ratkaisusi katsotaan oikeaksi, jos se tulostaa jokaisen mineraaliesiintymän sijainnin oikein. Voit tulostaa ne missä tahansa järjestyksessä.

Rajoitukset ja pisteytys

Kaikille testitapauksille pätee $1\leq b \leq 10^8$, $1 \leq k \leq 20$, ja $2 \le w \le 10^4$.

Ratkaisu testataan testiryhmillä, joista kullakin on oma pistemäärä. Jokainen testiryhmä sisältää joukon testitapauksia. Ryhmän pisteet saa vain, jos ratkaisee kaikki sen testitapaukset. Tehtävän lopullinen pistemäärä on suurin yksittäisen lähetyksen pistemäärä.

Ryhmä

Pisteet

Rajoitukset

$1$

$16$

$k = 1, w = 10^4$

$2$

$19$

$w \ge 500$

$3$

$11$

$w \ge 210$

$4$

$13$

$w \ge 130$

$5$

$14$

$w \ge 3$, $b \le 10^4$

$6$

$14$

$w \ge 3$, $b \le 10^7$

$7$

$13$

Ei muita rajoituksia

Esimerkki

\includegraphics[width=.6\textwidth ]{img/sample1.pdf}

Tässä esimerkissä on $k=2$ mineraaliesiintymää, jotka sijaitsevat pisteissä $(1,2)$ ja $(-3,-2)$, merkitty punaisilla tähdillä. Ensimmäisessä aallossa voisit lähettää $d=3$ luotainta pisteisiin $(-4,-3)$, $(-1, 0)$ ja $(2,-1)$, merkitty mustilla pisteillä. Tällöin aalto palauttaisi $6$ etäisyyttä

\[ 2, 4, 4, 4, 6, 10\, . \]

Seuraavalla aallolla voisit lähettää $d=2$ luotainta pisteisiin $(1,2)$ ja $(0,-2)$. Tällöin aalto palauttaisi $4$ etäisyyttä

\[ 0, 3, 5, 8\, . \]
Read Sample Interaction 1 Write
 4 2 10
 ? -4 -3 -1 0 2 -1
 2 4 4 4 6 10
 ? 1 2 0 -2
 0 3 5 8
 ! 1 2 -3 -2