1221.md (9543B)
1 Source: https://codeforces.com/blog/entry/69925 2 3 [1221A - 2048 Game](/contest/1221/problem/A "Educational Codeforces Round 73 (Rated for Div. 2)") 4 5 Idea: [Roms](/profile/Roms "Master Roms") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Roms)** 12 13 ``` 14 for t in range(int(input())): 15 n = input() 16 l = filter(lambda x : x <= 2048, map(int, input().split()) ) 17 print('YES' if sum(l) >= 2048 else 'NO') 18 ``` 19 20 [1221B - Knights](/contest/1221/problem/B "Educational Codeforces Round 73 (Rated for Div. 2)") 21 22 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 23 24 **Tutorial** 25 26 Tutorial is loading... 27 28 **Solution (PikMike)** 29 30 ``` 31 n = int(input()) 32 for i in range(n): 33 print(''.join(['W' if (i + j) % 2 == 0 else 'B' for j in range(n)])) 34 ``` 35 36 [1221C - Perfect Team](/contest/1221/problem/C "Educational Codeforces Round 73 (Rated for Div. 2)") 37 38 Idea: [Roms](/profile/Roms "Master Roms") 39 40 **Tutorial** 41 42 Tutorial is loading... 43 44 **Solution 1 (BledDest)** 45 46 ``` 47 t = int(input()) 48 for i in range(t): 49 c, m, x = map(int, input().split()) 50 d = max(c, m) - min(c, m) 51 x += d 52 if(c > m): 53 c -= d 54 else: 55 m -= d 56 ans = min(c, m, x) 57 c -= ans 58 m -= ans 59 x -= ans 60 ans += (c + m) // 3 61 print(ans) 62 ``` 63 64 **Solution 2 (PikMike)** 65 66 ``` 67 #include <bits/stdc++.h> 68 69 using namespace std; 70 71 int main(){ 72 int q; 73 cin >> q; 74 for (int i = 0; i < q; ++i){ 75 int c, m, x; 76 cin >> c >> m >> x; 77 int l = 0, r = min(c, m); 78 int ans = 0; 79 while (l <= r){ 80 int mid = (l + r) / 2; 81 if (c + m + x - 2 * mid >= mid){ 82 l = mid + 1; 83 ans = mid; 84 } 85 else{ 86 r = mid - 1; 87 } 88 } 89 cout << ans << "\n"; 90 } 91 } 92 ``` 93 94 [1221D - Make The Fence Great Again](/contest/1221/problem/D "Educational Codeforces Round 73 (Rated for Div. 2)") 95 96 Idea: [Roms](/profile/Roms "Master Roms") 97 98 **Tutorial** 99 100 Tutorial is loading... 101 102 **Solution (Roms)** 103 104 ``` 105 #include <bits/stdc++.h> 106 107 using namespace std; 108 109 const int N = int(3e5) + 99; 110 const long long INF64 = (long long)(1e18) + 100; 111 112 int t; 113 int n; 114 int a[N]; 115 int b[N]; 116 long long dp[3][N]; 117 118 long long calc(int add, int pos){ 119 long long &res = dp[add][pos]; 120 if(res != -1) return res; 121 122 res = INF64; 123 if(pos == n) return res = 0; 124 for(long long x = 0; x <= 2; ++x) 125 if(pos == 0 || a[pos] + x != a[pos - 1] + add) 126 res = min(res, calc(x, pos + 1) + x * b[pos]); 127 128 return res; 129 } 130 131 int main() { 132 scanf("%d", &t); 133 for(int tc = 0; tc < t; ++tc){ 134 scanf("%d", &n); 135 for(int i = 0; i < n; ++i){ 136 scanf("%d", a + i); 137 scanf("%d", b + i); 138 } 139 140 for(int i = 0; i <= n; ++i) 141 dp[0][i] = dp[1][i] = dp[2][i] = -1; 142 printf("%lld\n", calc(0, 0)); 143 } 144 return 0; 145 } 146 ``` 147 148 [1221E - Game With String](/contest/1221/problem/E "Educational Codeforces Round 73 (Rated for Div. 2)") 149 150 Idea: [Roms](/profile/Roms "Master Roms") 151 152 **Tutorial** 153 154 Tutorial is loading... 155 156 **Solution (Roms)** 157 158 ``` 159 #include <bits/stdc++.h> 160 161 using namespace std; 162 163 const int N = int(2e5) + 99; 164 165 int t; 166 int a, b; 167 string s; 168 169 int main() { 170 cin >> t; 171 for(int tc = 0; tc < t; ++tc){ 172 cin >> a >> b >> s; 173 vector <int> v; 174 int l = 0; 175 while(l < s.size()){ 176 if(s[l] == 'X'){ 177 ++l; 178 continue; 179 } 180 181 int r = l + 1; 182 while(r < s.size() && s[r] == '.') ++r; 183 v.push_back(r - l); 184 l = r; 185 } 186 187 bool ok = true; 188 int id = -1; 189 int cnt = 0; 190 for(int i = 0; i < v.size(); ++i){ 191 if(b <= v[i] && v[i] < a) ok = false; 192 if(b + b <= v[i]){ 193 if(id == -1) id = i; 194 else ok = false; 195 } 196 if(a <= v[i] && v[i] < b + b) ++cnt; 197 } 198 199 if(!ok){ 200 cout << "NO" << endl; 201 continue; 202 } 203 204 if(id == -1){ 205 if(cnt & 1) cout << "YES" << endl; 206 else cout << "NO" << endl; 207 continue; 208 } 209 210 ok = false; 211 int sz = v[id]; 212 assert(sz >= a); 213 for(int rem1 = 0; sz - a - rem1 >= 0; ++rem1){ 214 int rem2 = sz - a - rem1; 215 int ncnt = cnt; 216 if((rem1 >= b + b) || (b <= rem1 && rem1 < a)) continue; 217 if((rem2 >= b + b) || (b <= rem2 && rem2 < a)) continue; 218 219 if(rem1 >= a) ++ncnt; 220 if(rem2 >= a) ++ncnt; 221 if(ncnt % 2 == 0) ok = true; 222 } 223 224 if(ok) cout << "YES" << endl; 225 else cout << "NO" << endl; 226 } 227 return 0; 228 } 229 ``` 230 231 [1221F - Choose a Square](/contest/1221/problem/F "Educational Codeforces Round 73 (Rated for Div. 2)") 232 233 Idea: [Neon](/profile/Neon "Candidate Master Neon") 234 235 **Tutorial** 236 237 Tutorial is loading... 238 239 **Solution (Ne0n25)** 240 241 ``` 242 #include <bits/stdc++.h> 243 244 using namespace std; 245 246 #define x first 247 #define y second 248 #define mp make_pair 249 #define pb push_back 250 #define all(a) (a).begin(), (a).end() 251 #define sz(a) int((a).size()) 252 #define forn(i, n) for (int i = 0; i < int(n); ++i) 253 254 typedef long long li; 255 typedef pair<int, int> pt; 256 257 const int N = 1000 * 1000 + 13; 258 259 int n; 260 pair<pt, int> a[N]; 261 vector<int> vals; 262 vector<pt> ev[N]; 263 pair<li, int> t[4 * N]; 264 li add[4 * N]; 265 266 void build(int v, int l, int r) { 267 if (l == r) { 268 t[v] = mp(-vals[l], l); 269 add[v] = 0; 270 return; 271 } 272 int m = (l + r) >> 1; 273 build(v * 2 + 1, l, m); 274 build(v * 2 + 2, m + 1, r); 275 t[v] = max(t[v * 2 + 1], t[v * 2 + 2]); 276 } 277 278 void push(int v, int l, int r) { 279 if (add[v] == 0) return; 280 t[v].x += add[v]; 281 if (l != r) { 282 add[v * 2 + 1] += add[v]; 283 add[v * 2 + 2] += add[v]; 284 } 285 add[v] = 0; 286 } 287 288 void upd(int v, int l, int r, int L, int R, int val) { 289 push(v, l, r); 290 if (L > R) return; 291 if (l == L && r == R) { 292 add[v] += val; 293 push(v, l, r); 294 return; 295 } 296 int m = (l + r) >> 1; 297 upd(v * 2 + 1, l, m, L, min(m, R), val); 298 upd(v * 2 + 2, m + 1, r, max(m + 1, L), R, val); 299 t[v] = max(t[v * 2 + 1], t[v * 2 + 2]); 300 } 301 302 pair<li, int> get(int v, int l, int r, int L, int R) { 303 push(v, l, r); 304 if (L > R) return mp(-li(1e18), 0); 305 if (l == L && r == R) return t[v]; 306 int m = (l + r) >> 1; 307 auto r1 = get(v * 2 + 1, l, m, L, min(m, R)); 308 auto r2 = get(v * 2 + 2, m + 1, r, max(m + 1, L), R); 309 return max(r1, r2); 310 } 311 312 int main() { 313 scanf("%d", &n); 314 forn(i, n) scanf("%d%d%d", &a[i].x.x, &a[i].x.y, &a[i].y); 315 316 forn(i, n) { 317 vals.pb(a[i].x.x); 318 vals.pb(a[i].x.y); 319 } 320 321 vals.pb(0); 322 sort(all(vals)); 323 vals.pb(vals.back() + 1); 324 325 vals.resize(unique(all(vals)) - vals.begin()); 326 327 forn(i, n) { 328 int x = lower_bound(all(vals), a[i].x.x) - vals.begin(); 329 int y = lower_bound(all(vals), a[i].x.y) - vals.begin(); 330 ev[min(x, y)].pb(mp(max(x, y), a[i].y)); 331 } 332 333 n = sz(vals); 334 335 build(0, 0, n - 1); 336 337 li ans = -1; 338 int ansl = -1, ansr = -1; 339 340 for (int i = sz(vals) - 1; i >= 0; i--) { 341 for (auto it : ev[i]) upd(0, 0, n - 1, it.x, n - 1, it.y); 342 auto cur = get(0, 0, n - 1, i, n - 1); 343 if (cur.x + vals[i] > ans) { 344 ans = cur.x + vals[i]; 345 ansl = vals[i]; ansr = vals[cur.y]; 346 } 347 } 348 349 printf("%lld\n%d %d %d %d\n", ans, ansl, ansl, ansr, ansr); 350 351 } 352 ``` 353 354 [1221G - Graph And Numbers](/contest/1221/problem/G "Educational Codeforces Round 73 (Rated for Div. 2)") 355 356 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 357 358 **Tutorial** 359 360 Tutorial is loading... 361 362 **Solution (BledDest)** 363 364 ``` 365 #include <bits/stdc++.h> 366 367 using namespace std; 368 369 const int N = 40; 370 const int M = 20; 371 372 long long incident_mask[N]; 373 vector<int> g[N]; 374 int n, m; 375 long long ans = 0; 376 long long cntmask[1 << M]; 377 378 long long binpow(long long x, long long y) 379 { 380 long long z = 1; 381 while(y > 0) 382 { 383 if(y % 2 == 1) z *= x; 384 x *= x; 385 y /= 2; 386 } 387 return z; 388 } 389 390 int used[N]; 391 392 void dfs(int x, int c) 393 { 394 if(used[x]) 395 return; 396 used[x] = c; 397 for(auto y : g[x]) 398 dfs(y, 3 - c); 399 } 400 401 long long countIsolated() 402 { 403 long long ans = 0; 404 for(int i = 0; i < n; i++) 405 if(g[i].empty()) 406 ans++; 407 return ans; 408 } 409 410 long long countComponents() 411 { 412 memset(used, 0, sizeof used); 413 long long ans = 0; 414 for(int i = 0; i < n; i++) 415 if(!used[i]) 416 { 417 ans++; 418 dfs(i, 1); 419 } 420 return ans; 421 } 422 423 bool bipartite() 424 { 425 memset(used, 0, sizeof used); 426 for(int i = 0; i < n; i++) 427 if(!used[i]) 428 dfs(i, 1); 429 for(int i = 0; i < n; i++) 430 for(auto j : g[i]) 431 if(used[i] == used[j]) 432 return false; 433 return true; 434 } 435 436 long long countIndependentSets() 437 { 438 int m1 = min(n, 20); 439 int m2 = n - m1; 440 //cerr << m1 << " " << m2 << endl; 441 memset(cntmask, 0, sizeof cntmask); 442 for(int i = 0; i < (1 << m1); i++) 443 { 444 long long curmask = 0; 445 bool good = true; 446 for(int j = 0; j < m1; j++) 447 { 448 if((i & (1 << j)) == 0) 449 continue; 450 if(curmask & (1 << j)) 451 good = false; 452 curmask |= ((1 << j) | incident_mask[j]); 453 } 454 if(good) 455 { 456 cntmask[curmask >> m1]++; 457 } 458 } 459 for(int i = 0; i < m2; i++) 460 for(int j = 0; j < (1 << m2); j++) 461 if(j & (1 << i)) 462 cntmask[j] += cntmask[j ^ (1 << i)]; 463 long long ans = 0; 464 for(int i = 0; i < (1 << m2); i++) 465 { 466 long long curmask = 0; 467 bool good = true; 468 for(int j = m1; j < n; j++) 469 { 470 if((i & (1 << (j - m1))) == 0) 471 continue; 472 if(curmask & (1ll << j)) 473 good = false; 474 curmask |= (1ll << j) | incident_mask[j]; 475 } 476 if(good) 477 { 478 //cerr << i << endl; 479 ans += cntmask[(i ^ ((1 << m2) - 1))]; 480 } 481 } 482 return ans; 483 } 484 485 long long calc(int mask) 486 { 487 if(mask == 0) 488 return binpow(2, n); 489 if(mask == 1 || mask == 4) 490 return countIndependentSets(); 491 if(mask == 2) 492 return binpow(2, countComponents()); 493 if(mask == 3 || mask == 6) 494 return binpow(2, countIsolated()); 495 if(mask == 5) 496 return (bipartite() ? binpow(2, countComponents()) : 0); 497 if(mask == 7) 498 return (m == 0 ? binpow(2, n) : 0); 499 return 0; 500 } 501 502 int main() { 503 cin >> n >> m; 504 for(int i = 0; i < m; i++) 505 { 506 int x, y; 507 cin >> x >> y; 508 --x; 509 --y; 510 g[x].push_back(y); 511 g[y].push_back(x); 512 incident_mask[x] ^= (1ll << y); 513 incident_mask[y] ^= (1ll << x); 514 } 515 for(int i = 0; i < 8; i++) 516 { 517 //cerr << i << " " << calc(i) << endl; 518 if(__builtin_popcount(i) % 2 == 0) 519 ans += calc(i); 520 else 521 ans -= calc(i); 522 } 523 cout << ans << endl; 524 return 0; 525 } 526 ```