2014-05-22

ICPC 4020 - Hard Rode

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

Problem

The road to Shu is hard, even harder than climbing to the blue sky. A poem by Li Po from Tang Dynasty 1,200 years ago described the difficulty in travelling into Sichuan.

\epsfbox{p4020.eps}

However the above old saying is no longer true as a convenient communication network of railway, highway, waterway and air transport has come into being. Railways cover a total mileage of 2,693 km, consisting of five trunk lines including the BaojiChengdu and Chengdu-Chongqing railways, eight feeder lines and four local railways. The total mileage of highways stretches to nearly 80,000 km, ranking at the forefront in China. Now a highway network with the provincial capital of Chengdu as the center radiating to all cities in the province has been formed. A total of 500 km of expressways have been built. It is very easy to transfer passengers and freights between Sichuan and other provinces. After a nationwide railway speed acceleration launched in last year, trains can be allowed to run at a speed above 120 km per hour. However, the average speed of a train depends on its make-up. There is only single railway track between stations from Baoji to Chengdu, A primary task for dispatchers is to arrange for trains to meet and pass each other. You are requested to write a program to make the arrangement for a series of trains of different speeds from one station to its next station in the least amount of time.

What you should pay attention to while writing this program is that since there is a single railway track from Baoji to Chengdu, two trains are not allowed to pass the same spot at the same time, or they would be collision, and that because of the limited staff, there should be a fixed interval time between two trains out of the station, what’s more, the trains could pull into the station at the same time, but never get out at the same time.

Input

The input consists of several test cases. Each test case begins with a line containing 3 integers L (1 <= L <= 100000) , N (1 <= N <= 8) and T (1 < T < 10000) which indicate the distance between two stations (unit is meter), the number of trains, as well as the interval time of adjacent trains when trains leave the start (unit is second).

The next N lines contain average speeds of N trains (unit is m/s).

A single line with L = 0 indicates the end of input file and should not be processed by your program.

Output

For each test case, your output should be in one line with the minimum time(round to integer) needed by the trains pulling into the terminal as indicated in the sample output.

Sample Input

100000 6 300 
3 
4 
5 
6 
2 
1 
0

Sample Output

1	Case 1: 101500

Solution

題目描述：

從陝西省寶雞市到四川省成都市有一條鐵軌，而這一條鐵軌一次有好幾台火車在運行，但是不會發生追撞事件，然而每台火車的速度不一樣，而且站務人員會每隔固定時間發一班車，在不發生碰撞的情況下，最後一台火車到達成都市的最少時間為何？

題目解法：

在這樣的情況，有可能慢車先出發，然在在 T 秒之後，快車恰好追到慢車，這樣的情況會更好。但是實際數據應該長成什麼樣子沒有仔細考慮。

如果使用慢車最後出發，這樣能確保一定不會產生碰撞，但不確定是否是最佳解。

所以使用 O(n!) 的窮舉來計算答案。

#include <stdio.h> 
#include <algorithm>
#include <math.h>
using namespace std;
int main() {
    int L, N, T, cases = 0;
    long long speed[10];
    while(scanf("%d %d %d", &L, &N, &T) == 3 && L) {
        int p[10] = {};
        for(int i = 0; i < N; i++) {
            scanf("%lld", &speed[i]);
            p[i] = i;
        }
        sort(speed, speed + N);
        long long ret = 0x3f3f3f3f;
        do {
            double start = T, lastTime = L / speed[p[0]];
            for(int i = 1; i < N; i++) {
                double time = L / speed[p[i]] + start;
                if(time >= lastTime) {
                    start += T;
                    lastTime = time;
                } else {
                    lastTime = 0x3f3f3f3f;
                    break;
                    // start += T + (lastTime - time);
                }
            }
            ret = min(ret, (long long) ceil(lastTime));
        } while (next_permutation(p, p + N));
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}

Morris' Blog