Uzmini skaitli!

Uzmini skaitli!

4
Latvijas Informātikas olimpiādes logo

Uzdevums no 2024. g. LIO skolas kārtas.

Stāsts

Dators "ir iedomājies" naturālu skaitli XX robežās no 11 līdz NN.

Skaitļa XX atminēšanai Jūsu programma var veikt vaicājumus. Katrs vaicājums ir formā "Vai iedomātais skaitlis ir KK?", kur 1≤K≤N1 \leq K \leq N, un uz katru šādu vaicājumu dators dod vienu no trim atbildēm:

  • 11, ja K<XK < X,
  • 00, ja K=XK = X,
  • −1-1, ja K>XK > X.

Skaitlis XX ir uzminēts tikai tad, ja ir izdarīts vaicājums uz kuru saņemta atbilde 00.

Katram vaicājumam ir noteikta maksa – ja vaicājumā izmatots skaitlis KK, tad maksa par šādu vaicājumu ir KK eirocenti.

Uzrakstiet datorprogrammu, kas atrod skaitli XX, iztērējot ne vairāk kā 34003400 eirocentus!

Komunikācija

Šis ir interaktīvs uzdevums. Jūsu programmai, sākot darbu, pirmā ievada rinda satur veselu skaitli NN (1≤N≤500)(1 \leq N \leq 500). Iedomātā skaitļa vērtību XX vērtēšanas sistēma tur slepenībā. Tad jūsu programma var veikt vaicājumus, izvadā rakstot vērtību KK (1≤K≤N)(1 \leq K \leq N). Vērtēšanas sistēma izdod atbildi nākamajā ievada rindā. Atbilde ir vesels skaitlis – −1,0-1, 0 vai 11, kā aprakstīts iepriekš. Jūsu programma katrā testā var veikt ne vairāk kā NN vaicājumus un nedrīkst iztērēt vairāk par 34003400 eirocentiem. Kad uz vaicājumu tiek izdota atbilde 00, jūsu programmai darbs jābeidz.

Apakšuzdevumi un to vērtēšana

#Apakšuzdevuma aprakstsPunkti
1.

N≤5N \leq 5

10
2.

N≤80N \leq 80

10
3.

N≤400N \leq 400

40
4.

Bez papildu ierobežojumiem

40
Apakšuzdevumu punktu summa = 100.

Piemērs

Vērtēšanas sistēma

Jūsu programma

  1. Vērtēšanas sistēma:
    6
  2. Jūsu programma:
    3
  3. Vērtēšanas sistēma:
    1
  4. Jūsu programma:
    5
  5. Vērtēšanas sistēma:
    -1
  6. Jūsu programma:
    4
  7. Vērtēšanas sistēma:
    0

Piezīme

Pievērsiet uzmanību, ka, lai gan jau pēc otrā vaicājuma kļuva skaidrs, ka XX vērtība ir 44, nācās veikt vēl trešo vaicājumu, lai saņemtu atbildi 00. Šajā piemērā aprakstīto vaicājumu kopējās izmaksas bija 3+5+4=123 + 5 + 4 = 12 eirocenti.

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.