{"id":1151,"date":"2015-07-11T08:36:09","date_gmt":"2015-07-11T00:36:09","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1151"},"modified":"2015-07-11T08:46:52","modified_gmt":"2015-07-11T00:46:52","slug":"project-euler-503-compromise-or-persist","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/project-euler-503-compromise-or-persist\/","title":{"rendered":"Project Euler 503. Compromise or persist"},"content":{"rendered":"<p><!--more--><br \/>\n<a href=\"https:\/\/projecteuler.net\/problem=503\">https:\/\/projecteuler.net\/problem=503<\/a><\/p>\n<hr>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\r\nconst int N = int(1e6) + 9;\r\n\r\nint n = 1000000;\r\n\r\nDB f&#x5B;N];\r\n\r\n\r\n\r\n\/\/ randomly choosing i elements from n elements,\r\n\r\n\/\/ the expectation of the j-th element.\r\n\r\nDB e(int i, int j){\r\n\r\n    return (DB)(n+1) \/ (i+1) * j;\r\n\r\n}\r\n\r\n\r\n\r\nint main(){\r\n\r\n    \r\n\r\n#ifndef ONLINE_JUDGE\r\n\r\n    freopen(&quot;\/users\/xiaodao\/desktop\/Exercise\/in.txt&quot;, &quot;r&quot;, stdin);\r\n\r\n    \/\/freopen(&quot;\/users\/xiaodao\/desktop\/Exercise\/out.txt&quot;, &quot;w&quot;, stdout);\r\n\r\n#endif\r\n\r\n    \r\n\r\n    f&#x5B;n] = (n + 1.0) \/ 2;\r\n\r\n    int up = n - 1;\r\n\r\n    DWN(i, n, 1){\r\n\r\n        \/\/ in i-th round, we get j-th,\r\n\r\n        \/\/ we enumerate the cut-off point: k,\r\n\r\n        \/\/ that is, if j &lt;= k, we stop.\r\n\r\n        f&#x5B;i] = f&#x5B;i + 1]; \/\/ if k=0\r\n\r\n        DB prob = 1, expe = 0;\r\n\r\n        \/\/ the prob we don't stop ..\r\n\r\n        \/\/ the expe if we stop.\r\n\r\n        REP_1_C(k, up){\r\n\r\n            expe += 1.0 \/ i * e(i, k); if (expe &gt;= f&#x5B;i]) break;\r\n\r\n            prob -= 1.0 \/ i;\r\n\r\n            if (expe + prob * f&#x5B;i+1] &lt; f&#x5B;i]){\r\n\r\n                f&#x5B;i] = expe + prob * f&#x5B;i+1];\r\n\r\n                up = k;\r\n\r\n            }\r\n\r\n        }\r\n\r\n    }\r\n\r\n    printf(&quot;%.10f\\n&quot;, f&#x5B;1]);\r\n\r\n}\r\n\r\n\r\n\/\/ 3.8694550145\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","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":[143],"tags":[],"class_list":["post-1151","post","type-post","status-publish","format-standard","hentry","category-pe"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-iz","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1151","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=1151"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1151\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1151"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1151"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1151"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}