けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

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

問題概要

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

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

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

制約

  •  1 \le A, B, C, D \le 10^{5}

考えたこと

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

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

 A + Bx \le CDx

これを整理すると、

 (CD - B)x \ge A

となる。

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

よって、 CD - B \gt 0 としてよく、このとき、次のようになる。


 \displaystyle x \ge \lceil \frac{A}{CD - B} \rceil


よって、答えは  \displaystyle \lceil \frac{A}{CD - B} \rceil である。なお、一般に  \lceil \frac{p}{q} \rceil とは、 p q で割ったときに余りがあれば切り上げたものを表す。

コード

#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;
    }
}