Problem J
Gävlebocken 2

Ånej! Gävlebocken har brunnit ner! Och det är din uppgift att kolla igenom övervakningskamerorna för att hitta vem som gjorde det! Du har $30$ försök på dig kolla igenom övervakningskameran för att hitta tiden då Gävlebocken brann. För varje försök skriver du en tid (ett tal mellan $0$ och $N$). Övervakningssystemet kommer då svara med antingen ”Bocken finns kvar”, ”Bocken har brunnit” eller ”Bocken brinner nu!”. När du får svaret ”Bocken brinner nu!”, så har du lyckats hitta rätt tid! Undrar om personen som startade branden har fastnat på filmen eller om hen kom undan kamerorna...

Det finns bara en tid du kan gissa på som kommer ge svaret ”Bocken brinner nu!”. (Bonusfråga: hade din lösning ändrats ifall bocken brann över en längre tid?)

Interaktion

Det här är ett interaktivt problem.

Ditt program ska först läsa in talet $N$, antal tidsenheter som kameran har filmat. $N$ är antingen $30$, $225$ eller $10^9$.

Ditt program ska därefter upprepa som mest $30$ interaktioner enligt följande:

1. Skriv ut ett tal $i$ sådant att $0 \leq i < N$. Detta är din gissning för när bocken brann ner.

2. Läs in en rad. Raden kommer antingen innehålla Bocken finns kvar, Bocken har brunnit eller Bocken brinner nu! beroende på om tiden du gissar är före, efter eller medan Gävlebocken brann.

Efter att ha fått svaret Bocken brinner nu! ska ditt program avslutas direkt. Att skriva ut svaret räknas inte in i dina $30$ försök.

Se till att flusha outputen efter varje skrivning, annars kan du få Time Limit Exceeded.

• I C++ görs detta till exempel med cout << flush; eller fflush(stdout);.

• I Python görs det automatiskt när du använder input().

• I Java görs det med System.out.flush();.

• I C# görs det med Console.Out.Flush();.

Domaren (programmet som ditt program interagerar med) är adaptiv, vilket betyder att det ditt program läser in kan bero på vad ditt program skrev ut innan.

Poängsättning

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

30

3

Bocken finns kvar

27

Bocken har brunnit

23

Bocken har brunnit

13

Bocken brinner nu!