https://codeforces.com/contest/1040/problem/D
インタラクティブ問題
暴走列車が駅1から$N$の間のどこかにいる。区間を尋ねると、そのなかに暴走列車がいるかどうかを教えてくれる。ただし、一度質問するたびに暴走列車は最大$K$個の駅を移動することができる。
もし暴走列車が移動しないのであれば、二分探索で容易に答えを特定することができる。ただし実際は列車は移動するので、その分を考慮するとある程度までは二分探索で詰められるが、列車のいる可能性のある区間が$4K$になるとそれ以上縮められなくなる。そこで、ある程度まで縮めたら乱択で当てに行けばよい。質問は4500回可能であり、$K\leq10$なので確率的には余裕で当てられる。
方針はコンテスト中に立っていて実装もしたが、Codeforcesのインタラクティブの仕様がわかっていなかったせいでTLE以外のステータスを得ることができないままコンテストが終了した。結局、出力のflushがうまくできていなかったらしい(coutのあとにendl;をちゃんとやるのが大事)。コンテスト後にいくつかのバグが発覚したので、実際そこがうまくいっていてもACできていたかは不明。