某島

… : "…アッカリ~ン . .. . " .. .
April 28, 2012

Google Code Jam 2012 Round 1A

Brief description:

Problem C. Cruise Control
給定一條無限長的雙車道的單行道,n 量車的信息 (Li, Si, Pi) 表示初始在哪個車道、速度、和當前位置,
問第一次發生碰撞事件的時間。(每輛車車長 5m,車輛在旁邊沒有車時,可以任意切換車道且不計時間。)

Analysis:

Problem C. Cruise Control
對每輛車可能的相遇區間選取關鍵時間建立事件,排序。。。
。。之後 用並查集 暴力維護染色信息即可
(。。其實就是有一些點已經染色的情況下做二分圖判定。。並查集貌似會比較麻煩。。因為有拆解的情況產生呀。。。)

// <<= ' 0. I/O Accelerator interface .,

template<class T> inline void RD(T &x){
    //cin >> x;
    scanf("%d", &x);
    //char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';
    //char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';
}

int ____Case;
template<class T> inline void OT(const T &x){
    printf("Case #%d: ", ++____Case);
    //printf("%d", x);
    printf("%.9f", x);
    puts("");
}

/* .................................................................................................................................. */

const int N = 100009;
DB P[N], tmp, res, cur;
int A, B;

int main(){

    //freopen("A-small-attempt0.in", "r", stdin);
    freopen("A-large.in", "r", stdin);
    //freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);

    Rush{
        RD(A, B); REP(i, A) scanf("%lf", &P[i]); res = OO;

        res = B + 2, tmp = 1;
        DWN_1(i, A, 0){            
            cur = (DB) (2 * i + B - A + 1 + B + 1) - tmp * (B + 1);            
            checkMin(res, cur);
            tmp *= P[A - i];
        }

        OT(res);
    }
}

// <<= ' 0. I/O Accelerator interface .,

template<class T> inline void RD(T &x){
    //cin >> x;
    scanf("%d", &x);
    //char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';
    //char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';
}

bool failed;

int ____Case;
template<class T> inline void OT(const T &x){
    printf("Case #%d: ", ++____Case);
    if (failed) puts("Too Bad");
    else {
        printf("%d", x); puts("");
    }
}

/* .................................................................................................................................. */

const int N = 1009;
int a[N], b[N], c[N], star, tt;
int n;

int main(){

    //freopen("B-large-practice.in", "r", stdin);
    //freopen("A-large.in", "r", stdin);
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);

    Rush{

        REP_C(i, _RD(n)) RD(a[i], b[i]); b[n] = -INF;

        int j; RST(c); failed = false; star = tt = 0; while (star < 2*n && !failed){

            ++tt;

            REP(i, n) if (c[i] < 2 && star >= b[i]){
                star += 2 - c[i], c[i] = 2;
                goto A;
            }

            j = n; REP(i, n) if (c[i] < 1 && star >= a[i]){
                if (b[i] > b[j]) j = i;
            }

            if (j != n){
                star += 1, c[j] = 1;
                goto A;
            }

            failed = true;
            A:;
        }

        OT(tt);
    }
}
const int N = 59;

bool G[N][N]; int lane[N], pos[N], spd[N], tmp[N];
int n;


bool dfs(int u, int c) {
    if (lane[u] && lane[u] != c) return false;
    if (tmp[u]) return tmp[u] == c;

    tmp[u] = c; REP(v, n){
        if (G[u][v] && !dfs(v, c * -1)) return false;
    }
    return true;
}

vector<DB> L;

int main() {

    //freopen("C-small-practice.in", "r", stdin);
    freopen("C-large-practice.in", "r", stdin);
    //freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);


    Rush{

        CLR(L); L.PB(0);

        char dir; REP_C(i, _RD(n)){
            lane[i] = _RC(dir) == 'L' ? -1 : 1;
            RD(spd[i], pos[i]);
        }

        REP(i, n) REP(j, n) if (spd[j] > spd[i]){
            DB speed = spd[j] - spd[i]; if (pos[i] + 5 > pos[j]) {
                L.PB(DB(pos[i]+5-pos[j])/speed);
                if (pos[i] > pos[j]) {
                    L.PB(DB(pos[i]-pos[j])/speed);
                    if (pos[i] - 5 > pos[j]) L.PB(DB(pos[i]-5-pos[j])/speed);
                }
            }
        }

        res = 0; SRT(L); RST(G); int ii; REP_N(ii, SZ(L)){

                REP(i, n){
                    bool coll = false; REP(j, n) if (j != i) {
                    DB pi = pos[i] + spd[i] * L[ii], pj = pos[j] + spd[j] * L[ii];
                    if (sgn(abs(pi - pj), 5) < 0){
                        G[i][j] = G[j][i] = true;
                        coll = true;
                    }
                }

                if (!coll) {
                    for (int j = 0; j < N; j++) G[i][j] = G[j][i] = 0;
                    lane[i] = 0;
                }
            }

            REP(i, n) if (!lane[i]){
                RST(tmp); bool lv = dfs(i, -1);
                RST(tmp); bool rv = dfs(i, 1);

                if (!lv && !rv) goto Done;
                if (!lv && rv) lane[i] = 1;
                if (lv && !rv) lane[i] = -1;
            }
            else {
                RST(tmp); if (!dfs(i, lane[i])) goto Done;
            }

            res = L[ii];
        }

Done:
        printf("Case #%d: ", ++____Case);
        if (ii == SZ(L)) puts("Possible");
        else printf("%.9lf\n", res);
    }
}