https://codeforces.com/contest/1114/problem/E
インタラクティブ問題。
初項X0, 交差D, 項数Nの数列がある。
この数列がランダムな順で入った配列Aがある。
項数Nの情報と、以下のクエリを60回以下行うことで、X0,Dを見つけよ。
操作1 : 「? i」A[i]の要素を答える
操作2 : 「> x」xより大きい要素が存在するか答える
2≦N≦10^6
0≦x, A[i]≦10^9
前提知識
解説
https://codeforces.com/contest/1114/submission/49735909
まずは二分探索を使って、数列の最大項を求めよう。
これは31回かかる（30回かも。よくわからないね）
次に交差を探すのだが、乱択アルゴリズムを使おう。
適当に29回操作1をして29個の項を得る。
目的の交差は得た項の差の約数のどれかになっているはずである。
なので、得た項の全ての差の最大公約数を取る。
すると、これが交差になっている（らしい）。
数学的な背景は全くわからないが、確かにこれで解くしかなさそうだし、twitterでもこのような情報が流れている。
最大項maと交差dが分かれば、初項はma - d * (N-1)なので、答えが求まった。
注意点が色々あるので注意
- 悪い乱数生成器を使うと通らない
- クエリの数は[0,10^9]にする必要がある
int debug = 0; int N; int a[1010] = { 14,24,9,19 }; int ma = -1; //--------------------------------------------------------------------------------------------------- int ask1(int i) { printf("? %d\n", i + 1); fflush(stdout); if (debug) return a[i]; int r; cin >> r; return r; } int ask2(int x) { printf("> %d\n", x); fflush(stdout); if (debug) return x < ma; int r; cin >> r; return r; } void answer(int x, int d) { printf("! %d %d\n", x, d); fflush(stdout); } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; int ok = 0, ng = 1000000001; while (ok + 1 != ng) { int md = (ok + ng) / 2; if (ask2(md)) ok = md; else ng = md; } int ma = ng; vector<int> v; rep(i, 0, N) v.push_back(i); vector<int> w; w.push_back(ma); rep(i, 0, min(29,N)) { int j = getrand(0, N - 1 - i); int x = ask1(v[j]); w.push_back(x); swap(v[j], v[N - 1 - i]); } int g = 0; fore(x, w) fore(y, w) g = gcd(g, abs(x - y)); int ans1 = ma - g * (N - 1); int ans2 = g; answer(ans1, ans2); }
