[UVA][三分] 10385 - Duathlon＠Morris' Blog｜PChome Online 個人新聞台

2013-12-01 11:40:33| 人氣1,894| 回應0 | 上一篇 | 下一篇

[UVA][三分] 10385 - Duathlon

推薦 0 收藏 0 轉貼0 訂閱站台

Problem H
Duathlon
Input: standard input
Output: standard output
Time Limit: 15 seconds

A duathlon is a race that involves running r km and cycling k km. n contestants have entered the race; each contestant has different running and cycling speeds. One of the contestants has bribed the organizers to set r and k so that he can win by the maximum margin. You are to determine if this is possible and, if so, give r and k.

Input

The input file contains several sets of input. The description of each set is given below:

The first line of each set contains an integer t, the total distance of the race, in km. That is, r + k = t. The next line contains an integer n, the number of competitors. For each contestant, a line follows with two real numbers giving the running and cycling speed for that contestant. The last line of input gives the running and cycling speed of the contestant who has bribed the organizers. You may assume t does not exceed 100 km and n does not exceed 20. Input is terminated by end of file. Two consecutive sets may or may not be separated by a blank line.

Output

For each set of input produce one line of output. The output description for each set is given below:

If it is possible to fix the race as describe above, print a message giving r and k accurate to two decimal places, and the amount of seconds by which the cheater will win the race (0 is case some competitor ties him), as in the sample below. If it is not possible, print "The cheater cannot win." There is no blank line between outputs for two consecutive sets.

Sample Input
100
3
10.0 40.0
20.0 30.0
15.0 35.0

100
3
10.0 40.0
20.0 30.0
15.0 25.0

Sample Output
The cheater can win by 612 seconds with r = 14.29km and k = 85.71km.

The cheater cannot win.

(Regionals 2002 Warm-up Contest, Problem setter: Gordon V. Cormack)

題目描述：

鐵人兩項最佳化問題，每個參賽選手在兩項的速度不依，兩項的總距離不變
調整兩項距離比例，讓指定選手獲勝，而且贏過第二名越多秒越好。

題目解法：

三分搜索答案，至於證明凸性部分，暫且沒有辦法。

#include <stdio.h>
#include <math.h>
int n;
double T, rp[30], cp[30];
double calcWin(double r) {
    double k = T-r, mn = 1e+30, tmp;
    int i, j;
    for(i = n-2; i >= 0; i--) {
        tmp = r/rp[i] + k/cp[i];
        if(tmp < mn)
            mn = tmp;
    }
    tmp = r/rp[n-1] + k/cp[n-1];
    return mn - tmp;// > 0 win, < 0 lose
}
void ternary_search() {
    double l, r, mid, midmid;//ternary search
    double md, mmd;
    l = 0, r = T;
    while(fabs(l-r) > 1e-4) {
        mid = (l+r)/2;
        midmid = (mid+r)/2;
        md = calcWin(mid);
        mmd = calcWin(midmid);
        if(md >= mmd)
            r = midmid;
        else
            l = mid;
    }
    double sec = calcWin(r)*60*60;
    if(sec < 0)
        puts("The cheater cannot win.");
    else
        printf("The cheater can win by %.0lf seconds with r = %.2lfkm and k = %.2lfkm.\n", sec, r, T-r);
}
int main() {
    int i, j, k;
    while(scanf("%lf %d", &T, &n) == 2) {
        for(i = 0; i < n; i++)
            scanf("%lf %lf", &rp[i], &cp[i]);
        ternary_search();
    }
    return 0;
}

我要檢舉

#10385#Duathlon#三分搜索#凸性#三分

台長： Morris

您可能對以下文章有興趣

[UVA][極角排序] 1432 - Fire-Control System

[UVA] 10585 - Center of symmetry

[UVA] 11664 - Langton's Ant

[UVA] 11047 - The Scrooge Co Problem

人氣(1,894) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][數學][繁瑣] 10367 - Equations
此分類上一篇:[UVA][數學] 10329 - Combinatorial Expression

回應(0)