codeforces-scrape

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

1547.md (8615B)


      1 Source: https://codeforces.com/blog/entry/92715
      2 
      3 [1547A - Shortest Path with Obstacle](/contest/1547/problem/A "Codeforces Round 731 (Div. 3)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 #define forn(i, n) for (int i = 0; i < int(n); i++)
     19 
     20 int main() {
     21     int t;
     22     cin >> t;
     23     forn(tt, t) {
     24         vector<int> a(2), b(2), f(2);
     25         cin >> a[0] >> a[1];
     26         cin >> b[0] >> b[1];
     27         cin >> f[0] >> f[1];
     28         int ans = abs(a[0] - b[0]) + abs(a[1] - b[1]);
     29         if ((a[0] == b[0] && a[0] == f[0] && min(a[1], b[1]) < f[1] && f[1] < max(a[1], b[1]))
     30                 || (a[1] == b[1] && a[1] == f[1] && min(a[0], b[0]) < f[0] && f[0] < max(a[0], b[0])))
     31             ans += 2;
     32         cout << ans << endl;
     33     }
     34 }
     35 ```
     36 
     37 [1547B - Alphabetical Strings](/contest/1547/problem/B "Codeforces Round 731 (Div. 3)")
     38 
     39 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     40 
     41 **Tutorial**
     42 
     43 Tutorial is loading...
     44 
     45 **Solution**
     46 
     47 ```
     48 #include <bits/stdc++.h>
     49 
     50 using namespace std;
     51 
     52 #define forn(i, n) for (int i = 0; i < int(n); i++)
     53 
     54 int main() {
     55     int t;
     56     cin >> t;
     57     forn(tt, t) {
     58         string s;
     59         cin >> s;
     60         size_t L = s.find('a');
     61         if (L == string::npos) {
     62             cout << "NO" << endl;
     63             continue;
     64         }
     65         size_t n = s.length(), R = L;
     66         bool yes = true;
     67         for (size_t i = 1; i < n; i++) {
     68             size_t pos = s.find(char('a' + i));
     69             if (pos == string::npos || (pos != L - 1 && pos != R + 1)) {
     70                 yes = false;
     71                 break;
     72             } else {
     73                 L = min(L, pos);
     74                 R = max(R, pos);
     75             }
     76         }
     77         cout << (yes ? "YES" : "NO") << endl;
     78     }
     79 }
     80 ```
     81 
     82 [1547C - Pair Programming](/contest/1547/problem/C "Codeforces Round 731 (Div. 3)")
     83 
     84 Idea: [geranazavr555](/profile/geranazavr555 "Headquarters, geranazavr555"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     85 
     86 **Tutorial**
     87 
     88 Tutorial is loading...
     89 
     90 **Solution**
     91 
     92 ```
     93 #include <iostream>
     94 #include <vector>
     95 
     96 typedef std::vector<int> vi;
     97 
     98 int main() {
     99     int t;
    100     std::cin >> t;
    101     while (t--) {
    102         int k, n, m;
    103         std::cin >> k >> n >> m;
    104 
    105         vi a(n), b(m);
    106         for (int i = 0; i < n; i++)
    107             std::cin >> a[i];
    108         for (int i = 0; i < m; i++)
    109             std::cin >> b[i];
    110 
    111         int pos1 = 0, pos2 = 0;
    112         vi res;
    113         bool ok = true;
    114         while (pos1 != n || pos2 != m) {
    115             if (pos1 != n && a[pos1] == 0) {
    116                 res.push_back(0);
    117                 k++;
    118                 pos1++;
    119             } else if (pos2 != m && b[pos2] == 0) {
    120                 res.push_back(0);
    121                 k++;
    122                 pos2++;
    123             } else if (pos1 != n && a[pos1] <= k) {
    124                 res.push_back(a[pos1++]);
    125             } else if (pos2 != m && b[pos2] <= k) {
    126                 res.push_back(b[pos2++]);
    127             } else {
    128                 std::cout << -1 << '\n';
    129                 ok = false;
    130                 break;
    131             }
    132         }
    133 
    134         if (ok) {
    135             for (int cur : res)
    136                 std::cout << cur << ' ';
    137             std::cout << std::endl;
    138         }
    139     }
    140 
    141     return 0;
    142 }
    143 ```
    144 
    145 [1547D - Co-growing Sequence](/contest/1547/problem/D "Codeforces Round 731 (Div. 3)")
    146 
    147 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov")
    148 
    149 **Tutorial**
    150 
    151 Tutorial is loading...
    152 
    153 **Solution**
    154 
    155 ```
    156 def f(x, y):
    157     return x & ~y
    158 
    159 t = int(input())
    160 for tt in range(t):
    161     n = int(input())
    162     a = list(map(int, input().split()))
    163 
    164     ans = [0] * n
    165     for i in range(1, n):
    166         ans[i] = f(ans[i - 1] ^ a[i - 1], a[i])
    167     print(" ".join(map(str, ans)))
    168 ```
    169 
    170 [1547E - Air Conditioners](/contest/1547/problem/E "Codeforces Round 731 (Div. 3)")
    171 
    172 Idea: [geranazavr555](/profile/geranazavr555 "Headquarters, geranazavr555"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    173 
    174 **Tutorial**
    175 
    176 Tutorial is loading...
    177 
    178 **Solution**
    179 
    180 ```
    181 #include <bits/stdc++.h>
    182 
    183 using namespace std;
    184 
    185 #define forn(i, n) for (int i = 0; i < int(n); i++)
    186 
    187 int main() {
    188     int t;
    189     cin >> t;
    190     forn(tt, t) {
    191         int n, k;
    192         cin >> n >> k;
    193         vector<int> a(k);
    194         forn(i, k)
    195             cin >> a[i];
    196         vector<int> t(k);
    197         forn(i, k)
    198             cin >> t[i];
    199         vector<long long> c(n, INT_MAX);
    200         forn(i, k)
    201             c[a[i] - 1] = t[i];
    202 
    203         long long p;
    204 
    205         vector<long long> L(n, INT_MAX);
    206         p = INT_MAX;
    207         forn(i, n) {
    208             p = min(p + 1, c[i]);
    209             L[i] = p;
    210         }
    211 
    212         vector<long long> R(n, INT_MAX);
    213         p = INT_MAX;
    214         for (int i = n - 1; i >= 0; i--) {
    215             p = min(p + 1, c[i]);
    216             R[i] = p;
    217         }
    218 
    219         forn(i, n)  
    220             cout << min(L[i], R[i]) << " ";
    221         cout << endl;
    222     }
    223 }
    224 ```
    225 
    226 [1547F - Array Stabilization (GCD version)](/contest/1547/problem/F "Codeforces Round 731 (Div. 3)")
    227 
    228 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov")
    229 
    230 **Tutorial**
    231 
    232 Tutorial is loading...
    233 
    234 **Solution**
    235 
    236 ```
    237 #include <iostream>
    238 #include <vector>
    239 #include <set>
    240 
    241 using namespace std;
    242 
    243 const unsigned int MAX_A = 1'000'000;
    244 vector<unsigned int> sieve(MAX_A + 1);
    245 vector<unsigned int> prime;
    246 
    247 unsigned int gcd(unsigned int a, unsigned int b) {
    248     return b == 0 ? a : gcd(b, a % b);
    249 }
    250 
    251 unsigned int solve() {
    252 
    253     unsigned int n;
    254     cin >> n;
    255     vector<unsigned int> a(n);
    256     for (unsigned int i = 0; i < n; i++) {
    257         cin >> a[i];
    258     }
    259 
    260     unsigned int common = a[0];
    261     vector<set<unsigned int>> facts(n);
    262     for (unsigned int i = 1; i < n; i++) {
    263         common = gcd(common, a[i]);
    264     }
    265     for (unsigned int i = 0; i < n; i++) {
    266         unsigned int t = a[i] / common;
    267         while (t != 1) {
    268             facts[i].insert(sieve[t]);
    269             t /= sieve[t];
    270         }
    271     }
    272 
    273     unsigned int answer = 0;
    274     for (unsigned int i = 0; i < n; i++) {
    275         for (unsigned int p : facts[i]) {
    276             int l = (i + n - 1) % n, r = i;
    277             unsigned int cnt = 0;
    278             while (facts[l].count(p) > 0) {
    279                 facts[l].erase(p);
    280                 l--; cnt++;
    281                 if (l < 0) {
    282                     l = n - 1;
    283                 }
    284             }
    285             while (facts[r].count(p) > 0) {
    286                 if (r != i) {
    287                     facts[r].erase(p);
    288                 }
    289                 ++r %= n; cnt++;
    290             }
    291             answer = max(answer, cnt);
    292         }
    293         facts[i].clear();
    294     }
    295 
    296     return answer;
    297 
    298 }
    299 
    300 int main() {
    301 
    302     sieve[1] = 1;
    303     for (unsigned int i = 2; i <= MAX_A; i++) {
    304         if (sieve[i] == 0) {
    305             sieve[i] = i;
    306             prime.push_back(i);
    307         }
    308         for (unsigned int j = 0; j < prime.size() && prime[j] <= sieve[i] && i * prime[j] <= MAX_A; j++) {
    309             sieve[i * prime[j]] = prime[j];
    310         }
    311     }
    312 
    313     unsigned int t;
    314     cin >> t;
    315     for (unsigned int i = 0; i < t; i++) {
    316         cout << solve() << '\n';
    317     }
    318 
    319 }
    320 ```
    321 
    322 [1547G - How Many Paths?](/contest/1547/problem/G "Codeforces Round 731 (Div. 3)")
    323 
    324 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    325 
    326 **Tutorial**
    327 
    328 Tutorial is loading...
    329 
    330 **Solution**
    331 
    332 ```
    333 #include <bits/stdc++.h>
    334 
    335 using namespace std;
    336 
    337 #define forn(i, n) for (int i = 0; i < int(n); i++)
    338 
    339 int n;
    340 vector<vector<int>> g;
    341 set<int> s[2];
    342 
    343 void dfs(int u, vector<int>& color, bool use_s) {
    344     color[u] = 1;
    345     for (int v: g[u])
    346         if (color[v] == 0)
    347             dfs(v, color, use_s);
    348         else if (use_s)
    349             s[color[v] - 1].insert(v);
    350     color[u] = 2;
    351 }
    352 
    353 int main() {
    354     int t;
    355     cin >> t;
    356     forn(tt, t) {
    357         int m;
    358         cin >> n >> m;
    359         g = vector<vector<int>>(n);
    360         forn(i, 2)
    361             s[i] = set<int>();
    362         forn(i, m) {
    363             int x, y;
    364             cin >> x >> y;
    365             x--, y--;
    366             g[x].push_back(y);
    367         }
    368         vector<int> color = vector<int>(n);
    369         dfs(0, color, true);
    370         vector<vector<int>> c(2, vector<int>(n));
    371         forn(i, 2)
    372             for (auto u: s[i])
    373                 dfs(u, c[i], false);
    374         forn(i, n) {
    375             int ans = 0;
    376             if (color[i] != 0) {
    377                 ans = 1;
    378                 if (c[0][i])
    379                     ans = -1;
    380                 else if (c[1][i])
    381                     ans = 2;
    382             }
    383             cout << ans << " ";
    384         }
    385         cout << endl;
    386     }
    387 }
    388 ```