解説
最初に以下の質問をします。
- は 以上 以下の整数か。
これは明らかに真であり、0 と返されたならばジャッジは嘘つきです。
嘘つきの場合、以降は応答を逆の意味で受け取ればよいです。
残るは典型問題であり、二分探索で効率的に求めることができます。
二分探索では より高々 回質問すれば特定でき、最初の質問と合わせても 回以内に収まります。よって、この問題を解くことができました。
実装例(C++):
#include <bits/stdc++.h>
using namespace std;
int main(){
int N;
cin >> N;
cout << "? " << 1 << " " << N << endl;
int res;
cin >> res;
bool liar = false;
if(res == 0){ // 嘘つき確定
liar = true;
}
int left = 1, right = N;
while(left < right){
int mid = (left + right) / 2;
cout << "? " << left << " " << mid << endl;
cin >> res;
if(liar) res ^= 1; // 01を反転
if(res == 1){
right = mid;
} else {
left = mid + 1;
}
}
cout << "! " << left << endl;
return 0;
}
ユーザー解説
ユーザー解説を書くユーザー解説はまだありません。