[Codeforces Round #507(Div.2)] [인터랙티브 문제] [2점 예측] Subway Pursuit[기차 예측]

Description:
This is an interactive problem.
In the Wonderful Metropolis of the Future, there is no need in subway train drivers. Due to the technological progress, they were replaced by the Artificial Intelligence (AI). Unfortunately, one day the predictions of sci-fi writers came true: the AI rebelled and now there is an uncontrollable train in the subway. It can be dangerous! Your task is to find the train and stop the AI.
The subway of the Metropolis is one line (regular straight line with no self-intersections) with nn stations, indexed consecutively from 11 to nn. At each moment the train is at some station. You need to determine the index of this station, so that the train would be secured.
To find the train, dispatcher Sarah gave you a gadget that allows you to select arbitrary numbers ll and rr (l≤rl≤r), and then check, whether the train is located on a station with index between ll and rr, inclusive. Unfortunately, recharging of the gadget takes some time (and every time you use it as soon as possible), so between two applications of the gadget the train can move to any station that is at most kk stations away. Formally, if the train was at the station xx when the gadget was applied, then at the next application of the gadget the train can appear at any station yy such that max(1,x−k)≤y≤min(n,x+k)max(1,x−k)≤y≤min(n,x+k).
Note that AI is not aware that you are trying to catch the train, so it makes all moves according to its predefined plan.
After an examination of the gadget you found that it is very old and can hold no more than 45004500 applications, after which it will break and your mission will be considered a failure.
Can you find the station with the train using no more than 45004500 applications of the gadgets?
Input:
The first line contains two integers nn and kk (1≤n≤10181≤n≤1018, 0≤k≤100≤k≤10) — the number of stations and the maximum number of stations the train can move between two applications of the gadget.
Interaction:
You can apply the gadget at most 45004500 times. In order to apply the gadget you need to print two space-separated integers ll and rr (1≤l≤r≤n1≤l≤r≤n). You will then receive either string "Yes", if the train is between stations ll and rr, inclusive, or string "No"otherwise. If l=rl=rand you received "Yes", then you found the train successfully, and your program must halt immediately.
Answer "Bad"instead of "Yes"or "No"means that you made an invalid query or made too many queries. Exit immediately after receiving "Bad"and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.
After printing a query do not forget to output end of line and flush the output. Otherwise you will get Idleness limit exceeded. To do this, use:

fflush(stdout) or cout.flush() in C++;

System.out.flush() in Java;

flush(output) in Pascal;

stdout.flush() in Python;

see documentation for other languages.

 
제목:
기차 한 대가 지하철 노선에서 마구 뛰어다니며, 너는 그의 위치를 예측할 수 있으며, 시스템이Yes나No로 돌아올 것이다.
만약에 구간(l, r)을 입력하고 시스템이 Yes로 돌아간다면 다음 초에 기차가 (l-k, r+k) 구간에 나타날 것이다. 구간(x, x)을 물어보고 시스템이 Yes로 돌아갈 때만 이 문제를 통과할 수 있다. 4500팀의 문의에서 기차를 잡아야 한다. 그렇지 않으면 이 문제를 통과하지 못한다.
 
아이디어:
이것은 전형적인 상호작용 문제로 출력 형식에 주의해야 한다.
이 문제의 사고방식도 매우 간단하다. 바로 끊임없이 2점, 2점을 받을 때 구간을 확대해야 한다.
예를 들어 내가 2분(1,n)이라는 구간을 입력하고 (l,mid)구간을 입력한 다음에 시스템이Yes로 돌아오면 다음에 내가 2분의 구간이 (l-k,mid+k)이다.만약 시스템이 No로 되돌아온다면, 다음에 나는 2분의 구간을 (mid+1-k, r+k)으로 바꾸어야 한다.
 
k가 존재하기 때문에 구간의 길이는 시종 2*k보다 크다. 따라서 구간의 길이가 특정한 값보다 작을 때 우리는 이 구간 중의 특정한 수를 무작위로 추출하여 추측해야 한다. 만약에 틀리면 아까 구간으로 돌아가 계속 예측해야 한다.
그래서 하나의 확률 문제가 되었다. 구간의 길이가 맞출 확률을 결정한다. 여기서 나는 4*k를 선택했다. 나는 5*k도 통과할 수 있다는 것을 발견했다. 모두가 스스로 시도할 수 있다.
 
여기서 주의해야 할 문제가 하나 더 있습니다. 구간 내의 무작위 숫자를 추측할 때 저는 처음에 직접 선택한 구간의 중간 노드를 발견했는데 최대 99 또는 100까지만 wa할 수 있다는 것을 발견했습니다. 어쩔 수 없이 ac를 했습니다. 제가 rand 무작위로 바꿨을 때 AC가 되었습니다.이곳에서도 여러분들이 직접 시도해 보실 수 있습니다. [현학 상호작용 문제]
 
형식 문제:
상호작용 문제 형식은 캐시 영역을 비워야 하기 때문에 printf 출력이 끝난 후에 한 줄의 fflush(stdout)를 추가할 수 있습니다.직접 cout<
 
코드:

#include 
#include 
#include 
#include 
#include 
#include 
#define rep(i,a,b) for(int i = a;i <= b;i++)
using namespace std;
typedef long long ll;

ll n,k;
char s[10];

int main()
{
	srand(time(0));
//	scanf("%lld%lld",&n,&k);
	cin>>n>>k;
	ll l = 1, r = n;
	while(1)
	{
		if(r-l <= (ll)5*k)
		{
			ll ran=rand()%(r-l+1)+l;
			cout<>s;
			if(s[0] == 'Y' || s[0] == 'B') return 0;
			else{
				l = max(1ll,l-2*k);
				r = min(n,r+2*k);
			}
		}
		else{
			ll mid = (l+r)>>1;
			cout<>s;
			if(s[0] == 'B') return 0;
			else if(s[0] == 'Y'){
				l = max(1ll,l-k);
				r = min(n,mid+k);
			}	
			else{
				l = max(1ll,mid+1-k);
				r = min(n,r+k);
			}
		}
	}
	return 0;
}