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:
-
Skapa listan $L = [x_1, x_2, \dots , x_ N, v]$.
-
Sortera $L$.
-
Skapa listan $D$, där $D_ i = L_{i+1}-L_ i$ för alla $i = 1, 2, \dots , N$.
-
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
