Codeforces Round #597 (Div. 2) Editorial 
Difference between en3 and en4, changed 0 character(s)
[problem:1245A]↵

<spoiler summary="Tutorial">↵
[tutorial:1245A]↵
</spoiler>↵

<spoiler summary="Solution">↵

~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

int gcd(int a, int b)↵
{↵
    while (b)↵
    {↵
        a %= b;↵
        swap(a, b);↵
    }↵
    ↵
    return a;↵
}↵

int main()↵
{↵
    int t;↵
    for (cin >> t; t--;)↵
    ↵
    {↵
        int a, b;↵
        cin >> a >> b;↵
        ↵
        if (gcd(a, b) == 1)↵
            cout << "Finite" << '\n';↵
        else↵
            cout << "Infinite" << '\n';↵
    }↵
    ↵
    return 0;↵
}↵
~~~~~↵


</spoiler>↵

[problem:1245B]↵

<spoiler summary="Tutorial">↵
[tutorial:1245B]↵
</spoiler>↵

<spoiler summary="Solution">↵

~~~~~↵
#include <vector>↵
#include <string>↵
#include <iostream>↵
#include <cstdio>↵
#include <algorithm>↵
#include <stack>↵
#include <queue>↵
#include <deque>↵
#include <set>↵
#include <map>↵
using namespace std;↵

int main()↵
{↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0);↵
    ↵
    int q;↵
    for (cin >> q; q--;)↵
    {↵
        int n;↵
        cin >> n;↵
        int a, b, c;↵
        cin >> a >> b >> c;↵
        string s;↵
        cin >> s;↵
        ↵
        vector<int> count(26);↵
        for (char x : s)↵
         count[x - 'A']++;↵
        ↵
        int wins = min(a, count['S' - 'A']) + min(b, count['R' - 'A']) + min(c, count['P' - 'A']);↵
        ↵
        if (2 * wins < n)↵
        {↵
         cout << "NO" << '\n';continue;↵
        }↵
        ↵
        cout << "YES" << '\n';↵
        string t;↵
        for (int i = 0; i != n; ++i)↵
        {↵
         if (s[i] == 'S' && a)↵
         {↵
         t += 'R';↵
         a--;↵
         }↵
         else if (s[i] == 'R' && b)↵
         {↵
         t += 'P';↵
         b--;↵
         }↵
         else if (s[i] == 'P' && c)↵
         {↵
         t += 'S';↵
         c--;↵
         }↵
         else↵
         t += '_';↵
        }↵
        for (int i = 0; i != n; ++i)↵
        {↵
         if (t[i] != '_')↵
         continue;↵
         ↵
         if (a)↵
         {↵
         t[i] = 'R';↵
         a--;↵
         }↵
         else if (b)↵
         {↵
         t[i] = 'P';↵
         b--;↵
         }↵
         else↵
         {↵
         t[i] = 'S';↵
         c--;↵
         }↵
        }↵
        cout << t << '\n';↵
    }↵
    ↵
    return 0;↵
}↵
~~~~~↵


</spoiler>↵

[problem:1245C]↵

<spoiler summary="Tutorial">↵
[tutorial:1245C]↵
</spoiler>↵

<spoiler summary="Solution">↵

~~~~~↵
#include <vector>↵
#include <string>↵
#include <iostream>↵
#include <cstdio>↵
#include <algorithm>↵
#include <stack>↵
#include <queue>↵
#include <deque>↵
#include <set>↵
#include <map>↵
using namespace std;↵

const int MOD = 1000000007;↵

int main()↵
{↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0);↵
    ↵
    string s;↵
    cin >> s;↵
    ↵
    for (char x : s)↵
    {↵
        if (x == 'w' || x == 'm')↵
        {↵
            cout << 0 << '\n';↵
            return 0;↵
        }↵
    }↵
    ↵
    int n = s.size();↵
    vector<int> dp(n + 1);↵
    dp[0] = 1;↵
    dp[1] = 1;↵
    for (int i = 2; i <= n; ++i)↵
    {↵
        dp[i] = dp[i - 1];↵
        if (s[i - 1] == s[i - 2] && (s[i - 1] == 'u' || s[i - 1] == 'n'))↵
            dp[i] = (dp[i] + dp[i - 2]) % MOD;↵
    }↵
    ↵
    cout << dp[n] << '\n';↵
    ↵
    return 0;↵
}↵
~~~~~↵

</spoiler>↵

<spoiler summary="Solution (Arpa)">↵

~~~~~↵
// In the name of Allah.↵
// We're nothing and you're everything.↵
// Ya Ali!↵
 ↵
#include <bits/stdc++.h>↵
using namespace std;↵
typedef long long ll;↵
 ↵
const int maxn = 1e5 + 14, mod = 1e9 + 7;↵

