Official

B - 友好の印 / Sign of Friendship Editorial by tatyam


遮蔽物が \(1\) 個の場合を考えると、UFO と遮蔽物の上端を結ぶ直線の傾きが \(\frac{H-h}{D-d}\) なので、登らなければならない高さは \(\max\bigl(0, h - d \times \frac{H-h}{D-d}\bigr)\) です。
遮蔽物が複数ある場合は、\(\max\bigl(0, h - d \times \frac{H-h_i}{D-d_i}\bigr)\) の最大値が答えになります。

回答例 (C++)

#include <iostream>
using namespace std;
void chmax(double& a, double b){ if(a < b) a = b; }

int main(){
    int N;
    double D, H, ans = 0;
    cin >> N >> D >> H;
    while(N--){
        double d, h;
        cin >> d >> h;
        chmax(ans, h - d * (H - h) / (D - d));
    }
    cout << ans << endl;
}

回答例 (Python)

N, D, H = map(int, input().split())
ans = 0.0
for i in range(N):
    d, h = map(int, input().split())
    h -= d * (H - h) / (D - d)
    if ans < h:
        ans = h
print(ans)

posted:
last update: