絶滅

どうでもいい

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 }$

によって遷移する状態を図に書く.

f:id:my316g:20180214030433p:plain

同じ状態の繰り返しや $\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 も合わせていい問題だった.