AtCoder ABC 207 B - Hydrate (5Q, 灰色, 200 点)

これ結構難しい！ 数式を丁寧に立てよう。

• 問題へのリンク

問題概要

箱に水色のボールが 個入っている。

「箱に 個の水色のボールと、 個の赤色のボールを入れる」という操作を繰り返すことで、赤色のボールの個数が水色のボールの個数の 倍以上となるようにしたい。

それを達成するための最小回数を求めよ (不可能な場合は -1 とせよ)。

制約

• 

考えたこと

頭がこんがらがりそうになるので、落ち着いて数式で整理して考えよう。

回の操作で条件を満たすとする。このとき、水色のボールの個数は 、赤色のボールの個数は と表せることから、前者が後者の 倍以下となる条件は次のように書ける。

これを整理すると、

となる。

もし、 である場合は、左辺は常に負、右辺は常に正なので条件を満たす正の整数 は存在しない。

よって、 としてよく、このとき、次のようになる。

---

---

よって、答えは である。なお、一般に とは、 を で割ったときに余りがあれば切り上げたものを表す。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long A, B, C, D;
    cin >> A >> B >> C >> D;
    
    long long q = C * D - B;
    if (q <= 0) {
        cout << -1 << endl;
    } else {
        long long res = (A + q - 1) / q;
        cout << res << endl;
    }
}