Problem B
Mineral deposits
Languages
da
de
en
et
fi
lt
lv
pl
uk
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
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