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 ```