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