codeforces-scrape

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

2104.md (8736B)


      1 Source: https://codeforces.com/blog/entry/142472
      2 
      3 [2104A - Three Decks](/contest/2104/problem/A "Educational Codeforces Round 178 (Rated for Div. 2)")
      4 
      5 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (awoo)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15     a, b, c = map(int, input().split())
     16     if (a + b + c) % 3 != 0:
     17         print("NO")
     18         continue
     19     x = (a + b + c) // 3
     20     print("YES" if b <= x else "NO")
     21 ```
     22 
     23 [2104B - Move to the End](/contest/2104/problem/B "Educational Codeforces Round 178 (Rated for Div. 2)")
     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     int t;
     41     cin >> t;
     42     for(int i = 0; i < t; i++)
     43     {
     44         int n;
     45         cin >> n;
     46         vector<int> a(n);
     47         for(int j = 0; j < n; j++) cin >> a[j];
     48         vector<int> pmax(n + 1);
     49         vector<long long> psum(n + 1);
     50         for(int j = 0; j < n; j++)
     51         {
     52             pmax[j + 1] = max(pmax[j], a[j]);
     53             psum[j + 1] = psum[j] + a[j];
     54         }
     55         for(int k = 1; k <= n; k++)
     56             cout << pmax[n - k + 1] + psum[n] - psum[n - k + 1] << " ";
     57         cout << endl;
     58     }
     59 }
     60 ```
     61 
     62 [2104C - Card Game](/contest/2104/problem/C "Educational Codeforces Round 178 (Rated for Div. 2)")
     63 
     64 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     65 
     66 **Tutorial**
     67 
     68 Tutorial is loading...
     69 
     70 **Solution (BledDest)**
     71 
     72 ```
     73 def beats(n, x, y):
     74     if x == 0:
     75         return y == n - 1
     76     if x == n - 1:
     77         return y != 0
     78     return x > y
     79  
     80 for _ in range(int(input())):
     81     n = int(input())
     82     owner = input()
     83     good = False
     84     for i in range(n):
     85         if owner[i] != 'A':
     86             continue
     87         good_move = True
     88         for j in range(n):
     89             if owner[j] == 'B' and beats(n, j, i):
     90                 good_move = False
     91         if good_move:
     92             good = True
     93     if good:
     94         print('Alice')
     95     else:
     96         print('Bob')
     97 ```
     98 
     99 [2104D - Array and GCD](/contest/2104/problem/D "Educational Codeforces Round 178 (Rated for Div. 2)")
    100 
    101 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    102 
    103 **Tutorial**
    104 
    105 Tutorial is loading...
    106 
    107 **Solution (Neon)**
    108 
    109 ```
    110 #include <bits/stdc++.h>
    111  
    112 using namespace std;
    113  
    114 const int N = 6e6;
    115  
    116 int main() {
    117   ios::sync_with_stdio(false); cin.tie(0);
    118   vector<int> p, ip(N, 1);
    119   for (int i = 2; i < N; ++i) {
    120     if (!ip[i]) continue;
    121     p.push_back(i);
    122     for (int j = i; j < N; j += i) {
    123       ip[j] = 0;
    124     }
    125   }
    126   int t;
    127   cin >> t;
    128   while (t--) {
    129     int n;
    130     cin >> n;
    131     vector<int> a(n);
    132     for (auto& x : a) cin >> x;
    133     sort(a.begin(), a.end(), greater<int>());
    134     int ans = 0;
    135     long long suma = 0, sump = 0;
    136     for (int i = 0; i < n; ++i) {
    137       suma += a[i];
    138       sump += p[i];
    139       if (suma >= sump) ans = i + 1;
    140     }
    141     cout << n - ans << endl;
    142   }
    143 }
    144 ```
    145 
    146 [2104E - Unpleasant Strings](/contest/2104/problem/E "Educational Codeforces Round 178 (Rated for Div. 2)")
    147 
    148 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    149 
    150 **Tutorial**
    151 
    152 Tutorial is loading...
    153 
    154 **Solution (adedalic)**
    155 
    156 ```
    157 #include<bits/stdc++.h>
    158  
    159 using namespace std;
    160  
    161 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    162 #define sz(a) int((a).size())
    163  
    164 #define x first
    165 #define y second
    166  
    167 typedef long long li;
    168 typedef long double ld;
    169 typedef pair<int, int> pt;
    170  
    171 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    172     return out << "(" << p.x << ", " << p.y << ")";
    173 }
    174 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    175     fore(i, 0, sz(v)) {
    176         if(i) out << " ";
    177         out << v[i];
    178     }
    179     return out;
    180 }
    181  
    182 const int INF = int(1e9);
    183 const li INF64 = li(1e18);
    184 const ld EPS = 1e-9;
    185  
    186 int n, k;
    187 string s;
    188  
    189 inline bool read() {
    190     if(!(cin >> n >> k))
    191         return false;
    192     cin >> s;
    193     return true;
    194 }
    195  
    196 inline void solve() {
    197     vector<int> d(n + 1, 0);
    198     vector<vector<int>> nxt(n + 2, vector<int>(k, n));
    199     for (int i = n - 1; i >= 0; i--) {
    200         nxt[i] = nxt[i + 1];
    201         int mx = *max_element(nxt[i].begin(), nxt[i].end());
    202         d[i] = 1 + d[mx];
    203         nxt[i][s[i] - 'a'] = i;
    204     }
    205  
    206     int q; cin >> q;
    207     while (q--) {
    208         string t; cin >> t;
    209         int pos = -1;
    210         for (char c : t)
    211             pos = nxt[pos + 1][c - 'a'];
    212         cout << d[pos] << "\n";
    213     }
    214 }
    215  
    216 int main() {
    217 #ifdef _DEBUG
    218     freopen("input.txt", "r", stdin);
    219     int tt = clock();
    220 #endif
    221     ios_base::sync_with_stdio(false);
    222     cin.tie(0), cout.tie(0);
    223     cout << fixed << setprecision(15);
    224     
    225     if(read()) {
    226         solve();
    227         
    228 #ifdef _DEBUG
    229         cerr << "TIME = " << clock() - tt << endl;
    230         tt = clock();
    231 #endif
    232     }
    233     return 0;
    234 }
    235 ```
    236 
    237 [2104F - Numbers and Strings](/contest/2104/problem/F "Educational Codeforces Round 178 (Rated for Div. 2)")
    238 
    239 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    240 
    241 **Tutorial**
    242 
    243 Tutorial is loading...
    244 
    245 **Solution (BledDest)**
    246 
    247 ```
    248 #include<bits/stdc++.h>
    249  
    250 using namespace std;
    251  
    252 const long long A = (long long)(1e18);
    253  
    254 string S(long long x)
    255 {
    256     string s = to_string(x) + to_string(x + 1);
    257     sort(s.begin(), s.end());
    258     return s;
    259 }
    260  
    261 vector<long long> aux2;
    262 vector<pair<string, long long>> aux;
    263  
    264 long long get_num(string cur)
    265 {
    266     int first_non_zero = 0;
    267     while(cur[first_non_zero] == '0') first_non_zero++;
    268     swap(cur[first_non_zero], cur[0]);
    269     return stoll(cur);
    270 }
    271  
    272 void rec(string cur, bool flag)
    273 {
    274     if(*max_element(cur.begin(), cur.end()) > '0')
    275     {
    276         long long x = get_num(cur);
    277         aux.push_back(make_pair(S(x), x));
    278     }
    279     if(cur.size() < 9)
    280     {
    281         if(flag)
    282             rec(cur + "9", true);
    283         else
    284             for(char c = '0'; c <= '9'; c++)
    285                 rec(cur + string(1, c), c < cur.back());    
    286     }
    287 }   
    288  
    289 void precalc()
    290 {
    291     for(char c = '0'; c <= '9'; c++)
    292         rec(string(1, c), false);
    293     sort(aux.begin(), aux.end());
    294     for(int i = 0; i < aux.size(); i++)
    295         if(i == 0 || aux[i].first != aux[i - 1].first)
    296             aux2.push_back(aux[i].second);
    297     sort(aux2.begin(), aux2.end());
    298 }
    299  
    300 int main()
    301 {
    302     ios_base::sync_with_stdio(0);
    303     cin.tie(0);
    304     int t;
    305     cin >> t;
    306     precalc();
    307     for(int i = 0; i < t; i++)
    308     {
    309         long long n;
    310         cin >> n;
    311         cout << upper_bound(aux2.begin(), aux2.end(), n) - aux2.begin() << endl;              
    312     }
    313 }
    314 ```
    315 
    316 [2104G - Modulo 3](/contest/2104/problem/G "Educational Codeforces Round 178 (Rated for Div. 2)")
    317 
    318 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    319 
    320 **Tutorial**
    321 
    322 Tutorial is loading...
    323 
    324 **Solution (Neon)**
    325 
    326 ```
    327 #include <bits/stdc++.h>
    328  
    329 using namespace std;
    330  
    331 using pt = pair<int, int>;
    332  
    333 const int N = 200007;
    334  
    335 int n, q;
    336 int k[N];
    337 vector<pt> t[4 * N];
    338 int p[N], e[N], rk[N];
    339 int *pos[3 * N];
    340 int val[3 * N];
    341 int csz;
    342 int ans[N];
    343  
    344 void upd(int v, int l, int r, int L, int R, pt val) {
    345   if (L >= R) return;
    346   if (l == L && r == R) {
    347     t[v].push_back(val);
    348     return;
    349   }
    350   int m = (l + r) / 2;
    351   upd(v * 2 + 1, l, m, L, min(R, m), val);
    352   upd(v * 2 + 2, m, r, max(m, L), R, val);
    353 }
    354  
    355 void rollback(int tsz) {
    356   while (csz > tsz) {
    357     --csz;
    358     (*pos[csz]) = val[csz];
    359   }
    360 }
    361  
    362 pt get(int v) {
    363   if (p[v] == v) return {v, 0};
    364   auto [u, d] = get(p[v]);
    365   return {u, d ^ e[v]};
    366 }
    367  
    368 void assign(int& x, int y) {
    369   pos[csz] = &x;
    370   val[csz] = x;
    371   ++csz;
    372   x = y;
    373 }
    374  
    375 pt unite(int x, int y) {
    376   auto [v, d1] = get(x);
    377   auto [u, d2] = get(y);
    378   if (v == u) return {0, d1 ^ d2};
    379   if (rk[v] > rk[u]) swap(v, u);
    380   assign(p[v], u);
    381   assign(e[v], d1 ^ d2 ^ 1);
    382   assign(rk[u], rk[v] + rk[u]);
    383   return {1, 0};
    384 }
    385  
    386 void solve(int v, int l, int r, int cnt) {
    387   int tsz = csz;
    388   for (auto [x, y] : t[v]) {
    389     auto [f, d] = unite(x, y);
    390     //cerr << l << " " << r << " " << x + 1 << " " << y + 1 << " " << f << " " << d << endl;
    391     if (!f) cnt ^= d;
    392   }
    393   if (l != r - 1) {
    394     int m = (l + r) / 2;
    395     solve(v * 2 + 1, l, m, cnt);
    396     solve(v * 2 + 2, m, r, cnt);
    397   } else {
    398     ans[l] = k[l] % 3;
    399     if (ans[l] == 2) ans[l] = cnt + 1;
    400   }
    401   rollback(tsz);
    402 }
    403  
    404 int main() {
    405   cin >> n >> q;
    406   vector<int> g(n), lst(n);
    407   for (int i = 0; i < n; ++i) {
    408     cin >> g[i];
    409     --g[i];
    410   }
    411   for (int i = 0; i < q; ++i) {
    412     int x, y;
    413     cin >> x >> y >> k[i];
    414     --x; --y;
    415     upd(0, 0, q, lst[x], i, {x, g[x]});
    416     g[x] = y;
    417     lst[x] = i;
    418   }
    419   for (int i = 0; i < n; ++i) {
    420     upd(0, 0, q, lst[i], q, {i, g[i]});
    421     p[i] = i;
    422     rk[i] = 1;
    423   }
    424   solve(0, 0, q, n & 1);
    425   for (int i = 0; i < q; ++i) {
    426     cout << ans[i] << '\n';
    427   }
    428 }
    429 ```