Problem E
Mineraaliesiintymät
Languages
da
de
en
et
fi
lt
lv
pl
uk
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}](/problems/boi23.mineraldeposits/file/statement/fi/img-0002.png)
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
