[Codeforces] Codeforces Round #534 (Div. 2) D. Game with modulo
問題
https://codeforces.com/contest/1104/problem/D方針
題意
数字 \( a (1 \leq a \leq 10^9)\) を当てるリアクティブ問題です。整数 \(x, y\) を質問として返ってくる答えは、
-
\( x \mod a \leq y \mod a\)
-
\( x \mod a < y \mod a \)
となります。この答えを元に \( a \) を当てます。また、質問の回数は \( 100 \) 回を超えてはいけません。
区間の検討
\( f(x) = x \mod a \) という関数を考えると、\( k \) を整数として、\( [ak, a(k + 1) – 1] \) の区間で単調増加となります。
次に、\(x < y\) として質問をすることにします。\( y < a \) のとき、1. が必ず成り立ちます。一方で、2. が成り立つとき、\( a \leq y \) であるので、\( a \) の上限が分かります。どのような状況のとき\( a \) の上限が分かるかを考えます。
\( i \) 回目の質問を \( x_i, y_i \) として、\(x_1 = 0, y_1 = 1 \)、\( x_2 = 1, y_2 = 2\) とします。
区間の値を増加させて質問していったときに、初めて 2. が成り立つときが \( a \) の上限が分かります。このとき、区間に \( a \) と \( 2a\) が入らないように注意しなければなりません。したがって、
\[x_i = 2x_{i -1}, y_i = 2y_{i – 1} (i \geq 3) \]
のように区間を決めればよいです。2. が始めて成り立つ区間を \( [l, r]\) とすると、\( l < a \leq r\) が成り立ちます。
二分探索
区間が求まれば、あとは二分探索を行います。この部分は年齢当てゲームと殆ど同じだと思います。\( m = l + \dfrac{r – l}{2} \) として、新しい区間を \( [m, r] \) とします。このとき答えが 1. であれば区間の更新を \( r = m \) とし、そうでなければ、\( l = m \) とします。
https://codeforces.com/contest/1104/submission/54791830