解題區/解題區 - UVa

UVa 12791 - Lap

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

在賽車運動中，常用 Lap 表示套一圈賽道所消耗的時間，現在有多名賽車手，給予最快一圈多久、最慢一圈多久，請問在最快車手第幾圈的時候，可以倒追最慢的車手。

Sample Input

1
2
3
4
1 10
4 8
5 7
6875 7109

Sample Output

1
2
3
4
2
2
4
31

Solution

懶得推導公式，二分倒追的時間，找到何時會產生倒追，再計算第幾圈即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h> 
#include <math.h>
int main() {
    int X, Y;
    while (scanf("%d %d", &X, &Y) == 2) {
        double l = 0, r = 1e+30, mid;
        int ret = 0;
#define eps 1e-8
        while (fabs(l - r) > eps) {
            mid = (l + r)/2;
            if (mid * (1.0/X - 1.0/Y) >= 1)
                r = mid;
            else
                l = mid;
        }
        printf("%.0lf\n", ceil(mid/X));
    }
    return 0;
}