BOJ 30762 Shall We Play a Game?

문제 링크입니다.

문제 요약

숨겨진 값 $n$을 어떤 $x$에 대한 ${\lfloor {n \over x} \rfloor} \over n$의 값을 묻는 것으로 찾아내야 합니다.

그런데 이제 $n$은 $10^{18}$ 이하고 질문 횟수 제한이 6번인.

이분 탐색?

${\lfloor {n \over x} \rfloor} \over n$의 값은 $x > n$이면 0이 됩니다. 이 점을 이용해 이분 탐색을 하면 60번의 질문으로 $n$의 값을 찾을 수 있습니다. 원본 문제에는 부분 점수가 있는데 BOJ에 이식되면서 없어졌습니다.

이분 이분 탐색?

$x$가 $n/2$를 초과하면 $\lfloor {n \over x} \rfloor$는 1이 됩니다. 이때의 분모가 $n$이겠네요.

우리의 목표는 $n/2$ 초과 $n$ 이하인 아무 $x$로나 이동하도록 매개 변수 탐색을 하는 것입니다.

$x \le n/2 < 2x \le n$임을 생각해보면, $x$를 적당한 2의 거듭제곱 꼴로만 선택해 줘도 필요한 값을 찾아낼 수 있습니다. 이를 구현하면 6번의 질문으로 $n$의 값을 찾을 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
	int g; cin >> g; while(g--){
		ll l = 0, r = 61, ans = 1;
		while(l < r){
			ll mid = l+r>>1;
			ll x = min(1'000'000'000'000'000'000LL, 1LL<<mid);
			cout << "X " << x << endl;
			ll bunza, bunmo; cin >> bunza >> bunmo;
			if(bunza){
				l = mid+1;
				ans = bunmo;
			}
			else r = mid;
		}
		cout << "N " << ans << endl;
		string dummy; cin >> dummy;
	}
}