17/05/2024 08:36:50

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2019. Interactive Interception

Ограничения: время – 3s/6s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

This is an interactive problem.

North Eastern Emergency Rocket Control agency (NEERC) has developed a new radar control system that is designed to better control ballistic rocket interception. To test the new system NEERC agency had developed a mathematical model that is intended to show this system’s abilities.

Let us represent a rocket as a point on a line. Initially the point is at some unknown integer location between 0 and `p`, inclusive. It has some unknown speed of `q` which is an integer between 0 and `v`, inclusive. Each second the following happens. First, the control system makes a query to the radar of a form “`"check"(L,R)`” and gets an answer whether the point is currently between `L` and `R`, inclusive, or not. After that, the point’s coordinate increases by `q`.

The goal of the radar control system is to learn the exact location of the point at the beginning of some second. When it does learn the point’s location, then instead of making a query to the radar, it gives a command to intercept the point at that location.

You have to implement the control system that locates and intercepts the point while making at most 100 queries to the radar.

Interaction protocol

You must write function intercept with two integer parameters `p` and `v` (`1\ ≤\ p\ ≤\ 10^5`, `1\ ≤\ v\ ≤\ 10^5`).

int intercept(int p, int v)

Your function is allowed to perform one of the following two actions:

`"check"(L,R)` — make a query to the radar to get an answer whether the point is currently between `L` and `R`, inclusive, or not. The function return 0 or 1. After that the point’s coordinate is increased by `q`. `L` and `R` must be integers (`0\ ≤\ L\ ≤\ R\ ≤\ 10^9`). There must be at most 100 “check” calls.
`"return"\ x` — the exact coordinate x of the point is known, and you order to intercept the point.

Sample code

int intercept(int p, int v)
{ if(check(1,1)) return 1;
  else return 2;
}