int n, fib[maxn];↵

int main(){↵
    ios::sync_with_stdio(0), cin.tie(0);↵
    fib[0] = fib[1] = 1;↵
    for(int i = 2; i < maxn; i++)↵
        fib[i] = (fib[i - 1] + fib[i - 2]) % mod;↵
    string s;↵
    cin >> s;↵
    n = s.size();↵
    if(s.find('m') != -1 || s.find('w') != -1)↵
        return cout << "0\n", 0;↵
    int ans = 1;↵
    for(int i = 0, j = 0; i < n; i = j){↵
        while(j < n && s[j] == s[i])↵
            j++;↵
        if(s[i] == 'n' || s[i] == 'u')↵
            ans = (ll) ans * fib[j - i] % mod;↵
    }↵
    cout << ans << '\n';↵
}↵
~~~~~↵

</spoiler>↵


[problem:1245D]↵

<spoiler summary="Tutorial">↵
[tutorial:1245D]↵
</spoiler>↵

<spoiler summary="Solution">↵

~~~~~↵
#include <vector>↵
#include <string>↵
#include <iostream>↵
#include <cstdio>↵
#include <algorithm>↵
#include <stack>↵
#include <queue>↵
#include <deque>↵
#include <set>↵
#include <map>↵
using namespace std;↵

int main()↵
{↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0);↵
    ↵
    int n;↵
    cin >> n;↵
    pair<int, int> pos[n];↵
    for (int i = 0; i != n; ++i)↵
        cin >> pos[i].first >> pos[i].second;↵
    int c[n];↵
    for (int i = 0; i != n; ++i)↵
        cin >> c[i];↵
    int k[n];↵
    for (int i = 0; i != n; ++i)↵
        cin >> k[i];↵
    ↵
    long long ans = 0;↵
    vector<int> power_plants;↵
    vector<pair<int, int>> connections;↵
    ↵
    vector<bool> done(n);↵
    vector<int> parent(n, -1);↵
    for (int _n = n; _n--;)↵
    {↵
        int mi = 2000000000;↵
        int u = -1;↵
        for (int i = 0; i != n; ++i)↵
        {↵
            if (done[i])↵
                continue;↵
            ↵
            if (c[i] < mi)↵
            {↵
                mi = c[i];↵
                u = i;↵
            }↵
        }↵
        ↵
        ans += mi;↵
        done[u] = 1;↵
        if (parent[u] == -1)↵
            power_plants.push_back(u);↵
        else↵
            connections.push_back(make_pair(min(parent[u], u), max(parent[u], u)));↵
        ↵
        for (int i = 0; i != n; ++i)↵
            if (1LL * (k[u] + k[i]) * (abs(pos[u].first - pos[i].first) + abs(pos[u].second - pos[i].second)) < c[i])↵
            {↵
                c[i] = (k[u] + k[i]) * (abs(pos[u].first - pos[i].first) + abs(pos[u].second - pos[i].second));↵
                parent[i] = u;↵
            }↵
    }↵
    ↵
    cout << ans << '\n';↵
    cout << power_plants.size() << '\n';↵
    sort(power_plants.begin(), power_plants.end());↵
    for (int x : power_plants)↵
        cout << x + 1 << ' ';↵
    cout << '\n';↵
    cout << connections.size() << '\n';↵
    for (pair<int, int> x : connections)↵
        cout << x.first + 1 << ' ' << x.second + 1 << '\n';↵
    ↵
    return 0;↵
}↵
~~~~~↵

</spoiler>↵

<spoiler summary="Solution (PikMike)">↵

~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

#define forn(i, n) for(int i = 0; i < int(n); i++) ↵

int main(){↵
    int n;↵
    scanf("%d", &n);↵
    vector<int> x(n), y(n);↵
    forn(i, n)↵
        scanf("%d%d", &x[i], &y[i]);↵
    vector<int> c(n), k(n);↵
    forn(i, n)↵
        scanf("%d", &c[i]);↵
    forn(i, n)↵
        scanf("%d", &k[i]);↵
    ↵
    ++n;↵
    vector<int> p(n, -1);↵
    vector<int> d(n, int(1e9));↵
    vector<bool> used(n);↵
    ↵
    forn(i, n - 1){↵
        d[i] = c[i];↵
        p[i] = n - 1;↵
    }↵
    used[n - 1] = true;↵
    ↵
    long long ans = 0;↵
    vector<int> vv;↵
    vector<pair<int, int>> ee;↵
    ↵
    forn(_, n - 1){↵
        int v = -1;↵
        forn(i, n) if (!used[i] && (v == -1 || d[v] > d[i]))↵
            v = i;↵
        ↵
        if (p[v] == n - 1)↵
            vv.push_back(v + 1);↵
        else↵
            ee.push_back(make_pair(v + 1, p[v] + 1));↵
        ans += d[v];↵
        ↵
        used[v] = true;↵
        forn(i, n) if (!used[i]){↵
            long long dist = (k[v] + k[i]) * 1ll * (abs(x[v] - x[i]) + abs(y[v] - y[i]));↵
            if (dist < d[i]){↵
                d[i] = dist;↵
                p[i] = v;↵
            }↵
        }↵
    }↵
    ↵
    printf("%lld\n", ans);↵
    printf("%d\n", int(vv.size()));↵
    for (auto it : vv)↵
        printf("%d ", it);↵
    puts("");↵
    printf("%d\n", int(ee.size()));↵
    for (auto it : ee)↵
        printf("%d %d\n", it.first, it.second);↵
}↵
~~~~~↵

