Hide

Problem E
Mineral deposits

Languages da de en et fi lt lv pl uk
/problems/boi23.mineraldeposits/file/statement/pl/img-0001.jpg
Erodująca ściana błota odsłaniająca nowe minerały. Zdjęcie: Michael D. Turnbull, licencja: CC BY-SA.

Zajmujesz się przetwarzaniem sygnałów dla pozaziemskiej firmy wydobywczej, a Twój statek właśnie zbliża się do asteroidy. Wstępne skany wskazują na obecność $k$ złóż minerałów na asteroidzie, ale ich dokładne lokalizacje nie są znane.

Powierzchnia asteroidy może być postrzegana jako siatka współrzędnych całkowitych. Każde ze złóż minerałów znajduje się w nieznanych współrzędnych całkowitych, tak że $i$-te złoże ma współrzędne $(x_ i, y_ i)$ spełniające $-b \le x_ i \le b$ oraz $-b\le y_ i \le b$ dla pewnej liczby całkowitej $b$ odpowiadającej rozmiarowi Twojego początkowego skanu.

Aby określić dokładne położenie złóż minerałów, możesz wysłać na powierzchnię asteroidy sondy. Sondy są wysyłane w falach po kilka sond jednocześnie.

Powiedzmy, że wysłałeś jedną falę $d$ sond na powierzchnię na współrzędne $(s_ j,t_ j)$ dla $1\leq j\leq d$. Kiedy sonda dociera do swoich współrzędnych, określa odległości w metryce Manhattan do każdego z $k$ złóż minerałów i wysyła odległości z powrotem na statek. Wszystkie pakiety danych docierają w tym samym czasie i nie jest możliwe określenie, które sondy zwróciły jakie odległości. Tak więc fala zwraca $k\cdot d$ odległości całkowitych

\[ |x_ i-s_ j| + |y_ i - t_ j| \qquad \text {dla każdego } i \in \{ 1,\ldots ,k\} \text { oraz } j \in \{ 1,\ldots ,d\} \, . \]

Musisz zminimalizować liczbę fal sond, które są wysyłane na powierzchnię.

Interakcja

Jest to problem interaktywny. Interakcja rozpoczyna się od wczytania ze standardowego wejścia pojedynczego wiersza zawierającego trzy liczby całkowite $b$, $k$ oraz $w$: granica siatki $b$, liczbę złóż minerałów $k$, i maksymalna liczba $w$ fal, które możesz wysłać.

Następnie zadajesz co najwyżej $w$ zapytań, każde odpowiadające jakiejś fali. Zapytanie składa się z ?, po którym następuje $2d$ liczb całkowitych oddzielonych spacją, na przykład “? $s_1$ $t_1$ $\cdots $ $s_ d$ $t_ d$”, gdzie liczba $d$ sond w tej fali musi spełniać wymagania $1\leq d\leq 2000$. Wartości $(s_ i,t_ i)$ są interpretowane jako współrzędne $i$-tej sondy i muszą spełniać $-10^8 \leq s_ i \leq 10^8$ oraz $-10^8 \leq t_ i \leq 10^8$. Odpowiedzią jest jeden wiersz zawierający $k \cdot d$ liczb całkowitych w kolejności niemalejącej: wszystkie pary odległości w metryce Manhattan pomiędzy złożami mineralnymi oraz współrzędnymi sondy. Całkowita liczba sond we wszystkich falach nie może przekroczyć $2\cdot 10^4.$

Interakcja kończy się wypisaniem pojedynczego wiersza składającego się ze znaku !, po którym następuje $k$ punktów $x_1, y_1, x_2, y_2, \ldots x_ k, y_ k$, oddzielone spacją. To musi być ostatni wiersz wypisany przez Ciebie na standardowe wyjście.

Twoje zgłoszenie zostanie uznane za poprawne, jeśli wypiszesz wszystkie lokalizacje złóż minerałów. Możesz je wypisać w dowolnej kolejności.

Ograniczenia i punktacja

Zawsze jest spełnione $1\leq b \leq 10^8$, $1 \leq k \leq 20$, oraz $2 \le w \le 10^4$.

Twoje rozwiązanie zostanie przetestowane na zestawie grup testowych, z których każda jest warta pewną liczbę punktów. Każda grupa testowa zawiera zestaw przypadków testowych. Aby uzyskać punkty za daną grupę testową należy rozwiązać wszystkie przypadki testowe w tej grupie. Twój ostateczny wynik będzie maksymalnym wynikiem pojedynczego zgłoszenia.

Grupa

Punkty

Ograniczenia

$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$

Brak dalszych ograniczeń

Przykład

\includegraphics[width=.6\textwidth ]{img/sample1.pdf}

W tym przykładzie, na pozycjach $(1,2)$ oraz $(-3,-2)$ znajdują się $k=2$ złoża mineralne, zareprezentowane jako czerwone gwiazdy. W pierwszym rzucie możesz wysłać $d=3$ sondy na pozycje $(-4,-3)$, $(-1, 0)$ oraz $(2,-1)$, zareprezentowane jako czarne kropki. Ta fala zwróciłaby $6$ odległości

\[ 2, 4, 4, 4, 6, 10\, . \]

W następnej fali można wysłać sondy $d=2$ do $(1,2)$ oraz $(0,-2)$. Ta fala zwróciłaby $4$ odległości

\[ 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