Problem C. Cruise Control
\n\u7ed9\u5b9a\u4e00\u6761\u65e0\u9650\u957f\u7684\u53cc\u8f66\u9053\u7684\u5355\u884c\u9053\uff0cn \u91cf\u8f66\u7684\u4fe1\u606f (Li, Si, Pi) \u8868\u793a\u521d\u59cb\u5728\u54ea\u4e2a\u8f66\u9053\u3001\u901f\u5ea6\u3001\u548c\u5f53\u524d\u4f4d\u7f6e\uff0c
\n\u95ee\u7b2c\u4e00\u6b21\u53d1\u751f\u78b0\u649e\u4e8b\u4ef6\u7684\u65f6\u95f4\u3002(\u6bcf\u8f86\u8f66\u8f66\u957f 5m\uff0c\u8f66\u8f86\u5728\u65c1\u8fb9\u6ca1\u6709\u8f66\u65f6\uff0c\u53ef\u4ee5\u4efb\u610f\u5207\u6362\u8f66\u9053\u4e14\u4e0d\u8ba1\u65f6\u95f4\u3002)
\n…
\n<\/p>\n
Problem C. Cruise Control Brief description: Problem C. Cruise Control \u7ed9\u5b9a\u4e00\u6761\u65e0\u9650\u957f\u7684\u53cc\u8f66\u9053\u7684\u5355\u884c\u9053\uff0cn \u91cf\u8f66\u7684\u4fe1\u606f (Li, Si, Pi) \u8868\u793a\u521d\u59cb\u5728\u54ea\u4e2a\u8f66\u9053\u3001\u901f\u5ea6\u3001\u548c\u5f53\u524d\u4f4d\u7f6e\uff0c \u95ee\u7b2c\u4e00\u6b21\u53d1\u751f\u78b0\u649e\u4e8b\u4ef6\u7684\u65f6\u95f4\u3002(\u6bcf\u8f86\u8f66\u8f66\u957f 5m\uff0c\u8f66\u8f86\u5728\u65c1\u8fb9\u6ca1\u6709\u8f66\u65f6\uff0c\u53ef\u4ee5\u4efb\u610f\u5207\u6362\u8f66\u9053\u4e14\u4e0d\u8ba1\u65f6\u95f4\u3002) …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[67],"tags":[],"class_list":["post-194","post","type-post","status-publish","format-standard","hentry","category-google-code-jam"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-38","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/194","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=194"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/194\/revisions"}],"predecessor-version":[{"id":195,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/194\/revisions\/195"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=194"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=194"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=194"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n\u5bf9\u6bcf\u8f86\u8f66\u53ef\u80fd\u7684\u76f8\u9047\u533a\u95f4\u9009\u53d6\u5173\u952e\u65f6\u95f4\u5efa\u7acb\u4e8b\u4ef6\uff0c\u6392\u5e8f\u3002\u3002\u3002
\n\u3002\u3002\u4e4b\u540e \u7528\u5e76\u67e5\u96c6<\/del> \u66b4\u529b\u7ef4\u62a4\u67d3\u8272\u4fe1\u606f\u5373\u53ef
\n\uff08\u3002\u3002\u5176\u5b9e\u5c31\u662f\u6709\u4e00\u4e9b\u70b9\u5df2\u7ecf\u67d3\u8272\u7684\u60c5\u51b5\u4e0b\u505a\u4e8c\u5206\u56fe\u5224\u5b9a\u3002\u3002\u5e76\u67e5\u96c6\u8c8c\u4f3c\u4f1a\u6bd4\u8f83\u9ebb\u70e6\u3002\u3002\u56e0\u4e3a\u6709\u62c6\u89e3\u7684\u60c5\u51b5\u4ea7\u751f\u5440\u3002\u3002\u3002\uff09
\n…<\/p>\n\r\n\/\/ <<= ' 0. I\/O Accelerator interface .,\r\n\r\ntemplate<class T> inline void RD(T &x){\r\n \/\/cin >> x;\r\n scanf("%d", &x);\r\n \/\/char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';\r\n \/\/char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';\r\n}\r\n\r\nint ____Case;\r\ntemplate<class T> inline void OT(const T &x){\r\n printf("Case #%d: ", ++____Case);\r\n \/\/printf("%d", x);\r\n printf("%.9f", x);\r\n puts("");\r\n}\r\n\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 100009;\r\nDB P[N], tmp, res, cur;\r\nint A, B;\r\n\r\nint main(){\r\n\r\n \/\/freopen("A-small-attempt0.in", "r", stdin);\r\n freopen("A-large.in", "r", stdin);\r\n \/\/freopen("in.txt", "r", stdin);\r\n freopen("out.txt", "w", stdout);\r\n\r\n Rush{\r\n RD(A, B); REP(i, A) scanf("%lf", &P[i]); res = OO;\r\n\r\n res = B + 2, tmp = 1;\r\n DWN_1(i, A, 0){ \r\n cur = (DB) (2 * i + B - A + 1 + B + 1) - tmp * (B + 1); \r\n checkMin(res, cur);\r\n tmp *= P[A - i];\r\n }\r\n\r\n OT(res);\r\n }\r\n}\r\n\r\n<\/pre>\n\r\n\/\/ <<= ' 0. I\/O Accelerator interface .,\r\n\r\ntemplate<class T> inline void RD(T &x){\r\n \/\/cin >> x;\r\n scanf("%d", &x);\r\n \/\/char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';\r\n \/\/char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';\r\n}\r\n\r\nbool failed;\r\n\r\nint ____Case;\r\ntemplate<class T> inline void OT(const T &x){\r\n printf("Case #%d: ", ++____Case);\r\n if (failed) puts("Too Bad");\r\n else {\r\n printf("%d", x); puts("");\r\n }\r\n}\r\n\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 1009;\r\nint a[N], b[N], c[N], star, tt;\r\nint n;\r\n\r\nint main(){\r\n\r\n \/\/freopen("B-large-practice.in", "r", stdin);\r\n \/\/freopen("A-large.in", "r", stdin);\r\n freopen("in.txt", "r", stdin);\r\n freopen("out.txt", "w", stdout);\r\n\r\n Rush{\r\n\r\n REP_C(i, _RD(n)) RD(a[i], b[i]); b[n] = -INF;\r\n\r\n int j; RST(c); failed = false; star = tt = 0; while (star < 2*n && !failed){\r\n\r\n ++tt;\r\n\r\n REP(i, n) if (c[i] < 2 && star >= b[i]){\r\n star += 2 - c[i], c[i] = 2;\r\n goto A;\r\n }\r\n\r\n j = n; REP(i, n) if (c[i] < 1 && star >= a[i]){\r\n if (b[i] > b[j]) j = i;\r\n }\r\n\r\n if (j != n){\r\n star += 1, c[j] = 1;\r\n goto A;\r\n }\r\n\r\n failed = true;\r\n A:;\r\n }\r\n\r\n OT(tt);\r\n }\r\n}\r\n<\/pre>\n\r\nconst int N = 59;\r\n\r\nbool G[N][N]; int lane[N], pos[N], spd[N], tmp[N];\r\nint n;\r\n\r\n\r\nbool dfs(int u, int c) {\r\n if (lane[u] && lane[u] != c) return false;\r\n if (tmp[u]) return tmp[u] == c;\r\n\r\n tmp[u] = c; REP(v, n){\r\n if (G[u][v] && !dfs(v, c * -1)) return false;\r\n }\r\n return true;\r\n}\r\n\r\nvector<DB> L;\r\n\r\nint main() {\r\n\r\n \/\/freopen("C-small-practice.in", "r", stdin);\r\n freopen("C-large-practice.in", "r", stdin);\r\n \/\/freopen("in.txt", "r", stdin);\r\n freopen("out.txt", "w", stdout);\r\n\r\n\r\n Rush{\r\n\r\n CLR(L); L.PB(0);\r\n\r\n char dir; REP_C(i, _RD(n)){\r\n lane[i] = _RC(dir) == 'L' ? -1 : 1;\r\n RD(spd[i], pos[i]);\r\n }\r\n\r\n REP(i, n) REP(j, n) if (spd[j] > spd[i]){\r\n DB speed = spd[j] - spd[i]; if (pos[i] + 5 > pos[j]) {\r\n L.PB(DB(pos[i]+5-pos[j])\/speed);\r\n if (pos[i] > pos[j]) {\r\n L.PB(DB(pos[i]-pos[j])\/speed);\r\n if (pos[i] - 5 > pos[j]) L.PB(DB(pos[i]-5-pos[j])\/speed);\r\n }\r\n }\r\n }\r\n\r\n res = 0; SRT(L); RST(G); int ii; REP_N(ii, SZ(L)){\r\n\r\n REP(i, n){\r\n bool coll = false; REP(j, n) if (j != i) {\r\n DB pi = pos[i] + spd[i] * L[ii], pj = pos[j] + spd[j] * L[ii];\r\n if (sgn(abs(pi - pj), 5) < 0){\r\n G[i][j] = G[j][i] = true;\r\n coll = true;\r\n }\r\n }\r\n\r\n if (!coll) {\r\n for (int j = 0; j < N; j++) G[i][j] = G[j][i] = 0;\r\n lane[i] = 0;\r\n }\r\n }\r\n\r\n REP(i, n) if (!lane[i]){\r\n RST(tmp); bool lv = dfs(i, -1);\r\n RST(tmp); bool rv = dfs(i, 1);\r\n\r\n if (!lv && !rv) goto Done;\r\n if (!lv && rv) lane[i] = 1;\r\n if (lv && !rv) lane[i] = -1;\r\n }\r\n else {\r\n RST(tmp); if (!dfs(i, lane[i])) goto Done;\r\n }\r\n\r\n res = L[ii];\r\n }\r\n\r\nDone:\r\n printf("Case #%d: ", ++____Case);\r\n if (ii == SZ(L)) puts("Possible");\r\n else printf("%.9lf\\n", res);\r\n }\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"