</spoiler>↵

[problem:1245E]↵

<spoiler summary="Tutorial">↵
[tutorial:1245E]↵
</spoiler>↵

<spoiler summary="Solution">↵

~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

int main()↵
{↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0);↵
    ↵
    int grid[10][10];↵
    for (int i = 0; i != 10; ++i)↵
        for (int j = 0; j != 10; ++j)↵
            cin >> grid[i][j];↵
    ↵
    int flat[10][10];↵
    for (int i = 0; i != 10; ++i)↵
        for (int j = 0; j != 10; ++j)↵
                flat[i][j] = (9 - i) * 10 + ((i & 1) ? j : 9 - j);↵
    ↵
    int d = 1;↵
    int x = 9;↵
    int y = 0;↵
    int arr[100];↵
    for (int i = 0; i != 100; ++i)↵
    {↵
        arr[i] = flat[x - grid[x][y]][y];↵
        ↵
        if (y + d == -1 || y + d == 10)↵
        {↵
            d *= -1;↵
            x--;↵
        }↵
        else↵
            y += d;↵
    }↵
    ↵
    double dp[100];↵
    dp[99] = 0;↵
    for (int i = 98; i >= 0; --i)↵
    {↵
        dp[i] = 1;↵
        ↵
        int c = 6;↵
        for (int r = 1; r <= 6; ++r)↵
        {↵
            if (i + r >= 100)↵
                continue;↵
            dp[i] += min(dp[i + r], dp[arr[i + r]]) / 6;↵
            c--;↵
        }↵
        ↵
        dp[i] = 6 * dp[i] / (6 - c);↵
    }↵
    ↵
    cout << setprecision(10) << fixed << dp[0] << '\n';↵
    ↵
    return 0;↵
}↵
~~~~~↵

</spoiler>↵


[problem:1245F]↵

<spoiler summary="Tutorial">↵
[tutorial:1245F]↵
</spoiler>↵

<spoiler summary="Solution">↵

~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵

int f(int a, int b)↵
{↵
    int ret = 0;↵
    int zeroes = 0;↵
    ↵
    for (int i = 1; i <= b; i <<= 1)↵
    {↵
        if (b & i)↵
        {↵
            b ^= i;↵
            ↵
            if (!(a & b))↵
                ret += 1 << zeroes;↵
        }↵
        ↵
        if (!(a & i))↵
            zeroes++;↵
    }↵
    ↵
    return ret;↵
}↵

long long rec(int a, int b)↵
{↵
    if (a == b)↵
        return 0;↵
    if (a == 0)↵
        return 2 * b - 1 + rec(1, b);↵
    ↵
    long long ret = 0;↵
    if (a & 1)↵
    {↵
        ret += 2 * (f(a, b) - f(a, a));↵
        a++;↵
    }↵
    if (b & 1)↵
    {↵
        ret += 2 * (f(b - 1, b) - f(b - 1, a));↵
        b--;↵
    }↵
    ↵
    return ret + 3 * rec(a / 2, b / 2);↵
}↵

int main()↵
{↵
    int t;↵
    for (cin >> t; t--;)↵
    {↵
        int a, b;↵
        cin >> a >> b;↵
        cout << rec(a, b + 1) << '\n';↵
    }↵
    ↵
    return 0;↵
}↵
~~~~~↵


</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English DeliciousFlatChest 2019-11-01 19:43:15 0 (published)
en5 English DeliciousFlatChest 2019-11-01 19:40:22 0 (saved to drafts)
en4 English DeliciousFlatChest 2019-11-01 19:36:55 0 (published)
en3 English DeliciousFlatChest 2019-11-01 17:30:39 2 Tiny change: 'econd);\n}~~~~~\n\n<' -> 'econd);\n}\n~~~~~\n\n<'
en2 English DeliciousFlatChest 2019-11-01 17:27:35 2972
en1 English DeliciousFlatChest 2019-11-01 15:34:27 8760 Initial revision (saved to drafts)