yukicoder - No.643
No.643 Two Operations No.2
逆の操作を考える.つまり $(X, Y) = (a, a)$ から出発して,
操作 1' : $X = Y', \ \ Y = X'$
操作 2' : $\displaystyle X = \frac{ X' + Y' }{ 2 }, \ \ Y = \frac{ X' - Y' }{ 2 }$
によって遷移する状態を図に書く.
同じ状態の繰り返しや $\pm 4/a$ が出てくる遷移は省いた.これを見ると結局 $X = Y$ とできるのは
$(X, Y) = (a, a), (a, 0), (0, a), (a, -a)$
の 4 パターンに限られることがわかる.それぞれのパターンにおける最小ステップ数は
$(a, a)$ : 0 step
$(a, 0) \rightarrow (a, a)$ : 1 step (操作 2)
$(0, a) \rightarrow (a, 0) \rightarrow (a, a)$ : 2 step (操作 1 → 操作 2)
$(a, -a) \rightarrow (0, 2a) \rightarrow (2a, 0) \rightarrow (2a, 2a)$ : 3 step (操作 2 → 操作 1 → 操作 2)
となる.あとは editorial に書いてある通りの結果を得る.
#include "bits/stdc++.h" using namespace std; int main() { int X, Y; cin >> X >> Y; int ans = -1; if (X == Y) ans = 0; else if (Y == 0) ans = 1; else if (X == 0) ans = 2; else if (X == -Y) ans = 3; cout << ans << endl; return 0; }
No.642 - Two Operations No.1 も合わせていい問題だった.