Problem B
Mineral deposits
Languages
da
de
en
et
fi
lt
lv
pl
uk
Ви займаєтеся обробкою сигналів для компанії з видобутку космічних руд, а Ваше судно наразі підходить до астероїда. Попередні сканування показують наявність $k$ родовищ мінералів на астероїді, але їх точні місця невідомі.
Поверхня астероїда може бути описана сіткою цілих координат. Кожне мінеральне родовище знаходиться в невідомих цілих координатах, таких що $i$-те родовище має координати $(x_ i, y_ i)$ з обмеженнями $-b \le x_ i \le b$ та $-b\le y_ i \le b$ для деякого цілого числа $b$, яке відповідає розміру Вашого початкового сканування.
Для визначення точних координат мінеральних родовищ Ви можете відправляти зонди на поверхню астероїда. Зонди відправляються хвилею з декількох зондів одночасно.
Припустимо, що Ви відправили хвилю з $d$ зондів на поверхню з координатами $(s_ j,t_ j)$ для $1\leq j\leq d$. Коли зонд досягає своїх координат, він визначає Манхеттенські відстані до кожного з $k$ мінеральних родовищ і відправляє відстані на судно. Усі пакети даних надходять одночасно, і неможливо визначити, який зонд повернув які відстані. Таким чином, хвиля повертає $k\cdot d$ цілих відстаней
\[ |x_ i-s_ j| + |y_ i - t_ j| \qquad \text {для всіх } i \in \{ 1,\ldots ,k\} \text { and } j \in \{ 1,\ldots ,d\} \, . \]Вам потрібно зменшити кількість хвиль зондів, що відправляються на поверхню.
Взаємодія
Це інтерактивна задача. Взаємодія починається з того, що Ви отримуєте один рядок, який містить три цілих числа $b$, $k$ і $w$: межу сітки $b$, кількість мінеральних родовищ $k$, та максимальну кількість $w$ хвиль, які ви можете відправити.
Далі Ви можете задати не більше, ніж $w$ запитів, кожен з яких відповідає хвилі зондів. Запит складається з ?, за яким слідують $2d$ цілих чисел, розділених пробілом, таких як «? $s_1$ $t_1$ $\cdots $ $s_ d$ $t_ d$», де кількість зондів у цій хвилі, $d$, повинна задовольняти $1\leq d\leq 2000$. Значення $(s_ i,t_ i)$ трактуються як координати $i$-го зонда і повинні задовольняти $-10^8 \leq s_ i \leq 10^8$ і $-10^8 \leq t_ i \leq 10^8$. Відповідь є одним рядком з $k \cdot d$ цілих чисел у неспадаючому порядку: всі пари Мангетенських відстаней між мінеральними родовищами та координатами зонда. Загальна кількість зондів у всіх хвилях не може перевищувати $2\cdot 10^4.$
Взаємодія закінчується, коли Ви виводите один рядок, що складається з !, за яким слідують $k$ точок $x_1, y_1, x_2, y_2, \ldots x_ k, y_ k$, розділені пробілом. Це має бути останнім рядком виводу.
Рішення вважатиметься правильним, якщо Ви виведете всі місця розташування мінеральних родовищ. Ви можете виводити їх у будь-якому порядку.
Обмеження та оцінювання
Ми завжди маємо: $1\leq b \leq 10^8$, $1 \leq k \leq 20$, та $2 \le w \le 10^4$.
Ваше рішення буде перевірено на наборі тестових груп, кожна з яких має свою кількість балів. Кожна група тестів містить набір тестових прикладів. Щоб отримати бали за групу тестів, потрібно розв’язати всі тестові приклади в цій групі. Ваш кінцевий бал буде максимальним балом, який Ви отримали за одне відправлення.
|
Група |
Бали |
Обмеження |
|
$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$ |
Немає додаткових обмежень |
Приклад
![\includegraphics[width=.6\textwidth ]{img/sample1.pdf}](/problems/boi23.mineraldeposits/file/statement/uk/img-0002.png)
У цьому прикладі є $k=2$ мінеральні родовища в позиціях $(1,2)$ та $(-3,-2)$, показаних червоними зірочками. У першій хвилі Ви можете надіслати $d=3$ зонди до $(-4,-3)$, $(-1,0)$ та $(2,-1)$, показаних чорними крапками. Ця хвиля поверне $6$ відстаней:
\[ 2, 4, 4, 4, 6, 10\, . \]У наступній хвилі ви можете надіслати $d=2$ зонди до $(1,2)$ та $(0,-2)$. Ця хвиля поверне $4$ відстані:
\[ 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
