Duša - Programme.lv

Stāsts

Karlsons ir iegādājies ļoti precīzu dušas temperatūras regulētāju, un tagad vēlas to izmēģināt. Regulētājam ir $N$ iedaļas, apzīmētas ar skaitļiem no $1$ līdz $N$ . Iedaļa $1$ atbilst temperatūrai $38^\circ C$ , iedaļa $N - 39^\circ C$ , un starp iedaļām temperatūra pieaug vienmērīgi.

Karlsonam patiks tikai viena temperatūra, kas atbildīs regulētāja iedaļai $X$ ( $1 \leq X \leq N$ ), kuru Karlsons pats vēl nezina. Ja dušā nonāk ūdens, kas atbilst:

iedaļai, kas mazāka par $X$ , ūdens šķiet ledains;
iedaļai, kas lielāka par $X$ , ūdens šķiet verdošs;
iedaļai, kas vienāda ar $X$ , ūdens ir patīkams.

Karlsons vēlas pēc iespējas ātrāk noskaidrot precīzo $X$ vērtību.

Duša darbojas ar aizturi: siltajam ūdenim nepieciešamas nedaudz vairāk kā $t$ sekundes, lai aizplūstu no temperatūras regulētāja līdz dušas uzgalim. Tātad, ja laika brīdī $T$ regulētājā uzstāda temperatūru $S$ , dušā ūdens ar temperatūru $S$ sāks tecēt neilgi (sekundes daļu) pēc laika brīža $T+t$ .

Iedaļas noskaidrošanas piemērs, N = 11, t = 3. Temperatūra, kas uzstādīta laika brīdī T = 5, tiek sajusta neilgi pēc laika brīža T = 5 + 3 = 8.

Karlsons drīkst mainīt iestatīto iedaļu katru sekundi (precīzi veselos laika brīžos $T = 0, 1, 2, 3, \ldots$ ).

Uzrakstiet datorprogrammu, kas zināmiem $N$ un $t$ nosaka nezināmo $X$ pēc iespējas ātrāk!

Komunikācija

Šis ir interaktīvs uzdevums. Jūsu programmai, sākot darbu, pirmā ievada rinda satur divus veselus skaitļus $N$ un $t$ $(1 \leq N \leq 10^9, \ 0 \leq t \leq 2000, \ t \leq N)$ . $X$ vērtību ( $1 \leq X \leq N$ ) vērtēšanas sistēma patur slepenībā.

Jūsu programma var veikt vaicājumus, tos rakstot izvadā sekojošā formātā: «? $S_i$ », kur $S_i$ ir naturāls skaitlis no $1$ līdz $N$ (ieskaitot). Sākot no vaicājuma ar kārtas numuru $t+1$ , pēc $i$ -tā vaicājuma ievadīšanas vērtēšanas sistēma atbild uz $(i-t)$ -to vaicājumu nākamajā ievada rindā:

Ja $S_{i-t} < X$ $\rightarrow$ atbilde ir $-1$
Ja $S_{i-t} > X$ $\rightarrow$ atbilde ir $1$
Ja $S_{i-t} = X$ $\rightarrow$ atbilde ir $0$

Kad pareizā $X$ vērtība ir noskaidrota, jūsu programmai jāizvada «! $X$ », kur $X$ - atbilstošā patīkamās temperatūras iedaļa. Vērtēšanas sistēmu uz šādu vaicājumu neatbildēs un nepieņems sekojošus vaicājumus.

Pamattestēšanas laikā sistēma $X$ vērtību var izvēlēties adaptīvi atkarībā no veiktajiem vaicājumiem.

Apakšuzdevumi un to vērtēšana

#	Apakšuzdevuma apraksts	Punkti
1.	$t=0$	6
2.	$N \leq 2t, \ t \neq 0$	6
3.	$N \leq t^2, \ t \neq 0$	12
4.	$t=1$	24
5.	$t \geq 2$	52

Apakšuzdevumu punktu summa = 100.

Piemērs

Vērtēšanas sistēma

Jūsu programma

Vērtēšanas sistēma:
```
11 3
```
Jūsu programma:
```
? 5
? 1
? 2
? 10
```
Vērtēšanas sistēma:
```
-1
```
Jūsu programma:
```
? 11
```
Vērtēšanas sistēma:
```
-1
```
Jūsu programma:
```
? 7
```
Vērtēšanas sistēma:
```
-1
```
Jūsu programma:
```
? 8
```
Vērtēšanas sistēma:
```
1
```
Jūsu programma:
```
? 3
```
Vērtēšanas sistēma:
```
1
```
Jūsu programma:
```
? 9
```
Vērtēšanas sistēma:
```
-1
```
Jūsu programma:
```
? 4
```
Vērtēšanas sistēma:
```
0
```
Jūsu programma:
```
! 8
```

Piezīmes

Lai garantētu, ka jūsu programmas "vaicājumus" saņem vērtēšanas sistēma, jums ir "jāsinhronizē" (flush) izvaddatu plūsma (stdout) pēc katra vaicājuma. Vairāk par datu ievadi un izvadi interaktīvajos uzdevumos lasiet šeit.