Music Game

2 secs 1024 MB

dyktr_06

Problem

Submissions

Test cases

Editorial

以下の判定問題を考えてみましょう。

PERFECT が $S$ であるとき、 $K$ 点以上を達成できるか？

この判定問題を解くうえでは、PERFECT、GREAT、MISS の個数が分かっていることから全体の点数を計算することは容易です。

判定問題には単調性があるため、二分探索を用いるとこの問題を十分高速に解くことができます。
なお、二分探索の上限によるオーバーフローに注意してください。 (今回の問題では、答えは最大でも $1.5 \times 10^{10}$ 程度に収まります。)

実装例(C++)

#include<bits/stdc++.h>

using namespace std;

int main(){
    int y, z, k;
    cin >> y >> z >> k;
    long long ng = -1;
    long long ok = 1e12;

    while (abs(ok - ng) > 1) {
        long long mid = (ok + ng) / 2;
        long long sum = mid + y + z;
        long long score = ((mid * 2 + y) * 100000) / (sum * 2);
        if (score >= k) ok = mid;
        else ng = mid;
    }
    cout << ok << endl;
}