{"id":214,"date":"2020-01-22T00:00:57","date_gmt":"2020-01-21T16:00:57","guid":{"rendered":"https:\/\/wwwwodddd.com\/?p=214"},"modified":"2020-02-01T20:36:19","modified_gmt":"2020-02-01T12:36:19","slug":"usaco-2020-jan","status":"publish","type":"post","link":"https:\/\/wwwwodddd.com\/wordpress\/usaco-2020-jan\/","title":{"rendered":"USACO 2020 JAN"},"content":{"rendered":"

<\/p>\n

Bronze<\/h1>\n

B1<\/h2>\n
import sys\nsys.stdin = open('word.in', 'r')\nsys.stdout = open('word.out', 'w')\nn, m = map(int, input().split())\nl = 0\nfor s in input().split():\n    # print(l, s, len(s))\n    if l + len(s) > m:\n        print()\n        l = 0\n    if l > 0:\n        print(' ', end='')\n    print(s, end='')\n    l += len(s)\nprint()\n<\/code><\/pre>\n
B2<\/h2>\n
import sys\nsys.stdin = open('photo.in', 'r')\nsys.stdout = open('photo.out', 'w')\nn = int(input())\na = list(map(int, input().split()))\ndef F(s):\n    b = [s]\n    for i in range(len(a)):\n        b.append(a[i] - b[i])\n    if len(set(b)) == n and max(b) == n and min(b) == 1:\n        return ' '.join(map(str, b))\n    return None\nfor i in range(1, n):\n    if F(i):\n        print(F(i))\n<\/code><\/pre>\n
B3<\/h2>\n
import sys\nimport math\nsys.stdin = open('race.in', 'r')\nsys.stdout = open('race.out', 'w')\ndef F(t, x):\n    if t <= x:\n        return t * (t + 1) \/\/ 2\n    t += x - 1\n    t1 = t \/\/ 2\n    t2 = t - t1\n    return t1 * (t1 + 1) \/\/ 2 + t2 * (t2 + 1) \/\/ 2 - x * (x - 1) \/\/ 2\nk, n = map(int, input().split())\nfor i in range(n):\n    x = int(input())\n    L = 0\n    R = k\n    while L < R - 1:\n        M = (L + R) \/\/ 2\n        if F(M, x) >= k:\n            R = M\n        else:\n            L = M\n    print(R)\n<\/code><\/pre>\n
Silver<\/h1>\n
S1<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, k;\nint a[1020];\nint b[1020];\nint main()\n{\n    freopen(\"berries.in\", \"r\", stdin);\n    freopen(\"berries.out\", \"w\", stdout);\n    cin >> n >> k;\n    for (int i = 0; i < n; i++)\n    {\n        cin >> a[i];\n    }\n    sort(a, a + n);\n    int ans = 0;\n    for (int i = 1; i <= a[n - 1]; i++)\n    {\n        int cnt = 0;\n        for (int j = 0; j < n; j++)\n        {\n            b[j] = a[j] % i;\n            cnt += a[j] \/ i;\n        }\n        sort(b, b + n);\n        int sum = 0;\n        if (cnt >= k)\n        {\n            sum = i * k \/ 2;\n        }\n        else if (cnt >= k \/ 2)\n        {\n            sum = (cnt - k \/ 2) * i;\n            if (n - (k - cnt) < 0)\n            {\n                continue;\n            }\n            for (int j = n - (k - cnt); j < n; j++)\n            {\n                sum += b[j];\n            }\n        }\n        else\n        {\n            int kk = k \/ 2 - cnt;\n            if (n - kk - k \/ 2 < 0)\n            {\n                continue;\n            }\n            for (int j = n - kk - k \/ 2; j < n - kk; j++)\n            {\n                sum += b[j];\n            }\n        }\n        ans = max(ans, sum);\n    }\n    cout << ans << endl;\n    return 0;\n}\n<\/code><\/pre>\n
S2<\/h2>\n
import sys\nsys.stdin = open('loan.in', 'r')\nsys.stdout = open('loan.out', 'w')\nn, k, m = map(int, input().split())\nL = 1\nR = n + 1\ndef ok(n, x):\n    s = 0\n    kk = 0\n    while kk < k:\n        d = (n - s) \/\/ x\n        if d <= m:\n            return (n - s + m - 1) \/\/ m + kk <= k\n        t = (n - s - d * x) \/\/ d + 1\n        t = min(t, k - kk)\n        kk += t\n        s += t * d\n    return s == n\nwhile L < R - 1:\n    M = (L + R) \/\/ 2\n    if ok(n, M):\n        L = M\n    else:\n        R = M\nprint(L)\n<\/code><\/pre>\n
S3<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, m;\nint p[100020];\nint x[100020];\nint y[100020];\nint z[100020];\nint f[100020];\nint F(int x)\n{\n    return f[x] != x ? f[x] = F(f[x]) : x;\n}\nvoid U(int x, int y)\n{\n    x = F(x);\n    y = F(y);\n    f[x] = y;\n}\nbool ok(int M)\n{\n    for (int i = 1; i <= n; i++)\n    {\n        f[i] = i;\n    }\n    for (int i = 0; i < m; i++)\n    {\n        if (z[i] >= M)\n        {\n            U(x[i], y[i]);\n        }\n    }\n    for (int i = 1; i <= n; i++)\n    {\n        if (F(i) != F(p[i]))\n        {\n            return false;\n        }\n    }\n    return true;\n}\nint main()\n{\n    freopen(\"wormsort.in\", \"r\", stdin);\n    freopen(\"wormsort.out\", \"w\", stdout);\n    scanf(\"%d%d\", &n, &m);\n    for (int i = 1; i <= n; i++)\n    {\n        scanf(\"%d\", &p[i]);\n    }\n    for (int i = 0; i < m; i++)\n    {\n        scanf(\"%d%d%d\", &x[i], &y[i], &z[i]);\n    }\n    int L = 0;\n    int R = 1000000001;\n    while (L < R - 1)\n    {\n        int M = (L + R) \/ 2;\n        if (ok(M))\n        {\n            L = M;\n        }\n        else\n        {\n            R = M;\n        }\n    }\n    if (L == 1000000000)\n    {\n        L = -1;\n    }\n    printf(\"%d\\n\", L);\n    return 0;\n}\n<\/code><\/pre>\n
Gold<\/h1>\n
G1<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, m, c;\nint w[1020];\nint d[1020][1020];\nvector<int> a[1020];\npriority_queue<pair<int, int> > q[1020];\nint main()\n{\n    freopen(\"time.in\", \"r\", stdin);\n    freopen(\"time.out\", \"w\", stdout);\n    cin >> n >> m >> c;\n    int l = 0;\n    for (int i = 1; i <= n; i++)\n    {\n        cin >> w[i];\n        l = max(l, w[i]);\n    }\n    for (int i = 0; i < m; i++)\n    {\n        int x, y, z;\n        cin >> x >> y;\n        a[x].push_back(y);\n    }\n    q[0].push(make_pair(0, 1));\n    for (int x = 0; x < 1000; x++)\n    {\n        while (q[x].size() > 0)\n        {\n            int z = q[x].top().first;\n            int y = q[x].top().second;\n            q[x].pop();\n            if (z != d[x][y])\n            {\n                continue;\n            }\n            for (int i : a[y])\n            {\n                if (d[x + 1][i] < d[x][y] + w[i])\n                {\n                    d[x + 1][i] = d[x][y] + w[i];\n                    q[x + 1].push(make_pair(d[x + 1][i], i));\n                }\n            }\n        }\n    }\n    int ans = 0;\n    for (int i = 0; i < 1001; i++)\n    {\n        ans = max(ans, d[i][1] - c * i * i);\n    }\n    cout << ans << endl;\n    return 0;\n}\n<\/code><\/pre>\n
G2<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, q;\nint v[3000020];\nint a[5020];\nlong long z[5020][5020];\nint main()\n{\n    freopen(\"threesum.in\", \"r\", stdin);\n    freopen(\"threesum.out\", \"w\", stdout);\n    cin >> n >> q;\n    for (int i = 1; i <= n; i++)\n    {\n        cin >> a[i];\n    }\n    for (int i = 1; i <= n; i++)\n    {\n        for (int j = 1; j <= i; j++)\n        {\n            v[a[j] + 1000000] = 0;\n        }\n        for (int j = i - 1; j > 0; j--)\n        {\n            z[j][i] = z[j + 1][i] + z[j][i - 1] - z[j + 1][i - 1];\n            if (1000000 - a[i] - a[j] >= 0)\n            {\n                z[j][i] += v[1000000 - a[i] - a[j]];\n            }\n            v[1000000 + a[j]]++;\n        }\n    }\n    for (int i = 0; i < q; i++)\n    {\n        int l, r;\n        cin >> l >> r;\n        cout << z[l][r] << endl;\n    }\n    return 0;\n}\n<\/code><\/pre>\n
G3<\/h2>\n
\u6ce8\u610f\u9009\u62e9\u76842\u4e2a\u77e9\u5f62\u4e0d\u80fd\u6709\u4efb\u4f55\u91cd\u53e0\u7684\u90e8\u5206\u3002
\n\u8fd9\u6837\u9884\u5904\u7406\u51fa\u6765\u524d\u540e\u51e0\u884c\u7684\u7ed3\u679c\uff0c\u524d\u540e\u51e0\u5217\u7684\u7ed3\u679c\u3002\u679a\u4e3e\u5206\u5272\u7ebf\u5373\u53ef\u3002<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\npair<pair<int, int>, int> a[200020];\nint m, n;\nint l[200020], lc;\nlong long f[200020];\nlong long c[200020];\nlong long G(int x)\n{\n    long long re = 0;\n    for (int i = x; i > 0; i -= i & -i)\n    {\n        re = min(re, c[i]);\n    }\n    return re;\n}\nvoid R(int x, long long y)\n{\n    for (int i = x; i <= lc; i += i & -i)\n    {\n        c[i] = min(c[i], y);\n    }\n}\nint Q(int y)\n{\n    return lower_bound(l, l + lc, y) - l + 1;\n}\nint main()\n{\n    freopen(\"boards.in\", \"r\", stdin);\n    freopen(\"boards.out\", \"w\", stdout);\n    scanf(\"%d%d\", &m, &n);\n    long long ans = 0;\n    for (int i = 0; i < n; i++)\n    {\n        scanf(\"%d%d\", &a[i].first.first, &a[i].first.second);\n        a[i].second = i + 1;\n        l[lc++] = a[i].first.second;\n        scanf(\"%d%d\", &a[i + n].first.first, &a[i + n].first.second);\n        a[i + n].second = -i - 1;\n        l[lc++] = a[i + n].first.second;\n    }\n    sort(a, a + 2 * n);\n    sort(l, l + lc);\n    lc = unique(l, l + lc) - l;\n    for (int i = 0; i < 2 * n; i++)\n    {\n        if (a[i].second > 0)\n        {\n            f[a[i].second] = G(Q(a[i].first.second));\n            f[a[i].second] += a[i].first.first + a[i].first.second;\n        }\n        else\n        {\n            f[-a[i].second] -= a[i].first.first + a[i].first.second;\n            R(Q(a[i].first.second), f[-a[i].second]);\n            ans = min(ans, f[-a[i].second]);\n        }\n    }\n    printf(\"%lld\\n\", ans + 2 * m);\n    return 0;\n}\n<\/code><\/pre>\n
Platinum<\/h1>\n
P1<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, m;\nchar s[1020][1020];\nvector<int> a[1000020];\nint cnt;\nconst int mod = 1000000007;\nint f[1000020];\nint c[1000020];\nint v[1000020];\nint F(int x)\n{\n    return f[x] != x ? f[x] = F(f[x]) : x;\n}\nvoid U(int x, int y)\n{\n    x = F(x);\n    y = F(y);\n    if (x > y)\n    {\n        f[x] = y;\n    }\n    else\n    {\n        f[y] = x; \n    }\n}\nint G(int x)\n{\n    int re = 1;\n    for (int i: a[x])\n    {\n        re = (long long)re * G(i) % mod;\n    }\n    return (re + 1) % mod;\n}\nint main()\n{\n    freopen(\"cave.in\", \"r\", stdin);\n    freopen(\"cave.out\", \"w\", stdout);\n    scanf(\"%d%d\", &n, &m);\n    for (int i = 0; i < n; i++)\n    {\n        scanf(\"%s\", s[i]);\n    }\n    for (int i = 0; i < n * m; i++)\n    {\n        f[i] = i;\n    }\n    for (int i = n - 1; i >= 0; i--)\n    {\n        for (int j = 0; j < m; j++)\n        {\n            if (s[i][j] == '.' && s[i + 1][j] == '.')\n            {\n                U(i * m + j, (i + 1) * m + j);\n            }\n        }\n        for (int j = 1; j < m; j++)\n        {\n            if (s[i][j - 1] == '.' && s[i][j] == '.')\n            {\n                U(i * m + j - 1, i * m + j);\n            }\n        }\n        for (int j = 0; j < m; j++)\n        {\n            if (s[i][j] == '.')\n            {\n                if (F(i * m + j) == i * m + j)\n                {\n                    c[i * m + j] = ++cnt;\n                }\n                else\n                {\n                    c[i * m + j] = c[F(i * m + j)];\n                }\n            }\n        }\n        for (int j = 0; j < m; j++)\n        {\n            if (s[i][j] == '.' && s[i + 1][j] == '.')\n            {\n                a[c[i * m + j]].push_back(c[(i + 1) * m + j]);\n                v[c[(i + 1) * m + j]] = 1;\n            }\n        }\n    }\n    for (int i = 1; i <= cnt; i++)\n    {\n        sort(a[i].begin(), a[i].end());\n        a[i].resize(unique(a[i].begin(), a[i].end()) - a[i].begin());\n    }\n    int ans = 1;\n    for (int i = 1; i <= cnt; i++)\n    {\n        if (v[i] == 0)\n        {\n            ans = (long long)ans * G(i) % mod;\n        }\n    }\n    printf(\"%d\\n\", ans);\n    return 0;\n}\n<\/code><\/pre>\n
P2<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n, m;\nconst int mod = 1000000007;\nint p[50020][20][20], q[50020][20][20];\nint f[20][20][20];\nint g[20][20][20];\nvoid amul(int a[20][20], int b[20][20], int c[20][20])\n{\n    for (int i = 0; i < m; i++)\n    {\n        for (int j = 0; j < m; j++)\n        {\n            c[i][j] = 0;\n        }\n    }\n    for (int i = 0; i < m; i++)\n    {\n        for (int k = 0; k < m; k++)\n        {\n            if (a[i][k] == 0)\n            {\n                continue;\n            }\n            for (int j = 0; j < m; j++)\n            {\n                c[i][j] = (c[i][j] + (long long)a[i][k] * b[k][j]) % mod;\n            }\n        }\n    }\n}\nvoid bmul(int a[20][20], int b[20][20], int c[20][20])\n{\n    for (int i = 0; i < m; i++)\n    {\n        for (int j = 0; j < m; j++)\n        {\n            c[i][j] = 0;\n        }\n    }\n    for (int j = 0; j < m; j++)\n    {\n        for (int k = 0; k < m; k++)\n        {\n            if (b[k][j] == 0)\n            {\n                continue;\n            }\n            for (int i = 0; i < m; i++)\n            {\n                c[i][j] = (c[i][j] + (long long)a[i][k] * b[k][j]) % mod;\n            }\n        }\n    }\n}\nint a[200020];\nint main()\n{\n    freopen(\"nondec.in\", \"r\", stdin);\n    freopen(\"nondec.out\", \"w\", stdout);\n    scanf(\"%d%d\", &n, &m);\n    for (int i = 0; i < m; i++)\n    {\n        for (int j = 0; j < m; j++)\n        {\n            f[i][j][j] = 1;\n            g[i][j][j] = 1;\n        }\n        for (int j = 0; j <= i; j++)\n        {\n            f[i][j][i] += 1;\n            g[i][j][i] = (g[i][j][i] + (mod - 1) \/ 2) % mod;\n        }\n    }\n    for (int i = 0; i < m; i++)\n    {\n        p[0][i][i] = 1;\n        q[0][i][i] = 1;\n    }\n    for (int i = 1; i <= n; i++)\n    {\n        scanf(\"%d\", &a[i]);\n        a[i]--;\n        bmul(p[i - 1], f[a[i]] , p[i]);\n        amul(g[a[i]] , q[i - 1], q[i]);\n    }\n    int t, l, r;\n    scanf(\"%d\", &t);\n    for (int i = 0; i < t; i++)\n    {\n        scanf(\"%d%d\", &l, &r);\n        l--;\n        int ans = 0;\n        for (int i = 0; i < m; i++)\n        {\n            for (int j = 0; j < m; j++)\n            {\n                ans = (ans + (long long)q[l][0][i] * p[r][i][j]) % mod;\n            }\n        }\n        printf(\"%d\\n\", ans);\n    }\n    \/\/ fprintf(stderr, \"cnt=%d\\n\", cnt);\n    return 0;\n}\n<\/code><\/pre>\n
P3<\/h2>\n
#include <bits\/stdc++.h>\nusing namespace std;\nint n;\npair<pair<int, int>, pair<int, int> > a[200020];\nint z[200020];\nint y[200020];\nint p[200020];\npair<int, int> s[200020];\nint ss;\nbool judge(pair<int, int> a, pair<int, int> b, pair<int, int> c)\n{\n    \/\/ cout << \"judge\" << endl;\n    \/\/ cout << a.first << ' ' << a.second << endl;\n    \/\/ cout << b.first << ' ' << b.second << endl;\n    \/\/ cout << c.first << ' ' << c.second << endl;\n    \/\/ cout << \"return \" << ((long long)(b.first - a.first) * (a.second - c.second) <= (long long)(c.first - a.first) * (a.second - b.second)) << endl;\n    return (long long)(b.first - a.first) * (a.second - c.second) <= (long long)(c.first - a.first) * (a.second - b.second);\n}\nint gcd(int x, int y)\n{\n    return y ? gcd(y, x % y) : x;\n}\nint main()\n{\n    freopen(\"falling.in\", \"r\", stdin);\n    freopen(\"falling.out\", \"w\", stdout);\n    scanf(\"%d\", &n);\n    for (int i = 0; i < n; i++)\n    {\n        scanf(\"%d\", &a[i].first.first);\n        a[i].first.second = -i - 1;\n    }\n    for (int i = 0; i < n; i++)\n    {\n        a[i].second.first = i;\n        scanf(\"%d\", &a[i].second.second);\n        a[i].second.second--;\n    }\n    sort(a, a + n);\n    for (int i = 0; i < n; i++)\n    {\n        p[a[i].second.first] = i;\n        y[a[i].second.first] = 1;\n    }\n    ss = 0;\n    for (int i = 0; i < n; i++)\n    {\n        while ((ss >= 1 && s[ss - 1].second < a[i].first.second) || (ss >= 2 && judge(s[ss - 2], s[ss - 1], a[i].first)))\n        {\n            ss--;\n        }\n        s[ss++] = a[i].first;\n        if (p[a[i].second.second] > i)\n        {\n            int L = 0;\n            int R = ss;\n            pair<int, int> u = a[p[a[i].second.second]].first;\n            while (L < R - 1)\n            {\n                int M = (L + R) \/ 2;\n                \/\/ cout << \"binary search before \" << L << ' ' << R << endl;\n                if ((ss >= 1 && s[M].second < u.second) || (M >= 1 && judge(s[M - 1], s[M], u)))\n                {\n                    R = M;\n                }\n                else\n                {\n                    L = M;\n                }\n                \/\/ cout << \"binary search after \" << L << ' ' << R << endl;\n            }\n            \/\/ cout << \"query \"  << L << endl;\n            if (s[L].second < u.second)\n            {\n                z[a[i].second.first] = -1;\n            }\n            else\n            {\n                z[a[i].second.first] = (u.first - s[L].first);\n                y[a[i].second.first] = (s[L].second - u.second);\n            }\n        }\n        \/\/ for (int i = 0; i < ss; i++)\n        \/\/ {\n        \/\/  cout << s[i].first << ' ' << s[i].second << endl;\n        \/\/ }\n        \/\/ cout << endl;\n    }\n    ss = 0;\n    for (int i = n - 1; i >= 0; i--)\n    {\n        a[i].first.first = -a[i].first.first;\n        a[i].first.second = -a[i].first.second;\n    }\n    for (int i = n - 1; i >= 0; i--)\n    {\n        while ((ss >= 1 && s[ss - 1].second < a[i].first.second) || (ss >= 2 && judge(s[ss - 2], s[ss - 1], a[i].first)))\n        {\n            ss--;\n        }\n        s[ss++] = a[i].first;\n        if (p[a[i].second.second] < i)\n        {\n            int L = 0;\n            int R = ss;\n            pair<int, int> u = a[p[a[i].second.second]].first;\n            while (L < R - 1)\n            {\n                int M = (L + R) \/ 2;\n                if ((ss >= 1 && s[M].second < u.second) || (M >= 1 && judge(s[M - 1], s[M], u)))\n                {\n                    R = M;\n                }\n                else\n                {\n                    L = M;\n                }\n            }\n            if (s[L].second < u.second)\n            {\n                z[a[i].second.first] = -1;\n            }\n            else\n            {\n                z[a[i].second.first] = (u.first - s[L].first);\n                y[a[i].second.first] = (s[L].second - u.second);\n            }\n        }\n    }\n    for (int i = 0; i < n; i++)\n    {\n        if (z[i] == -1)\n        {\n            printf(\"%d\\n\", z[i]);\n        }\n        else\n        {\n            int g = gcd(z[i], y[i]);\n            z[i] \/= g;\n            y[i] \/= g;\n            printf(\"%d\/%d\\n\", z[i], y[i]);\n        }\n    }\n    return 0;\n}\n<\/code><\/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":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-214","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/214","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=214"}],"version-history":[{"count":0,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/214\/revisions"}],"wp:attachment":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/media?parent=214"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/categories?post=214"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/tags?post=214"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}