codeforces-scrape

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

1749.md (9697B)


      1 Source: https://codeforces.com/blog/entry/108269
      2 
      3 [1749A - Cowardly Rooks](/contest/1749/problem/A "Educational Codeforces Round 138 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution 1 (awoo)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15     n, m = map(int, input().split())
     16     for _ in range(m):
     17         input()
     18     print("NO" if n == m else "YES")
     19 ```
     20 
     21 **Solution 2 (awoo)**
     22 
     23 ```
     24 #include <bits/stdc++.h>
     25 
     26 #define forn(i, n) for (int i = 0; i < int(n); i++)
     27 
     28 using namespace std;
     29 
     30 int main() {
     31     int t;
     32     scanf("%d", &t);
     33     forn(_, t){
     34         int n, m;
     35         scanf("%d%d", &n, &m);
     36         vector<pair<int, int>> a(m);
     37         forn(i, m){
     38             scanf("%d%d", &a[i].first, &a[i].second);
     39             --a[i].first, --a[i].second;
     40         }
     41         bool ans = false;
     42         forn(i, m) forn(x, n) forn(y, n) if ((x == a[i].first) ^ (y == a[i].second)){
     43             bool ok = true;
     44             forn(j, m) if (i != j){
     45                 ok &= x != a[j].first && y != a[j].second;
     46             }
     47             ans |= ok;
     48         }
     49         puts(ans ? "YES" : "NO");
     50     }
     51 }
     52 ```
     53 
     54 [1749B - Death's Blessing](/contest/1749/problem/B "Educational Codeforces Round 138 (Rated for Div. 2)")
     55 
     56 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     57 
     58 **Tutorial**
     59 
     60 Tutorial is loading...
     61 
     62 **Solution (adedalic)**
     63 
     64 ```
     65 fun main() {
     66     repeat(readLine()!!.toInt()) {
     67         val n = readLine()!!.toInt()
     68         val a = readLine()!!.split(' ').map { it.toLong() }
     69         val b = readLine()!!.split(' ').map { it.toLong() }
     70 
     71         println(a.sum() + b.sum() - b.maxOrNull()!!)
     72     }
     73 }
     74 ```
     75 
     76 [1749C - Number Game](/contest/1749/problem/C "Educational Codeforces Round 138 (Rated for Div. 2)")
     77 
     78 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     79 
     80 **Tutorial**
     81 
     82 Tutorial is loading...
     83 
     84 **Solution (Neon)**
     85 
     86 ```
     87 #include <bits/stdc++.h>
     88 
     89 using namespace std;
     90 
     91 int main() {
     92   int t;
     93   cin >> t;
     94   while (t--) {
     95     int n;
     96     cin >> n;
     97     vector<int> a(n);
     98     for (int &x : a) cin >> x;
     99     int ans = 0;
    100     for (int k = 1; k <= n; ++k) {
    101       multiset<int> s(a.begin(), a.end());
    102       for (int i = 0; i < k; ++i) {
    103         auto it = s.upper_bound(k - i);
    104         if (it == s.begin()) break;
    105         s.erase(--it);
    106         if (!s.empty()) {
    107           int x = *s.begin();
    108           s.erase(s.begin());
    109           s.insert(x + k - i);
    110         }
    111       }
    112       if (s.size() + k == n) ans = k;
    113     }
    114     cout << ans << '\n';
    115   }
    116 }
    117 ```
    118 
    119 [1749D - Counting Arrays](/contest/1749/problem/D "Educational Codeforces Round 138 (Rated for Div. 2)")
    120 
    121 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    122 
    123 **Tutorial**
    124 
    125 Tutorial is loading...
    126 
    127 **Solution (BledDest)**
    128 
    129 ```
    130 #include <bits/stdc++.h>
    131  
    132 using namespace std;
    133 
    134 const int MOD = 998244353;
    135 
    136 int add(int x, int y)
    137 {
    138     x += y;
    139     while(x >= MOD) x -= MOD;
    140     while(x < 0) x += MOD;
    141     return x;
    142 }   
    143 
    144 int sub(int x, int y)
    145 {
    146     return add(x, -y);
    147 }   
    148 
    149 int mul(int x, int y)
    150 {
    151     return (x * 1ll * y) % MOD;
    152 }
    153 
    154 int binpow(int x, int y)
    155 {
    156     int z = 1;
    157     while(y)
    158     {
    159         if(y & 1) z = mul(z, x);
    160         x = mul(x, x);
    161         y >>= 1;
    162     }
    163     return z;
    164 }
    165 
    166 bool prime(int x)
    167 {
    168     for(int i = 2; i * 1ll * i <= x; i++)
    169         if(x % i == 0)
    170             return false;
    171     return true;    
    172 }
    173 
    174 int main()
    175 {
    176     int n;
    177     long long m;
    178     cin >> n >> m;
    179     int ans = 0;
    180     for(int i = 1; i <= n; i++)
    181         ans = add(ans, binpow(m % MOD, i));
    182     long long cur = 1;
    183     int cnt = 1;
    184     for(int i = 1; i <= n; i++)
    185     {
    186         if(cur > m) continue;
    187         if(prime(i)) cur *= i;
    188         cnt = mul(cnt, (m / cur) % MOD);
    189         ans = sub(ans, cnt);
    190     }
    191     cout << ans << endl;
    192 }
    193 ```
    194 
    195 [1749E - Cactus Wall](/contest/1749/problem/E "Educational Codeforces Round 138 (Rated for Div. 2)")
    196 
    197 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    198 
    199 **Tutorial**
    200 
    201 Tutorial is loading...
    202 
    203 **Solution (Neon)**
    204 
    205 ```
    206 #include <bits/stdc++.h>
    207 
    208 using namespace std;
    209 
    210 const int INF = 1e9;
    211 
    212 int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
    213 int dy[] = {1, 0, -1, 0, -1, 1, -1, 1};
    214 
    215 int main() {
    216   ios::sync_with_stdio(false); cin.tie(0);
    217   int t;
    218   cin >> t;
    219   while (t--) {
    220     int n, m;
    221     cin >> n >> m;
    222     vector<string> s(n);
    223     for (auto &it : s) cin >> it;
    224     
    225     auto in = [&](int x, int y) {
    226       return 0 <= x && x < n && 0 <= y && y < m;
    227     };
    228     
    229     auto can = [&](int x, int y) {
    230       if (!in(x, y)) return false;
    231       for (int i = 0; i < 4; ++i) {
    232         int nx = x + dx[i], ny = y + dy[i];
    233         if (in(nx, ny) && s[nx][ny] == '#')
    234           return false;
    235       }
    236       return true;
    237     };
    238     
    239     vector<vector<int>> d(n, vector<int>(m, INF)), p(n, vector<int>(m));
    240     deque<pair<int, int>> q;
    241     for (int i = 0; i < n; ++i) {
    242         if (s[i][0] == '#') {
    243           d[i][0] = 0;
    244           q.push_front({i, 0});
    245         } else if (can(i, 0)) {
    246           d[i][0] = 1;
    247           q.push_back({i, 0});
    248         }
    249     }
    250     
    251     while (!q.empty()) {
    252       auto [x, y] = q.front();
    253       q.pop_front();
    254       for (int i = 4; i < 8; ++i) {
    255         int nx = x + dx[i], ny = y + dy[i];
    256         if (!can(nx, ny)) continue;
    257         int w = (s[nx][ny] != '#');
    258         if (d[nx][ny] > d[x][y] + w) {
    259           d[nx][ny] = d[x][y] + w;
    260           p[nx][ny] = i;
    261           if (w) q.push_back({nx, ny});
    262           else q.push_front({nx, ny});
    263         }
    264       }
    265     }
    266     
    267     int x = 0, y = m - 1;
    268     for (int i = 0; i < n; ++i) if (d[x][y] > d[i][y])
    269       x = i;
    270     if (d[x][y] == INF) {
    271       cout << "NO\n";
    272       continue;
    273     }
    274     while (true) {
    275       s[x][y] = '#';
    276       int i = p[x][y];
    277       if (!i) break;
    278       x -= dx[i];
    279       y -= dy[i];
    280     }
    281     cout << "YES\n";
    282     for (auto it : s) cout << it << '\n';
    283   }
    284 }
    285 ```
    286 
    287 [1749F - Distance to the Path](/contest/1749/problem/F "Educational Codeforces Round 138 (Rated for Div. 2)")
    288 
    289 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") и [adedalic](/profile/adedalic "International Master adedalic")
    290 
    291 **Tutorial**
    292 
    293 Tutorial is loading...
    294 
    295 **Solution (adedalic)**
    296 
    297 ```
    298 #include<bits/stdc++.h>
    299 
    300 using namespace std;
    301 
    302 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    303 #define sz(a) int((a).size())
    304 
    305 typedef long long li;
    306 typedef pair<int, int> pt;
    307 
    308 const int INF = int(1e9);
    309 const li INF64 = li(1e18);
    310 
    311 const int N = int(2e5) + 55;
    312 const int LOG = 18;
    313 
    314 int n;
    315 vector<int> g[N];
    316 
    317 inline bool read() {
    318     if(!(cin >> n))
    319         return false;
    320     fore (i, 0, n - 1) {
    321         int u, v;
    322         cin >> u >> v;
    323         u--, v--;
    324         
    325         g[u].push_back(v);
    326         g[v].push_back(u);
    327     }
    328     return true;
    329 }
    330 
    331 int p[LOG][N];
    332 int tin[N], tout[N], T = 0;
    333 
    334 void build(int v, int pr) {
    335     tin[v] = T++;
    336     p[0][v] = pr;
    337     fore (pw, 1, LOG)
    338         p[pw][v] = p[pw - 1][p[pw - 1][v]];
    339     
    340     for (int to : g[v]) {
    341         if (to == pr)
    342             continue;
    343         build(to, v);
    344     }
    345     tout[v] = T;
    346 }
    347 
    348 bool inside(int l, int v) {
    349     return tin[l] <= tin[v] && tout[v] <= tout[l];
    350 }
    351 
    352 int lca(int u, int v) {
    353     if (inside(u, v))
    354         return u;
    355     if (inside(v, u))
    356         return v;
    357     
    358     for (int pw = LOG - 1; pw >= 0; pw--) {
    359         if (!inside(p[pw][u], v))
    360             u = p[pw][u];
    361     }
    362     return p[0][u];
    363 }
    364 
    365 const int D = 21;
    366 struct Fenwick {
    367     int n;
    368     vector<int> F;
    369     void init(int nn) {
    370         n = nn;
    371         F.assign(n, 0);
    372     }
    373     
    374     void add(int pos, int val) {
    375         for (; pos < n; pos |= pos + 1)
    376             F[pos] += val;
    377     }
    378     int sum(int pos) {
    379         int ans = 0;
    380         for (; pos >= 0; pos = (pos & (pos + 1)) - 1)
    381             ans += F[pos];
    382         return ans;
    383     }
    384     int getSum(int l, int r) {
    385         return sum(r - 1) - sum(l - 1);
    386     }
    387 };
    388 
    389 struct DS {
    390     Fenwick f;
    391     void init(int n) {
    392         f.init(n);
    393     }
    394     
    395     void addPath(int v, int l, int k) {
    396         f.add(tin[v], +k);
    397         f.add(tin[l], -k);
    398     }
    399     int getVertex(int v) {
    400         return f.getSum(tin[v], tout[v]);
    401     }
    402     
    403     void addVertex(int v, int k) {
    404         f.add(tin[v], +k);
    405         if (p[0][v] != v)
    406             f.add(tin[p[0][v]], -k);
    407     }
    408 };
    409 
    410 DS t[D];
    411 
    412 inline void solve() {
    413     fore (i, 0, D) {
    414         g[n - 1 + i].push_back(n + i);
    415         g[n + i].push_back(n - 1 + i);
    416     }
    417     int root = n + D - 1;
    418     
    419     build(root, root);
    420     fore (i, 0, D)
    421         t[i].init(root + 1);
    422     
    423     int m; cin >> m;
    424     fore(_, 0, m) {
    425         int tp; cin >> tp;
    426         if (tp == 1) {
    427             int v; cin >> v;
    428             v--;
    429             
    430             int ans = 0;
    431             for (int i = 0, cur = v; i < D; i++, cur = p[0][cur])
    432                 ans += t[i].getVertex(cur);
    433             cout << ans << endl;
    434         } 
    435         else {
    436             assert(tp == 2);
    437 
    438             int u, v, k, d;
    439             cin >> u >> v >> k >> d;
    440             u--, v--;
    441             
    442             int l = lca(u, v);
    443             
    444             if (u != l)
    445                 t[d].addPath(u, l, k);
    446             if (v != l)
    447                 t[d].addPath(v, l, k);
    448             
    449             for (int i = 0; i <= d; i++, l = p[0][l]) {
    450                 t[d - i].addVertex(l, k);
    451                 if (d - i > 0)
    452                     t[d - i - 1].addVertex(l, k);
    453             }
    454         }
    455     }
    456 }
    457 
    458 int main() {
    459 #ifdef _DEBUG
    460     freopen("input.txt", "r", stdin);
    461     int tt = clock();
    462 #endif
    463     ios_base::sync_with_stdio(false);
    464     cin.tie(0), cout.tie(0);
    465     cout << fixed << setprecision(15);
    466     
    467     if(read()) {
    468         solve();
    469         
    470 #ifdef _DEBUG
    471         cerr << "TIME = " << clock() - tt << endl;
    472         tt = clock();
    473 #endif
    474     }
    475     return 0;
    476 }
    477 ```