codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1245.md (9874B)


      1 Source: https://codeforces.com/blog/entry/71080
      2 
      3 [1245A - Good ol' Numbers Coloring](/contest/1245/problem/A "Codeforces Round 597 (Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 using namespace std;
     14 
     15 int gcd(int a, int b)
     16 {
     17     while (b)
     18     {
     19         a %= b;
     20         swap(a, b);
     21     }
     22     
     23     return a;
     24 }
     25 
     26 int main()
     27 {
     28     int t;
     29     for (cin >> t; t--;)
     30     
     31     {
     32         int a, b;
     33         cin >> a >> b;
     34         
     35         if (gcd(a, b) == 1)
     36             cout << "Finite" << '\n';
     37         else
     38             cout << "Infinite" << '\n';
     39     }
     40     
     41     return 0;
     42 }
     43 ```
     44 
     45 [1245B - Restricted RPS](/contest/1245/problem/B "Codeforces Round 597 (Div. 2)")
     46 
     47 **Tutorial**
     48 
     49 Tutorial is loading...
     50 
     51 **Solution**
     52 
     53 ```
     54 #include <vector>
     55 #include <string>
     56 #include <iostream>
     57 #include <cstdio>
     58 #include <algorithm>
     59 #include <stack>
     60 #include <queue>
     61 #include <deque>
     62 #include <set>
     63 #include <map>
     64 using namespace std;
     65 
     66 int main()
     67 {
     68     ios_base::sync_with_stdio(0);
     69     cin.tie(0);
     70     
     71     int q;
     72     for (cin >> q; q--;)
     73     {
     74         int n;
     75         cin >> n;
     76         int a, b, c;
     77         cin >> a >> b >> c;
     78         string s;
     79         cin >> s;
     80         
     81         vector<int> count(26);
     82         for (char x : s)
     83         	count[x - 'A']++;
     84         
     85         int wins = min(a, count['S' - 'A']) + min(b, count['R' - 'A']) + min(c, count['P' - 'A']);
     86         
     87         if (2 * wins < n)
     88         {
     89         	cout << "NO" << '\n';continue;
     90         }
     91         
     92         cout << "YES" << '\n';
     93         string t;
     94         for (int i = 0; i != n; ++i)
     95         {
     96         	if (s[i] == 'S' && a)
     97         	{
     98         		t += 'R';
     99         		a--;
    100         	}
    101         	else if (s[i] == 'R' && b)
    102         	{
    103         		t += 'P';
    104         		b--;
    105         	}
    106         	else if (s[i] == 'P' && c)
    107         	{
    108         		t += 'S';
    109         		c--;
    110         	}
    111         	else
    112         		t += '_';
    113         }
    114         for (int i = 0; i != n; ++i)
    115         {
    116         	if (t[i] != '_')
    117         		continue;
    118         	
    119         	if (a)
    120         	{
    121         		t[i] = 'R';
    122         		a--;
    123         	}
    124         	else if (b)
    125         	{
    126         		t[i] = 'P';
    127         		b--;
    128         	}
    129         	else
    130         	{
    131         		t[i] = 'S';
    132         		c--;
    133         	}
    134         }
    135         cout << t << '\n';
    136     }
    137     
    138     return 0;
    139 }
    140 ```
    141 
    142 [1245C - Constanze's Machine](/contest/1245/problem/C "Codeforces Round 597 (Div. 2)")
    143 
    144 **Tutorial**
    145 
    146 Tutorial is loading...
    147 
    148 **Solution**
    149 
    150 ```
    151 #include <vector>
    152 #include <string>
    153 #include <iostream>
    154 #include <cstdio>
    155 #include <algorithm>
    156 #include <stack>
    157 #include <queue>
    158 #include <deque>
    159 #include <set>
    160 #include <map>
    161 using namespace std;
    162 
    163 const int MOD = 1000000007;
    164 
    165 int main()
    166 {
    167     ios_base::sync_with_stdio(0);
    168     cin.tie(0);
    169     
    170     string s;
    171     cin >> s;
    172     
    173     for (char x : s)
    174     {
    175         if (x == 'w' || x == 'm')
    176         {
    177             cout << 0 << '\n';
    178             return 0;
    179         }
    180     }
    181     
    182     int n = s.size();
    183     vector<int> dp(n + 1);
    184     dp[0] = 1;
    185     dp[1] = 1;
    186     for (int i = 2; i <= n; ++i)
    187     {
    188         dp[i] = dp[i - 1];
    189         if (s[i - 1] == s[i - 2] && (s[i - 1] == 'u' || s[i - 1] == 'n'))
    190             dp[i] = (dp[i] + dp[i - 2]) % MOD;
    191     }
    192     
    193     cout << dp[n] << '\n';
    194     
    195     return 0;
    196 }
    197 ```
    198 
    199 **Solution (Arpa)**
    200 
    201 ```
    202 // In the name of Allah.
    203 // We're nothing and you're everything.
    204 // Ya Ali!
    205  
    206 #include <bits/stdc++.h>
    207 using namespace std;
    208 typedef long long ll;
    209  
    210 const int maxn = 1e5 + 14, mod = 1e9 + 7;
    211 
    212 int n, fib[maxn];
    213 
    214 int main(){
    215     ios::sync_with_stdio(0), cin.tie(0);
    216     fib[0] = fib[1] = 1;
    217     for(int i = 2; i < maxn; i++)
    218         fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
    219     string s;
    220     cin >> s;
    221     n = s.size();
    222     if(s.find('m') != -1 || s.find('w') != -1)
    223         return cout << "0\n", 0;
    224     int ans = 1;
    225     for(int i = 0, j = 0; i < n; i = j){
    226         while(j < n && s[j] == s[i])
    227             j++;
    228         if(s[i] == 'n' || s[i] == 'u')
    229             ans = (ll) ans * fib[j - i] % mod;
    230     }
    231     cout << ans << '\n';
    232 }
    233 ```
    234 
    235 [1245D - Shichikuji and Power Grid](/contest/1245/problem/D "Codeforces Round 597 (Div. 2)")
    236 
    237 **Tutorial**
    238 
    239 Tutorial is loading...
    240 
    241 **Solution**
    242 
    243 ```
    244 #include <vector>
    245 #include <string>
    246 #include <iostream>
    247 #include <cstdio>
    248 #include <algorithm>
    249 #include <stack>
    250 #include <queue>
    251 #include <deque>
    252 #include <set>
    253 #include <map>
    254 using namespace std;
    255 
    256 int main()
    257 {
    258     ios_base::sync_with_stdio(0);
    259     cin.tie(0);
    260     
    261     int n;
    262     cin >> n;
    263     pair<int, int> pos[n];
    264     for (int i = 0; i != n; ++i)
    265         cin >> pos[i].first >> pos[i].second;
    266     int c[n];
    267     for (int i = 0; i != n; ++i)
    268         cin >> c[i];
    269     int k[n];
    270     for (int i = 0; i != n; ++i)
    271         cin >> k[i];
    272     
    273     long long ans = 0;
    274     vector<int> power_plants;
    275     vector<pair<int, int>> connections;
    276     
    277     vector<bool> done(n);
    278     vector<int> parent(n, -1);
    279     for (int _n = n; _n--;)
    280     {
    281         int mi = 2000000000;
    282         int u = -1;
    283         for (int i = 0; i != n; ++i)
    284         {
    285             if (done[i])
    286                 continue;
    287             
    288             if (c[i] < mi)
    289             {
    290                 mi = c[i];
    291                 u = i;
    292             }
    293         }
    294         
    295         ans += mi;
    296         done[u] = 1;
    297         if (parent[u] == -1)
    298             power_plants.push_back(u);
    299         else
    300             connections.push_back(make_pair(min(parent[u], u), max(parent[u], u)));
    301         
    302         for (int i = 0; i != n; ++i)
    303             if (1LL * (k[u] + k[i]) * (abs(pos[u].first - pos[i].first) + abs(pos[u].second - pos[i].second)) < c[i])
    304             {
    305                 c[i] = (k[u] + k[i]) * (abs(pos[u].first - pos[i].first) + abs(pos[u].second - pos[i].second));
    306                 parent[i] = u;
    307             }
    308     }
    309     
    310     cout << ans << '\n';
    311     cout << power_plants.size() << '\n';
    312     sort(power_plants.begin(), power_plants.end());
    313     for (int x : power_plants)
    314         cout << x + 1 << ' ';
    315     cout << '\n';
    316     cout << connections.size() << '\n';
    317     for (pair<int, int> x : connections)
    318         cout << x.first + 1 << ' ' << x.second + 1 << '\n';
    319     
    320     return 0;
    321 }
    322 ```
    323 
    324 **Solution (PikMike)**
    325 
    326 ```
    327 #include <bits/stdc++.h>
    328 
    329 using namespace std;
    330 
    331 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    332 
    333 int main(){
    334     int n;
    335     scanf("%d", &n);
    336     vector<int> x(n), y(n);
    337     forn(i, n)
    338         scanf("%d%d", &x[i], &y[i]);
    339     vector<int> c(n), k(n);
    340     forn(i, n)
    341         scanf("%d", &c[i]);
    342     forn(i, n)
    343         scanf("%d", &k[i]);
    344     
    345     ++n;
    346     vector<int> p(n, -1);
    347     vector<int> d(n, int(1e9));
    348     vector<bool> used(n);
    349     
    350     forn(i, n - 1){
    351         d[i] = c[i];
    352         p[i] = n - 1;
    353     }
    354     used[n - 1] = true;
    355     
    356     long long ans = 0;
    357     vector<int> vv;
    358     vector<pair<int, int>> ee;
    359     
    360     forn(_, n - 1){
    361         int v = -1;
    362         forn(i, n) if (!used[i] && (v == -1 || d[v] > d[i]))
    363             v = i;
    364         
    365         if (p[v] == n - 1)
    366             vv.push_back(v + 1);
    367         else
    368             ee.push_back(make_pair(v + 1, p[v] + 1));
    369         ans += d[v];
    370         
    371         used[v] = true;
    372         forn(i, n) if (!used[i]){
    373             long long dist = (k[v] + k[i]) * 1ll * (abs(x[v] - x[i]) + abs(y[v] - y[i]));
    374             if (dist < d[i]){
    375                 d[i] = dist;
    376                 p[i] = v;
    377             }
    378         }
    379     }
    380     
    381     printf("%lld\n", ans);
    382     printf("%d\n", int(vv.size()));
    383     for (auto it : vv)
    384         printf("%d ", it);
    385     puts("");
    386     printf("%d\n", int(ee.size()));
    387     for (auto it : ee)
    388         printf("%d %d\n", it.first, it.second);
    389 }
    390 ```
    391 
    392 [1245E - Hyakugoku and Ladders](/contest/1245/problem/E "Codeforces Round 597 (Div. 2)")
    393 
    394 **Tutorial**
    395 
    396 Tutorial is loading...
    397 
    398 **Solution**
    399 
    400 ```
    401 #include <bits/stdc++.h>
    402 using namespace std;
    403 
    404 int main()
    405 {
    406     ios_base::sync_with_stdio(0);
    407     cin.tie(0);
    408     
    409     int grid[10][10];
    410     for (int i = 0; i != 10; ++i)
    411         for (int j = 0; j != 10; ++j)
    412             cin >> grid[i][j];
    413     
    414     int flat[10][10];
    415     for (int i = 0; i != 10; ++i)
    416         for (int j = 0; j != 10; ++j)
    417                 flat[i][j] = (9 - i) * 10 + ((i & 1) ? j : 9 - j);
    418     
    419     int d = 1;
    420     int x = 9;
    421     int y = 0;
    422     int arr[100];
    423     for (int i = 0; i != 100; ++i)
    424     {
    425         arr[i] = flat[x - grid[x][y]][y];
    426         
    427         if (y + d == -1 || y + d == 10)
    428         {
    429             d *= -1;
    430             x--;
    431         }
    432         else
    433             y += d;
    434     }
    435     
    436     double dp[100];
    437     dp[99] = 0;
    438     for (int i = 98; i >= 0; --i)
    439     {
    440         dp[i] = 1;
    441         
    442         int c = 6;
    443         for (int r = 1; r <= 6; ++r)
    444         {
    445             if (i + r >= 100)
    446                 continue;
    447             dp[i] += min(dp[i + r], dp[arr[i + r]]) / 6;
    448             c--;
    449         }
    450         
    451         dp[i] = 6 * dp[i] / (6 - c);
    452     }
    453     
    454     cout << setprecision(10) << fixed << dp[0] << '\n';
    455     
    456     return 0;
    457 }
    458 ```
    459 
    460 [1245F - Daniel and Spring Cleaning](/contest/1245/problem/F "Codeforces Round 597 (Div. 2)")
    461 
    462 **Tutorial**
    463 
    464 Tutorial is loading...
    465 
    466 **Solution**
    467 
    468 ```
    469 #include<bits/stdc++.h>
    470 using namespace std;
    471 
    472 int f(int a, int b)
    473 {
    474     int ret = 0;
    475     int zeroes = 0;
    476     
    477     for (int i = 1; i <= b; i <<= 1)
    478     {
    479         if (b & i)
    480         {
    481             b ^= i;
    482             
    483             if (!(a & b))
    484                 ret += 1 << zeroes;
    485         }
    486         
    487         if (!(a & i))
    488             zeroes++;
    489     }
    490     
    491     return ret;
    492 }
    493 
    494 long long rec(int a, int b)
    495 {
    496     if (a == b)
    497         return 0;
    498     if (a == 0)
    499         return 2 * b - 1 + rec(1, b);
    500     
    501     long long ret = 0;
    502     if (a & 1)
    503     {
    504         ret += 2 * (f(a, b) - f(a, a));
    505         a++;
    506     }
    507     if (b & 1)
    508     {
    509         ret += 2 * (f(b - 1, b) - f(b - 1, a));
    510         b--;
    511     }
    512     
    513     return ret + 3 * rec(a / 2, b / 2);
    514 }
    515 
    516 int main()
    517 {
    518     int t;
    519     for (cin >> t; t--;)
    520     {
    521         int a, b;
    522         cin >> a >> b;
    523         cout << rec(a, b + 1) << '\n';
    524     }
    525     
    526     return 0;
    527 }
    528 ```