Hide

Problem B
Mineral deposits

Languages da de en et fi lt lv pl uk
/problems/boi23.mineraldeposits/file/statement/uk/img-0001.jpg
Eroding mud face exposing new minerals. Photo: Michael D. Turnbull, licence: CC BY-SA.

Ви займаєтеся обробкою сигналів для компанії з видобутку космічних руд, а Ваше судно наразі підходить до астероїда. Попередні сканування показують наявність $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}

У цьому прикладі є $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