Hide

Problem E
Sågverket

Alma har en massa brädor som hon vill såga i bitar. Hon har därför gått till ett toppmodernt sågverk som automatiskt sågar itu och sorterar brädor. Varje bräda kan representeras av en oändligt lång $x$-axel, och sågverket kommer såga av brädan vid de $N+1$ positionerna

\[ x_1, x_2, \dots , x_ N, v \]

där $v$ är ett tal som användaren får välja. Därefter sorteras alla ändligt långa bitar och matas ut av sågverket. Alma vill ha reda på talen $x_1, x_2, \dots , x_ N$, men det verkar som att ingen vet hur sågverket ser ut på insidan. Så istället tänker hon lista ut talen genom att mata in några brädor med väl valda värden $v$.

Det finns $N$ hemliga heltal $x_1 < x_2 < \dots < x_ N$ mellan $1$ och $10^9$. Notera att alla dessa tal är olika. Ditt mål är att hitta talen. Du får skicka brädor till sågverket. Sågverket tar ett heltal $v$ som input ($1 \leq v \leq 10^9$), och gör följande:

  1. Skapa listan $L = [x_1, x_2, \dots , x_ N, v]$.

  2. Sortera $L$.

  3. Skapa listan $D$, där $D_ i = L_{i+1}-L_ i$ för alla $i = 1, 2, \dots , N$.

  4. Sortera $D$, och returnera de $N$ talen i $D$.

Du får skicka högst $N$ brädor, förutom i testgrupp $4$ där du får skicka $N+1$ brädor.

Interaktion

Ditt program ska först läsa in två heltal $N$ och $T$ ($1 \leq N \leq 1000$, $1 \leq T \leq 5$). $N$ är antalet hemliga tal du ska hitta, och $T$ är numret på testgruppen. Anledningen till att $T$ är givet i input är för att göra det lättare att ta delpoäng.

Därefter får du börja skicka brädor. Skriv ut en rad med “? v” för att skicka en bräda med talet $v$ till sågverket. Talet $v$ måste uppfylla $1 \leq v \leq 10^9$. Sedan ska ditt program läsa in $N$ heltal på en rad, talen $D_1, D_2, \dots , D_ N$. Notera att $D_1$ kan vara noll, ifall $v$ var lika med ett av talen $x_ i$.

När du har hittat talen $x_1, x_2, \dots , x_ N$ ska du skriva ut en rad på formen

\[ ! \; x_1 \; x_2 \; x_3 \; \dots \; x_ N \]

Därefter ska ditt program avsluta och inte skriva ut något mer.

Se till att flusha outputen efter varje query, annars kan du få Time Limit Exceeded. I C++ kan detta göras med exempelvis cout << flush eller fflush(stdout); i Python med stdout.flush(); och i Java med System.out.flush().

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Gränser

$1$

$15$

$N = 1$

$2$

$15$

$N = 2$

$3$

$11$

$x_ i \leq N+1$

$4$

$37$

$N \leq 100$, $x_ i \leq 10^4$, du får skicka högst $N+1$ brädor.

$5$

$22$

Inga ytterligare begränsningar

Read Sample Interaction 1 Write
 2 2
 ? 5
 3 3
 ? 10
 2 6
 ! 2 8

Please log in to submit a solution to this problem

Log in