http://arc078.contest.atcoder.jp/tasks/arc078_c
まず桁数を特定する。これは1, 10, 100,...と比較するとわかる。
それからは上の位から数字を特定していく。
例えば(10^3,10^4)の区間において49990を投げると、
(10^3,5*10^3)でyes,[5*10^3,10^4)でNoとなる。
同じようなことをにぶたんで行えば各桁が4回の質問で求められるので、64回の制限を余裕で満たす。
下のコードは自分でもわけのわからず通したもの…
bool ok(ll res) { //char c = get_ans(res); cout << "? " << res << endl; char c; cin >> c; return c == 'Y'; } void solve() { ll res = 0; for(ll i = 0; i < 10; i++) { ll lv, rv = 10; if(i == 0) lv = 1; else lv = 0; while(rv - lv > 1) { ll m = (lv + rv) / 2; if(ok(res * 10 + m)) lv = m; else rv = m; } res = res * 10 + lv; //char c = get_ans(res + 1); cout << "? " << res + 1 << endl; char c; cin >> c; if((all_nine(res) && c == 'N') || (!all_nine(res) && c == 'Y')) { res -= 9; if(i == 0) lv = 0; else lv = -1; rv = 9; while(rv - lv > 1) { ll m = (lv + rv) / 2; if(ok(res * 10 + m * 10)) rv = m; else lv = m; } cout << "! " << res + rv << endl; return; } } cout << "! 1" << endl; }
文字列を比較するときは文字の長さを特定するのも重要だね。