#include<bits/stdc++.h> #include "prize.h" using namespace std; int find_best(int n) { int cnt = 0, id = 0, cnR = 0; for(int i = 0; i < min(n, 473); i++) { vector<int> v = ask(i); if(!v[0] && !v[1]) return i; if(cnt <= v[0] + v[1]) { cnt = v[0] + v[1]; cnR = v[1]; id = i; } } while(true) { int l = id + 1, r = n - 1, nxt = 0; while(l <= r) { int mid = (l + r) / 2; vector<int> v = ask(mid); if(!v[0] && !v[1]) return mid; if(v[0] + v[1] != cnt) { nxt = mid; r = mid - 1; continue; } if(v[1] == cnR) { l = mid + 1; } else r = mid - 1; } assert(nxt); id = nxt; while(true) { ++id; vector<int> v = ask(id); if(!v[0] && !v[1]) return id; if(v[0] + v[1] == cnt) break; } } }