Problem B
Mineraalilademed
Languages
da
de
en
et
fi
lt
lv
pl
uk
Sa töötad maavälises kaevandusfirmas signaalitöötluse kallal. Hetkel on sinu tähelaev asteroidile lähenemas. Esialgsete seireandmete alusel on põhjust arvata, et asteroidil on $k$ mineraaliladet. Nende täpsed asukohad on aga teadmata.
Kirjeldame asteroidi pinda kui täisarvuliste koordinaatidega ruudustikku. $i$-s mineraalilade asub teadmata positsioonil $(x_ i, y_ i)$, kus $-b \le x_ i \le b$ and $-b\le y_ i \le b$. Siin $b$ on mingi täisarv, mis vastab esialgse seire ulatusalale.
Mineraalilademete täpsete asukohtade leidmiseks saad sa saata asteroidi pinnale sonde. Sondid saadetakse lainete kaupa, mitu sondi korraga.
Oletame, et saatsid $d$ sondist koosneva laine asteroidi pinnale, koordinaatidele $(s_ j,t_ j)$ iga $1 \leq j \leq d$ kohta. Kui sond jõuab oma asukohale, arvutab see Manhattani kauguse iga $k$ mineraalilademeni ja saadab kaugused tähelaevale tagasi. Kõik andmepaketid saabuvad samal ajal, seega ei ole võimalik teada saada, millised kaugused on millise sondi saadetud. Niisiis tagastab laine $k\cdot d$ täisarvulist kaugust:
\[ |x_ i-s_ j| + |y_ i - t_ j| \qquad \text {iga } i \in \{ 1,\ldots ,k\} \text { ja } j \in \{ 1,\ldots ,d\} \text { kohta}\, . \]Sinu ülesanne on minimeerida pinnale saadetud sondide arv.
Interaktsioon
See on interaktiivne ülesanne. Interaktsioon algab, kui sa loed sisendist ühe rea, mis koosneb kolmest täisarvust $b$, $k$ ja $w$: ruudustiku piir $b$, mineraalilademete arv $k$, maksimaalne lainete arv $w$, mida sul on lubatud saata.
Seejärel saad sa küsida ülimalt $w$ päringut, millest igaüks vastab ühele lainele. Päring koosneb sümbolist ?, millele järgnevad $2d$ tühikutega eraldatud täisarvu: “? $s_1$ $t_1$ $\cdots $ $s_ d$ $t_ d$”, kus laines olevate sondide arv $d$ peab rahuldama tingimust $1\leq d\leq 2000$. Väärtused $(s_ i, t_ i)$ tähistavad $i$-nda sondi koordinaate ja peavad rahuldama tingimusi $-10^8 \leq s_ i \leq 10^8$ ja $-10^8 \leq t_ i \leq 10^8$. Vastuseks tuleb üks rida, mis koosneb mittekahanevas järjekorras $k \cdot d$ täisarvust: kõikide mineraalilademete ja sondikoordinaatide paaride vahelised Manhattani kaugused. Sondide koguarv üle kõikide lainete ei tohi ületada $2\cdot 10^4.$
Interaktsioon lõpeb, kui trükid välja ühe rea, mis koosneb sümbolist !, millele järgnevad $k$ tühikutega eraldatud arvu $x_1, y_1, x_2, y_2, \ldots , x_ k, y_ k$. See peab olema viimane sinu poolt trükitud väljundirida.
Vastus loetakse korrektseks, kui trükid välja kõikide mineraalilademete asukohad. Need võid välja trükkida mistahes järjekorras.
Piirangud ja hindamine
Alati kehtivad $1\leq b \leq 10^8$, $1 \leq k \leq 20$, ja $2 \le w \le 10^4$.
Selles ülesandes on testid jagatud gruppidesse, iga grupp on väärt mingi arvu punkte. Iga grupi eest saavad punkte vaid need lahendused, mis läbivad kõik sellesse gruppi kuuluvad testid. Sinu lõplik skoor on esituste maksimum.
|
Grupp |
Punktid |
Lisapiirangud |
|
$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$ |
Lisapiirangud puuduvad |
Example
![\includegraphics[width=.6\textwidth ]{img/sample1.pdf}](/problems/boi23.mineraldeposits/file/statement/et/img-0002.png)
Selles näites on $k=2$ mineraaliladet, mis asuvad positsioonidel $(1,2)$ ja $(-3,-2)$. Need on kujutatud punaste tähekestena. Esimese lainega võid saata näiteks $d=3$ sondi koordinaatidele $(-4,-3)$, $(-1, 0)$ ja $(2,-1)$, mida on kujutatud mustade täppidena. See laine tagastab $6$ kaugust
\[ 2, 4, 4, 4, 6, 10\, . \]Järgmise lainega võid saata näiteks $d=2$ sondi koordinaatidele $(1,2)$ ja $(0,-2)$. See laine tagastab $4$ kaugust
\[ 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
