読者です 読者をやめる 読者になる 読者になる

Codeforces Round #370 (Div. 2) C. Memory and De-Evolution

問題

codeforces.com

考察

前提として、三角形になるのは辺の長さが「最小 + 2番目 > 最大」という状態です。

3番目のサンプルにあるように、単純に「初手はなるべくyに近づける」という手法では上手くいきません。
減らす上限を固定しても上手くいかなさそうですし、途中に正三角形が現れないパターンもあるのでDPのような何かもできなさそうです。

そこで、答えから逆算して考えてみます。
3番目のサンプルで考えると、(7, 4, 4)は後1回で答えになります。
同様に、(7, 10, 4)は1回で↑の状態になります。

式っぽくすると、(最小の要素) = (2番目) + (3番目) - 1 という処理を繰り返しています。
これにより、常に条件を満たしつつギリギリの移動ができます。

このような処理を繰り返し、全ての要素がxを上回ったらそこまでの回数が答えです。
最小の要素tが最悪時(正三角形)でも t*2 - 1になるので、制約上数十回の計算で済みます。

コード

int main() {
    ll x, y;
    cin >> x >> y;

    vll a(3, y);
    int ans = 0;
    while(true) {
        if(a[0] >= x && a[1] >= x && a[2] >= x)
            break;

        a[0] = a[1] + a[2] - 1;

        sort(all(a));
        ans++;
    }

    cout << ans << endl;
    
    return 0;
}