codeforces-scrape

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

1674.md (7109B)


      1 Source: https://codeforces.com/blog/entry/102482
      2 
      3 [1674A - Number Transformation](/contest/1674/problem/A "Codeforces Round 786 (Div. 3)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     x, y = map(int, input().split())
     17     if y % x != 0:
     18         print(0, 0)
     19     else:
     20         print(1, y // x)
     21 ```
     22 
     23 [1674B - Dictionary](/contest/1674/problem/B "Codeforces Round 786 (Div. 3)")
     24 
     25 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     26 
     27 **Tutorial**
     28 
     29 Tutorial is loading...
     30 
     31 **Solution (BledDest)**
     32 
     33 ```
     34 #include <bits/stdc++.h>
     35  
     36 using namespace std;
     37  
     38 int main() 
     39 {
     40     string w = "aa";
     41     map<string, int> idx;
     42     int i = 1;
     43     for(w[0] = 'a'; w[0] <= 'z'; w[0]++)
     44         for(w[1] = 'a'; w[1] <= 'z'; w[1]++)
     45             if(w[0] != w[1])
     46                 idx[w] = i++;
     47     int t;
     48     cin >> t;
     49     for(int i = 0; i < t; i++)
     50     {
     51         string s;
     52         cin >> s;
     53         cout << idx[s] << endl;
     54     }   
     55 }
     56 ```
     57 
     58 [1674C - Infinite Replacement](/contest/1674/problem/C "Codeforces Round 786 (Div. 3)")
     59 
     60 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     61 
     62 **Tutorial**
     63 
     64 Tutorial is loading...
     65 
     66 **Solution (awoo)**
     67 
     68 ```
     69 for _ in range(int(input())):
     70     s = input()
     71     t = input()
     72     if t == "a":
     73         print(1)
     74     elif t.count('a') != 0:
     75         print(-1)
     76     else:
     77         print(2**len(s))
     78 ```
     79 
     80 [1674D - A-B-C Sort](/contest/1674/problem/D "Codeforces Round 786 (Div. 3)")
     81 
     82 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     83 
     84 **Tutorial**
     85 
     86 Tutorial is loading...
     87 
     88 **Solution (adedalic)**
     89 
     90 ```
     91 fun main() {
     92     repeat(readLine()!!.toInt()) {
     93         val n = readLine()!!.toInt()
     94         val a = readLine()!!.split(' ').map { it.toInt() }.toIntArray()
     95         for (i in (n % 2) until n step 2) {
     96             if (a[i] > a[i + 1])
     97                 a[i] = a[i + 1].also { a[i + 1] = a[i] }
     98         }
     99         var sorted = true
    100         for (i in a.indices)
    101             if (i > 0 && a[i - 1] > a[i])
    102                 sorted = false
    103         println(if(sorted) "YES" else "NO")
    104     }
    105 }
    106 ```
    107 
    108 [1674E - Breaking the Wall](/contest/1674/problem/E "Codeforces Round 786 (Div. 3)")
    109 
    110 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    111 
    112 **Tutorial**
    113 
    114 Tutorial is loading...
    115 
    116 **Solution (fcspartakm)**
    117 
    118 ```
    119 #include <iostream>
    120 #include <sstream>
    121 #include <cstdio>
    122 #include <vector>
    123 #include <cmath>
    124 #include <queue>
    125 #include <string>
    126 #include <cstring>
    127 #include <cassert>
    128 #include <iomanip>
    129 #include <algorithm>
    130 #include <set>
    131 #include <map>
    132 #include <ctime>
    133 #include <cmath>
    134 
    135 #define forn(i, n) for(int i=0;i<n;++i)
    136 #define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
    137 #define sz(v) int(v.size())
    138 #define all(v) v.begin(), v.end()
    139 #define pb push_back
    140 #define mp make_pair
    141 #define x first
    142 #define y1 ________y1
    143 #define y second
    144 #define ft first
    145 #define sc second
    146 #define pt pair<int, int>
    147 
    148 template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
    149 template<typename X> inline X sqr(const X& a) { return a * a; }
    150 
    151 typedef long long li;
    152 typedef long double ld;
    153 
    154 using namespace std;
    155 
    156 const int INF = 1000 * 1000 * 1000;
    157 const ld EPS = 1e-9;
    158 const ld PI = acos(-1.0);
    159 
    160 const int N = 200 * 1000 + 13;
    161 
    162 int n;
    163 int a[N];
    164 
    165 inline void read() {
    166     cin >> n;
    167     for (int i = 0; i < n; i++) {
    168         cin >> a[i];
    169     }   
    170 }
    171 
    172 inline void solve() {   
    173     int ans = INF;
    174     for (int i = 0; i < n - 1; i++) {
    175         int cur = 0;
    176         int x = a[i], y = a[i + 1];
    177         if (x < y) {
    178             swap(x, y);
    179         }
    180         int cnt = min(x - y, (x + 1) / 2);
    181         cur += cnt;
    182         x -= 2 * cnt;
    183         y -= cnt;
    184         if (x > 0 && y > 0) {
    185             cur += (x + y + 2) / 3;
    186         }
    187         ans = min(ans, cur);    
    188     }
    189 
    190     for (int i = 0; i < n - 2; i++) {
    191         int cur = 0;
    192         int x = a[i], y = a[i + 2];
    193         if (x < y) {
    194             swap(x, y);
    195         }
    196         int cnt = (x - y + 1) / 2;
    197         cur += cnt;
    198         cur += y;
    199         ans = min(ans, cur);
    200     }
    201     
    202     sort(a, a + n);
    203     ans = min(ans, (a[0] + 1) / 2 + (a[1] + 1) / 2);
    204     cout << ans << endl;
    205 }
    206 
    207 int main () {
    208 #ifdef fcspartakm
    209     freopen("input.txt", "r", stdin);
    210     //freopen("output.txt", "w", stdout);
    211 #endif
    212     srand(time(NULL));
    213     cerr << setprecision(10) << fixed;
    214     
    215     read();
    216     solve();
    217  
    218     //cerr << "TIME: " << clock() << endl;
    219 }
    220 ```
    221 
    222 [1674F - Desktop Rearrangement](/contest/1674/problem/F "Codeforces Round 786 (Div. 3)")
    223 
    224 Idea: [vovuh](/profile/vovuh "Master vovuh")
    225 
    226 **Tutorial**
    227 
    228 Tutorial is loading...
    229 
    230 **Solution (vovuh)**
    231 
    232 ```
    233 #include <bits/stdc++.h>
    234 
    235 using namespace std;
    236 
    237 static char buf[1010];
    238 
    239 int main() {
    240 #ifdef _DEBUG
    241     freopen("input.txt", "r", stdin);
    242 //  freopen("output.txt", "w", stdout);
    243 #endif
    244     
    245     int n, m, q;
    246     scanf("%d %d %d", &n, &m, &q);
    247     vector<string> tmp(n);
    248     string s;
    249     int sum = 0;
    250     for (int i = 0; i < n; ++i) {
    251         scanf("%s", buf);
    252         tmp[i] = buf;
    253         sum += count(tmp[i].begin(), tmp[i].end(), '*');
    254     }
    255     
    256     for (int j = 0; j < m; ++j) {
    257         for (int i = 0; i < n; ++i) {
    258             s += tmp[i][j];
    259         }
    260     }
    261     int res = count(s.begin(), s.begin() + sum, '.');
    262     int pos = sum;
    263     for (int i = 0; i < q; ++i) {
    264         int x, y;
    265         scanf("%d %d", &x, &y);
    266         --x, --y;
    267         int p = y * n + x;
    268         if (p < pos) {
    269             if (s[p] == '.') {
    270                 --res;
    271             } else {
    272                 ++res;
    273             }
    274         }
    275         s[p] = (s[p] == '.' ? '*' : '.');
    276         if (s[p] == '*') {
    277             if (s[pos] == '.') {
    278                 ++res;
    279             }
    280             ++pos;
    281         } else {
    282             if (s[pos - 1] == '.') {
    283                 --res;
    284             }
    285             --pos;
    286         }
    287         printf("%d\n", res);
    288     }
    289     
    290     return 0;
    291 }
    292 ```
    293 
    294 [1674G - Remove Directed Edges](/contest/1674/problem/G "Codeforces Round 786 (Div. 3)")
    295 
    296 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    297 
    298 **Tutorial**
    299 
    300 Tutorial is loading...
    301 
    302 **Solution (awoo)**
    303 
    304 ```
    305 #include <bits/stdc++.h>
    306  
    307 #define forn(i, n) for (int i = 0; i < int(n); i++)
    308  
    309 using namespace std;
    310  
    311 const int INF = 1e9;
    312  
    313 vector<int> in, out;
    314 vector<vector<int>> g;
    315 vector<int> dp;
    316  
    317 int calc(int v){
    318     if (dp[v] != -1) return dp[v];
    319     if (in[v] >= 2 && out[v] >= 2){
    320         dp[v] = 1;
    321         for (int u : g[v])
    322             dp[v] = max(dp[v], calc(u) + 1);
    323     }
    324     else if (in[v] >= 2){
    325         dp[v] = 1;
    326     }
    327     else{
    328         dp[v] = -INF;
    329     }
    330     return dp[v];
    331 }
    332  
    333 int main() {
    334     int n, m;
    335     scanf("%d%d", &n, &m);
    336     g.resize(n);
    337     in.resize(n);
    338     out.resize(n);
    339     forn(i, m){
    340         int v, u;
    341         scanf("%d%d", &v, &u);
    342         --v, --u;
    343         g[v].push_back(u);
    344         ++in[u];
    345         ++out[v];
    346     }
    347     int ans = 1;
    348     dp.resize(n, -1);
    349     forn(v, n) if (out[v] >= 2){
    350         for (int u : g[v]){
    351             ans = max(ans, calc(u) + 1);
    352         }
    353     }
    354     printf("%d\n", ans);
    355     return 0;
    356 }
    357 ```