//表 - 裏を描いてみるが、色々なケースを考えると混乱するので、場合分けによって単純化する。 //f(k) = 上からk枚における表の枚数 - 裏の枚数 とおく。 //まず1枚目とN枚目が異なる向きになる条件とf(1) = f(N - 1)は同値であり、このときは2~N-1枚目を取ればよい。 //1枚目もN枚目も表の場合、f(1) = 1, f(N - 1) = -1であり、 //|f(i) - f(i+1)| = 1が任意のiで成り立つので、f(k) = 0なるk(2~N-2)が存在する。 //これは2分法によって1つ求めることができて、カード1~k or カードk+1~Nのどちらかは条件を満たす。 //1枚目もN枚目も裏の場合は、fの値を反転して解けばよい。 #include using namespace std; int f(int k) { cout << "? " << k << endl; cout.flush(); int s; cin >> s; return s - (k - s); } int main() { int n; cin >> n; int a = f(1); int b = f(n - 1); if (a == b) { cout << "! 2 " << n - 1 << endl; return 0; } bool hanten = (a < 0); int l = 1, r = n - 1, mid; //[l, r)の中にf(k) = 0なるkが存在する while (r - l >= 2) { mid = (l + r) / 2; int res = f(mid) * (hanten ? -1 : 1); if (res >= 0) l = mid; else r = mid; } //f(l) = 0. if (l >= n / 2) { cout << "! 1 " << l << endl; } else { cout << "! " << l + 1 << " " << n << endl; } return 0; }