{"id":183,"date":"2019-05-20T12:00:00","date_gmt":"2019-05-20T04:00:00","guid":{"rendered":"http:\/\/wwwwodddd.com\/?p=183"},"modified":"2019-05-20T12:00:00","modified_gmt":"2019-05-20T04:00:00","slug":"gcj-2019-r2","status":"publish","type":"post","link":"https:\/\/wwwwodddd.com\/wordpress\/gcj-2019-r2\/","title":{"rendered":"Google Code Jam 2019 Round 2"},"content":{"rendered":"<p><!--more--><\/p>\n<h1>P1<\/h1>\n<p>\u5b9e\u9645\u4e0a\u53ea\u9700\u8981\u7edf\u8ba1\u4e0d\u540c\u659c\u7387\u7684\u4e2a\u6570\u3002<\/p>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\ntypedef long long ll;\nint n;\nbool o;\nll A, B;\nll C[320];\nll J[320];\nbool cmp(int x, int y) {\n    if (A * C[x] + B * J[x] != A * C[y] + B * J[y]) {\n        return A * C[x] + B * J[x] &lt; A * C[y] + B * J[y];\n    }\n    if (o) {\n        return C[x] &lt; C[y];\n    } else {\n        return C[x] &gt; C[y];\n    }\n}\nll gcd(ll x, ll y) {\n    return y ? gcd(y, x % y) : x;\n}\nint main() {\n    int t;\n    scanf(\"%d\", &amp;t);\n    for (int tt = 1; tt &lt;= t; tt++) {\n        scanf(\"%d\", &amp;n);\n        vector&lt;vector&lt;int&gt; &gt; z;\n        vector&lt;int&gt; r;\n        for (int i = 0; i &lt; n; i++) {\n            scanf(\"%lld%lld\", &amp;C[i], &amp;J[i]);\n            r.push_back(i);\n        }\n        set&lt;pair&lt;int, int&gt; &gt; fuck;\n        for (int i = 0; i &lt; n; i++) {\n            for (int j = 0; j &lt; n; j++) {\n                if (i != j &amp;&amp; C[i] &gt; C[j]) {\n                    if (J[i] &lt; J[j]) {\n                        B = C[i] - C[j];\n                        A = J[j] - J[i];\n                        ll g = gcd(A, B);\n                        A \/= g;\n                        B \/= g;\n                        fuck.insert(make_pair(A, B));\n                    }\n                }\n            }\n        }\n        printf(\"Case #%d: %d\\n\", tt, (int)fuck.size() + 1);\n    }\n    return 0;\n}\n<\/code><\/pre>\n<h1>P2<\/h1>\n<p>\u770b\u8d77\u6765\u5c31\u662f\u4e71\u641e<br \/>\n\u5e76\u4e0d\u9700\u8981\u5229\u7528\u53ef\u4ee5\u6a21\u4eff\u522b\u4eba\u8fd9\u4e00\u70b9<\/p>\n<h1>P3<\/h1>\n<p>\u7ecf\u5178\u8bba\u6587\u9898<\/p>\n<pre><code class=\"line-numbers\">from fractions import *\n# C \/ J\nt = input()\ndef gao(ax, ay, bx, by):\n    if by == 0 or ax \/ ay &lt; (bx - 1) \/ by:\n        return ax \/ ay + 1, 1\n    else:\n        xx, yy = gao(by, bx - ax \/ ay * by, ay, ax % ay)\n        return yy + ax \/ ay * xx, xx\n\nfor tt in range(1, t + 1):\n    n = input()\n    a = []\n    A = Fraction(1, 10 ** 9 + 1)\n    B = Fraction(10 ** 9 + 1, 1)\n    for i in range(n):\n        x, y = map(int, raw_input().split())\n        a.append((x, y))\n    for i in range(1, n):\n        if a[i - 1][0] &gt;= a[i][0] and a[i - 1][1] &gt;= a[i][1]:\n            A = B\n            break\n        elif a[i - 1][0] &lt;= a[i][0] and a[i - 1][1] &lt;= a[i][1]:\n            continue\n        elif a[i - 1][0] &gt; a[i][0] and a[i - 1][1] &lt; a[i][1]:\n            A = max(A, Fraction(a[i - 1][0] - a[i][0], a[i][1] - a[i - 1][1]))\n        elif a[i - 1][1] &gt; a[i][1] and a[i - 1][0] &lt; a[i][0]:\n            B = min(B, Fraction(a[i][0] - a[i - 1][0], a[i - 1][1] - a[i][1]))\n#  print A, B\n    if A &lt; B:\n        X, Y = gao(A.numerator, A.denominator, B.numerator, B.denominator)\n        print 'Case #%d: %d %d' % (tt, Y, X)\n    else:\n        print 'Case #%d: IMPOSSIBLE' % (tt)\n<\/code><\/pre>\n<h1>P4<\/h1>\n<p>\u6ca1\u770b<\/p>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-183","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/183","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/comments?post=183"}],"version-history":[{"count":0,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/183\/revisions"}],"wp:attachment":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/media?parent=183"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/categories?post=183"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/tags?post=183"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}