Problem D
Kvack

Men olyckligtvis har några av dem försvunnit! Ankorna har gömt sig i det höga gräset längs en linje, och gräset är så högt att Harry inte kan se var de befinner sig.

Det finns $N$ ankor som gömmer sig på heltalspositioner inom intervallet $[0, 10^9]$, där varje position kan innehålla högst en anka. Problemet är att Harry inte vet hur många ankor som är försvunna.

Harry har dock möjlighet att utföra följande handling upp till $Q$ gånger:

• Kvacka från en position: Harry kan ställa sig på en heltalsposition på linjen $[-10^9, 2 \cdot 10^9]$ och börja kvacka.

  • Den närmaste ankan kommer då att kvacka tillbaka, vilket låter Harry bestämma positionen för just den ankan.

  • Om det finns flera ankor som är lika nära, kommer den anka med den lägre koordinaten att kvacka tillbaka först.

  • Notera att ankorna inte rör sig eller försvinner efter att Harry har hittat dem; de stannar kvar på sina positioner tills alla ankor har identifierats.

Ditt uppdrag är att hjälpa Harry hitta alla ankor genom att bestämma antalet ankor som gömmer sig, samt ange de exakta positionerna för dessa ankor.

Figure 1: Den hemliga placeringen av de gömda ankorna i exempelfall 2.

Interaktion

Det här är ett interaktivt problem, där du kan ställa Harry på en heltalspostition inom intervallet $[-10^9,2\cdot 10^9]$ upp till $Q$ gånger. Notera att både $N$ och $Q$ är hemliga tal.

Ditt program börjar med att läsa in ett heltal $T$ ($1 \leq T \leq 7$), där $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 ställa Harry på en valfri heltalspostion $x_h$ inom intervallet $[-10^9,2\cdot 10^9]$. Du ställer frågan genom att skriva ut

Sedan ska ditt program läsa in ett heltal $x_a$, positionen av den närmaste ankan. Om ditt program inte avslutas kan du få felaktiga bedömningar som Run-Time Error.

Du får ställa ut Harry upp till $Q$ gånger. Men när du har hittat alla $N$ ankors positioner $x_1 \; x_2 \; x_3 \; \dots \; x_N$, ska du skriva ut två rader. Först en rad med ett utropstecken samt talet $N$, antalet ankor som gömmer sig:

Sedan ska du skriva ut en ny rad med $N$ heltal, postionerna av de $N$ ankorna i valfri ordning:

Därefter ska ditt program avslutas, och inget mer ska skrivas ut.

Se till att flusha outputen efter varje utskrivning, annars kan du få Time Limit Exceeded. I C++ kan detta göras med exempelvis cout << flush; eller fflush(stdout);, i Python görs detta automatiskt när du använder input(), men annars behöver man använda sys.stdout.flush(), och i Java med System.out.flush();.

Notera även att om ditt program skriver ut ett ogiltigt tal, alternativt felaktigt svar, kommer du få bedömningen som Wrong Answer, om inget annat händer innan det som kan påverka din bedömning.

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.

Förklaring av exempelfall 2

Enligt interaktionen så ställer programmet först Harry på position $1$ och kvackar. Detta följs av att programmet får reda på att ankan närmast position $1$ är ankan vid position $0$.

Sedan ställer programmet Harry på position $4$ och kvackar. Programmet får då reda på att ankan närmast position $4$ är en anka som också befinner sig på position $4$.

Efter det ställer programmet Harry på position $9$ och kvackar. Programmet får då informationen om att ankan närmast position $9$ är en anka som befinner sig på position $10$.

Därefter testar programmet att ställa Harry på position $2$ och kvackar. Notera att det finns $2$ olika ankor som befinner sig på samma avstånd till Harry i det här fallet. Men programmet får endast veta om ankan med det lägre positionen, i detta fall ankan vid position $0$.

Tillslut antar programmet att alla ankor är hittade, och skriver därför ut svaret.

0

? 1000

100

? 10000

10000

! 2
100 10000

0

? 1

0

? 4

4

? 9

10

? 2

0

! 3
10 0 4