Problem E
Minerālu atradnes
Languages
da
de
en
et
fi
lt
lv
pl
uk
Jūs pārvaldāt signālu apstrādi ārpuszemes kalnrūpniecības uzņēmumam, un jūsu kuģis pašlaik tuvojas asteroīdam. Sākotnējās izlūkošanās dati rāda, ka asteroīdā atrodas $k$ minerālvielu atradnes, bet to precīzas atrašanās vietas nav zināmas.
Asteroīda virsmu var uzskatīt par koordinātu režģi ar veselām koordinātēm. Katra minerālu atradne atrodas nezināmās veselās koordinātēs, kur $i$-tajai vietai ir koordinātas $(x_ i, y_ i)$ un $-b \le x_ i \le b$ un $-b\le y_ i \le b$ kādam veselam skaitlim $b$, kas atbilst jūsu sākotnējās izlūkošanās izmēram.
Lai noteiktu minerālu atradņu precīzas atrašanās vietas, jūs varat sūtīt zondes uz asteroīda virsmas. Zondes tiek sūtītas viļņos no vairākām zondēm vienlaikus.
Pieņemsim, ka jūs nosūtījāt vilni ar $d$ zondēm uz virsmas koordinātēm $(s_ j, t_ j)$ katram $1\leq j\leq d$. Kad zonde sasniedz savas koordinātes, tā nosaka Manhetenas attālumus līdz katrai no $k$ minerālu atradnēm un nosūta attālumus atpakaļ uz kuģi. Visi dati no zondēm tiek saņemti uz kuģa vienlaikus, un nav iespējams noteikt, kuras zondes nosūtīja kurus attālumus. Tādējādi viens vilnis atgriež $k\cdot d$ veselus attālumus
\[ |x_ i-s_ j| + |y_ i - t_ j| \qquad \text {visiem } i \in \{ 1,\ldots ,k\} \text { un } j \in \{ 1,\ldots ,d\} \, . \]Jums nepieciešams minimizēt zonžu viļņu skaitu, kas ir nosūtīti uz virsmas pārbaudi.
Komunikācija
Šis ir interaktīvs uzdevums. Komunikācija sākas, kad nolasāt vienu rindu ar trīs veseliem skaitļiem $b$, $k$ un $w$: režģa robeža $b$, minerālu atradņu skaits $k$ un maksimālais viļņu skaits $w$, ko jūs drīkstat nosūtīt.
Pēc tam jūs uzdodat ne vairāk kā $w$ vaicājumus, kur katrs atbilst vienam vilnim. Vaicājums sastāv no simbola ?, kuram seko $2d$ veseli ar atstarpi atdalīti veseli skaitļi, piemēram “? $s_1$ $t_1$ $\cdots $ $s_ d$ $t_ d$”, kur zonžu skaitam $d$ šajā vilnī jāapmierina $1\leq d\leq 2000$. Vērtības $(s_ i, t_ i)$ tiek interpretētas kā $i$-tās zondes koordinātas un tām jāapmierina $-10^8 \leq s_ i \leq 10^8$ un $-10^8 \leq t_ i \leq 10^8$. Atbilde uz vaicājumu ir viena rinda ar $k \cdot d$ veseliem skaitļiem augošā secībā: visi Manhetenas attālumi starp minerālu atradnēm un zonžu koordinātām. Kopējais zonžu skaits visos viļņos kopā nedrīkst pārsniegt $2\cdot 10^4$.
Komunikācija beidzas ar to, ka jūs izdrukājat vienu rindu, kas sastāv no !, pēc kuras seko $k$ punkti $x_1$, $y_1$, $x_2$, $y_2$, $\ldots $, $x_ k$, $y_ k$, kas ir atdalīti ar atstarpi. Šai jābūt jūsu izvada pēdējai rindai.
Jūsu risinājums tiks uzskatīts par pareizu, ja jūs izvadīsiet visas minerālu atradņu atrašanās vietu koordinātas. Jūs varat tās izdrukāt jebkurā secībā.
Ierobežojumi un vērtēšana
Vienmēr izpildās ierobežojumi $1\leq b \leq 10^8$, $1 \leq k \leq 20$, un $2 \le w \le 10^4$.
Jūsu risinājums tiks pārbaudīts uz vairākām testu grupām. Katra grupa ir vērta noteiktu punktu skaitu. Katra testu grupa satur vairākus testus. Lai saņemtu punktus par testu grupu, ir jāatrisina visi testi testu grupā. Jūsu gala rezultāts būs lielākais punktu skaits, kas iegūts ar vienu risinājuma iesniegumu.
|
Grupa |
Punkti |
Ierobežojumi |
|
$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$ |
Bez papildu ierobežojumiem |
Piemērs
![\includegraphics[width=.6\textwidth ]{img/sample1.pdf}](/problems/boi23.mineraldeposits/file/statement/lv/img-0002.png)
Šajā piemērā ir $k=2$ minerālu atradnes, kas atrodas pozīcijās $(1,2)$ un $(-3,-2)$, attēlotas ar sarkanām zvaigznītēm. Pirmajā vilnī jūs varētu sūtīt $d=3$ zondes uz $(-4,-3)$, $(-1, 0)$ un $(2,-1)$, kas ir attēlotas kā melni punkti. Šis vilnis atgrieztu $6$ attālumus
\[ 2, 4, 4, 4, 6, 10\, . \]Nākamajā vilnī jūs varētu sūtīt $d=2$ zondes uz $(1,2)$ un $(0,-2)$. Šī vilnis atgrieztu $4$ attālumus
\[ 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
