{"id":1199,"date":"2015-08-20T20:32:27","date_gmt":"2015-08-20T12:32:27","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1199"},"modified":"2015-10-19T00:24:46","modified_gmt":"2015-10-18T16:24:46","slug":"pe-393","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/pe-393\/","title":{"rendered":"ProjectEuler 393. Migrating ants"},"content":{"rendered":"<p><a href=\"https:\/\/projecteuler.net\/problem=393\">https:\/\/projecteuler.net\/problem=393<\/a><\/p>\n<p><!--more--><\/p>\n<p>Fork: <a href=\"https:\/\/www.shuizilong.com\/house\/archives\/ural-1519-formula-1\/\">https:\/\/www.shuizilong.com\/house\/archives\/ural-1519-formula-1\/<\/a><\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;iostream&gt;\r\n#include &lt;cstdio&gt;\r\n#include &lt;cstring&gt;\r\nusing namespace std;\r\nconst int hh = 12, ww = 12, _W = 15, MaxH = 10 * 15511;\r\nbool O&#x5B;hh+1]&#x5B;ww+1]; int A, B, X, Y; int h, w, l, s;\r\nlong long ans, d;\r\n\r\nstruct hashTable {\r\n    int state&#x5B;MaxH], head&#x5B;MaxH], next&#x5B;MaxH], sz;\r\n    long long key&#x5B;MaxH];\r\n    \r\n    inline void clear() {\r\n        sz = 0;\r\n        memset(head, -1, sizeof(head));\r\n    }\r\n    inline void insert(int s) {\r\n        int x = s % MaxH;\r\n        for ( int it = head&#x5B;x] ; it != -1 ; it = next&#x5B;it] ) {\r\n            if ( state&#x5B;it] == s ) {\r\n                key&#x5B;it] += d;\r\n                return;\r\n            }\r\n        }\r\n        state&#x5B;sz] = s, key&#x5B;sz] = d;\r\n        next&#x5B;sz] = head&#x5B;x];\r\n        head&#x5B;x] = sz++;\r\n    }\r\n} H&#x5B;2] , *src , *des;\r\n\r\nint n;\r\n\r\n\r\ninline int countBits(int x){\r\n    x = (x &amp; 0x00005555) + ((x &amp; 0x0000aaaa) &gt;&gt; 1);\r\n    x = (x &amp; 0x00003333) + ((x &amp; 0x0000cccc) &gt;&gt; 2);\r\n    x = (x &amp; 0x00000f0f) + ((x &amp; 0x0000f0f0) &gt;&gt; 4);\r\n    x = (x &amp; 0x000000ff) + ((x &amp; 0x0000ff00) &gt;&gt; 8);\r\n    return x;\r\n}\r\n\r\n\r\nint eatLeft(int s, int i){\r\n    int An = 0;\r\n    for (i--;;i--){\r\n        if (!(s &amp; (1 &lt;&lt; i))) continue;\r\n        if (s &amp; (1 &lt;&lt; _W + i)) An++;\r\n        else {if (An==0){s ^= 1 &lt;&lt; (_W + i); return s;} An--;}\r\n    }\r\n}\r\nint eatRight(int s, int i){\r\n    int An = 0;\r\n    for (i++;;i++){\r\n        if (!(s &amp; (1 &lt;&lt; i))) continue;\r\n        if (!(s &amp; (1 &lt;&lt; _W + i))) An++;\r\n        else {if (An==0){s ^= 1 &lt;&lt; (_W + i); return s;} An--;}\r\n    }\r\n}\r\n\r\n\r\n\r\n\r\nbool _O(){\r\n    for (int i=0;i&lt;w;i++)\r\n        if (!O&#x5B;h-1]&#x5B;i]) return false;\r\n    return true;\r\n}\r\n\r\n\r\n\r\nvoid init(){\r\n    \r\n    h = w = n;\r\n    \r\n    for (int i=0;i&lt;h;i++)\r\n        for (int j=0;j&lt;w;j++)\r\n            O&#x5B;i]&#x5B;j] = false;\r\n    \r\n    \r\n    while (_O()) h--;\r\n    \r\n    \r\n    for (int i=0;i&lt;h;i++)\r\n        O&#x5B;h]&#x5B;i] = O&#x5B;i]&#x5B;w] = true;\r\n    \r\n}\r\n\r\n\r\n\r\nvoid solve(){\r\n    \r\n    src = H, des = src + 1, d = 1;\r\n    des-&gt;clear(), des-&gt;insert(0); src-&gt;clear();\r\n    ans = 0;\r\n    \r\n    int _w = w;\r\n    \r\n    for (int i = 0; i &lt; h; i ++){\r\n        \r\n        for (int j = 0; j &lt; src-&gt;sz; j ++)\r\n            des-&gt;state&#x5B;j] &lt;&lt;= 1;\r\n        \r\n        w = _w;\r\n        \r\n        while (O&#x5B;i]&#x5B;w-1]) w--;\r\n        \r\n      \/\/  cout &lt;&lt; w &lt;&lt; &quot; &quot; &lt;&lt; i &lt;&lt; endl;\r\n        \r\n        for (int j = 0; j &lt; w; j ++){\r\n            \r\n            if (O&#x5B;i]&#x5B;j]) continue;\r\n            \r\n            swap(src, des), des-&gt;clear();\r\n            \r\n           \/\/ cout &lt;&lt; &quot; &quot; &lt;&lt; j &lt;&lt; endl;\r\n            \r\n            for (int k = 0; k &lt; src-&gt;sz; k ++){\r\n                s = src-&gt;state&#x5B;k], d = src-&gt;key&#x5B;k];\r\n                A = s &amp; (1 &lt;&lt; j), B = s &amp; (1 &lt;&lt; (j+1));\r\n                \r\n         \/\/       cout &lt;&lt; &quot;  &quot; &lt;&lt; k &lt;&lt; &quot; &quot; &lt;&lt; src-&gt;sz &lt;&lt; endl;\r\n                \r\n                if (!A &amp;&amp; !B){\r\n                    if (!O&#x5B;i+1]&#x5B;j] &amp;&amp; !O&#x5B;i]&#x5B;j+1]) des-&gt;insert(s ^ (3 &lt;&lt; j | 1 &lt;&lt;( _W + j + 1)));\r\n                }\r\n                else{\r\n                    \r\n                    X = s &amp; (1 &lt;&lt; (_W + j)), Y = s &amp; (1 &lt;&lt; (_W + j + 1));\r\n                    \r\n                    if (A &amp;&amp; B){\r\n                        \r\n                        if (X){\r\n                            if (Y){ \/\/'))'\r\n                                des-&gt;insert(eatLeft(s, j) ^ (3 &lt;&lt; j | 3 &lt;&lt; _W + j));\r\n                            }\r\n                            else { \/\/')('\r\n                                des-&gt;insert(s ^ (3 &lt;&lt; j | 1 &lt;&lt; _W + j));\r\n                            }\r\n                        }\r\n                        else {\r\n                            if (Y){ \/\/'()'                            if (Y){ \/\/'()'\r\n                                \r\n                                \/\/  ans += d;\r\n                                \r\n                                d *= 2;\r\n                                \r\n                                if (i + 1 == h &amp;&amp; j + 1 == w &amp;&amp; countBits(s)==2) ans += d;\r\n                                \r\n                                \/\/   d *= 2;\r\n                                \r\n                                \r\n                                \r\n                                \/\/ if (\r\n                                \r\n                                des-&gt;insert(s ^ (3 &lt;&lt; j) ^ X ^ Y);\r\n                                \r\n                                d \/= 2;\r\n                                \r\n                            }\r\n                            else { \/\/'(('\r\n                                des-&gt;insert(eatRight(s, j+1) ^ (3 &lt;&lt; j));\r\n                            }\r\n                        }\r\n                        \r\n                        \r\n                    }\r\n                    else {\r\n                        if (A){\r\n                            if (!O&#x5B;i+1]&#x5B;j]) des-&gt;insert(s);\r\n                            \r\n                            if (!O&#x5B;i]&#x5B;j+1]) {\r\n                                if (X) des-&gt;insert(s ^ (3 &lt;&lt; j | 3 &lt;&lt; (_W + j)));\r\n                                else des-&gt;insert(s ^ (3 &lt;&lt; j));\r\n                            }\r\n                        }\r\n                        else {\r\n                            if (!O&#x5B;i]&#x5B;j+1]) des-&gt;insert(s);\r\n                            if (!O&#x5B;i+1]&#x5B;j]) {\r\n                                if (Y) des-&gt;insert(s ^ (3 &lt;&lt; j | 3 &lt;&lt; (_W + j)));\r\n                                else des-&gt;insert(s ^ (3 &lt;&lt; j));\r\n                            }\r\n                        }\r\n                    }\r\n                }\r\n                \r\n            }\r\n        }\r\n    }\r\n}\r\n\r\n\r\nint main(){\r\n    \r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;\/users\/xiaodao\/desktop\/Exercise\/in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;\/users\/xiaodao\/desktop\/Exercise\/out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n    \r\n    \/\/freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    while (cin &gt;&gt; n){\r\n        init(); ans = 0;  solve();\r\n        cout &lt;&lt; ans &lt;&lt; endl;\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/projecteuler.net\/problem=393<\/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":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-1199","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-jl","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1199","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=1199"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1199\/revisions"}],"predecessor-version":[{"id":1205,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1199\/revisions\/1205"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1199"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1199"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1199"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}