Algoogle

Algorithm for Programming Contest

AOJ 2298 Starting Line

Category: AOJ Tag: implementation

Starting Line

問題概要


解法


時間以外は離散的に扱えるので距離(1mごと)でシミュレーションします.
スピードアップしてる時間は整数なので整数の速さを掛ければスピードアップしている距離が整数ででる.
距離nまで走った時の時間は
距離n-1まで走った時の時間 + 距離1走るのにかかる時間
1メートル走るのにかかる時間は, スピードアップ時に 1 / V
そうでないときに 1 / U
距離nで人参が手に入る時, スピードアップしてないなら食べる(スピードアップしてる時間は残りT).
そうでないなら手持ちに加える. このとき, オーバーするならオーバー分は食べたと考えて, スピードアップしてる時間の残りはTにする.

コード


(2298.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
using namespace std;
int N, K, T, U, V, L;
int D[10010];

int main(){
    cin >> N >> K >> T >> U >> V >> L;
    rep(i,N){
        int t; cin >> t;
        D[t]++;
    }
    int have = 0;
    double ans = 0;
    int res = 0, prev = 0, pos = 0;
    repi(i,1,L+1){
        if(res){
            res--;
            ans += 1.0 / V;
        }
        else ans += 1.0 / U;
        if(have && !res) {
            have--;
            res = V * T;
        }
        if(D[i]) {
            if(!res) {
                D[i]--;
                res = V * T;
            }
            if(have + D[i] > K){
                D[i]--;
                res = V * T;
                have = K;
            }
            else have += D[i];
        }
    }
    printf("%.8f\n", ans);
    return 0;
}

Comments