# 某岛

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

# Google Code Jam 2012 Round 1A

### Brief description:

Problem C. Cruise Control

### 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);
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);
}
}