Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Tutorial

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;
}

1245B - Restricted RPS

Tutorial

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;
}

1245C - Constanze's Machine

Tutorial

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;
}

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';
}

1245D - Shichikuji and Power Grid

Tutorial

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;
}

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);
}

1245E - Hyakugoku and Ladders

Tutorial

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;
}

1245F - Daniel and Spring Cleaning

Tutorial

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;
}

Full text and comments »

DeliciousFlatChest's blog