Official

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


When there are a single obstacle, the slope of the line through the UFO and the top of the obstacle is \(\frac{H-h}{D-d}\), so the minimum height you have to climb is \(\max\bigl(0, h - d \times \frac{H-h}{D-d}\bigr)\).
When there are multiple obstacles, the answer will be the maximum value of \(\max\bigl(0, h - d \times \frac{H-h_i}{D-d_i}\bigr)\).

Sample Code (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;
}

Sample Code (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: