1051.md (11634B)
1 Source: https://codeforces.com/blog/entry/61969 2 3 [1051A - Vasya And Password](/contest/1051/problem/A "Educational Codeforces Round 51 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (Ajosteen)** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 string s; 17 18 bool ok(string t){ 19 int msk = 0; 20 21 for(int i = 0; i < int(t.size()); ++i){ 22 if(isupper(t[i])) msk |= 1; 23 if(islower(t[i])) msk |= 2; 24 if(isdigit(t[i])) msk |= 4; 25 } 26 27 return msk == 7; 28 } 29 30 int main() { 31 //freopen("input.txt", "r", stdin); 32 int t; 33 cin >> t; 34 for(int i = 0; i < t; ++i){ 35 cin >> s; 36 if(ok(s)){ 37 cout << s << endl; 38 continue; 39 } 40 bool fnd = false; 41 for(int i = 0; i < int(s.size()); ++i){ 42 string t = s; 43 44 t[i] = '1'; 45 if(ok(t)){ 46 cout << t << endl; 47 fnd = true; 48 break; 49 } 50 t[i] = 'a'; 51 if(ok(t)){ 52 cout << t << endl; 53 fnd = true; 54 break; 55 } 56 t[i] = 'A'; 57 if(ok(t)){ 58 cout << t << endl; 59 fnd = true; 60 break; 61 } 62 } 63 64 if(fnd) continue; 65 66 if(isupper(s[2])){ 67 s[0] = 'a'; 68 s[1] = '1'; 69 cout << s << endl; 70 continue; 71 } 72 if(islower(s[2])){ 73 s[0] = 'A'; 74 s[1] = '1'; 75 cout << s << endl; 76 continue; 77 } 78 if(isdigit(s[2])){ 79 s[0] = 'a'; 80 s[1] = 'A'; 81 cout << s << endl; 82 continue; 83 } 84 } 85 return 0; 86 } 87 ``` 88 89 [1051B - Relatively Prime Pairs](/contest/1051/problem/B "Educational Codeforces Round 51 (Rated for Div. 2)") 90 91 **Tutorial** 92 93 Tutorial is loading... 94 95 **Solution (PikMike)** 96 97 ``` 98 #include <bits/stdc++.h> 99 100 using namespace std; 101 102 #define forn(i, n) for(int i = 0; i < int(n); i++) 103 104 int main() { 105 long long l, r; 106 scanf("%lld%lld", &l, &r); 107 puts("YES"); 108 forn(i, (r - l) / 2 + 1) 109 printf("%lld %lld\n", l + i * 2, l + i * 2 + 1); 110 } 111 ``` 112 113 [1051C - Vasya and Multisets](/contest/1051/problem/C "Educational Codeforces Round 51 (Rated for Div. 2)") 114 115 **Tutorial** 116 117 Tutorial is loading... 118 119 **Solution (Ajosteen)** 120 121 ``` 122 #include <bits/stdc++.h> 123 124 using namespace std; 125 126 const int N = 109; 127 128 int n; 129 int a[N]; 130 map<int, int> m; 131 set <int> s[2]; 132 133 int main() { 134 int n; 135 cin >> n; 136 for(int i = 0; i < n; ++i){ 137 cin >> a[i]; 138 m[a[i]]++; 139 } 140 141 int pos = 0; 142 for(auto p : m) 143 if(p.second == 1){ 144 s[pos].insert(p.first); 145 pos = 1 - pos; 146 } 147 148 if(s[0].size() == s[1].size()){ 149 string res(n, 'A'); 150 for(int i = 0; i < n; ++i) 151 if(s[1].count(a[i])) 152 res[i] = 'B'; 153 154 cout << "YES" << endl; 155 for(auto c : res) cout << c; 156 cout << endl; 157 return 0; 158 } 159 else{ 160 assert(int(s[0].size()) - 1 == int(s[1].size())); 161 string res(n, 'A'); 162 for(int i = 0; i < n; ++i) 163 if(s[1].count(a[i])) 164 res[i] = 'B'; 165 166 int id = -1; 167 for(auto p : m) 168 if(p.second >= 3){ 169 id = p.first; 170 break; 171 } 172 173 if(id == -1){ 174 cout << "NO" << endl; 175 return 0; 176 } 177 178 bool flag = false; 179 for(int i = 0; i < n; ++i){ 180 if(a[i] == id) 181 if(!flag){ 182 flag = true; 183 res[i] = 'B'; 184 } 185 } 186 187 cout << "YES" << endl; 188 for(auto c : res) cout << c; 189 cout << endl; 190 return 0; 191 } 192 return 0; 193 } 194 195 ``` 196 197 [1051D - Bicolorings](/contest/1051/problem/D "Educational Codeforces Round 51 (Rated for Div. 2)") 198 199 **Tutorial** 200 201 Tutorial is loading... 202 203 **Solution (PikMike)** 204 205 ``` 206 #include <bits/stdc++.h> 207 208 using namespace std; 209 210 #define forn(i, n) for(int i = 0; i < int(n); i++) 211 212 const int N = 1000 + 7; 213 const int MOD = 998244353; 214 215 int dp[N][2 * N][4]; 216 217 int add(int a, int b){ 218 return (a + b) % MOD; 219 } 220 221 bool full(int mask){ 222 return (mask == 0 || mask == 3); 223 } 224 225 int get(int mask, int nmask){ 226 int cnt = __builtin_popcount(mask ^ nmask); 227 if (cnt == 0) return 0; 228 if (cnt == 2) return (full(mask) ? 1 : 2); 229 return (full(mask) ? 0 : 1); 230 } 231 232 int main() { 233 int n, k; 234 scanf("%d%d", &n, &k); 235 forn(i, 4) 236 dp[1][0][i] = 1; 237 238 for (int i = 1; i < n; ++i){ 239 forn(j, k + 1){ 240 forn(mask, 4){ 241 forn(nmask, 4){ 242 dp[i + 1][j + get(mask, nmask)][nmask] = add(dp[i + 1][j + get(mask, nmask)][nmask], dp[i][j][mask]); 243 } 244 } 245 } 246 } 247 248 int ans = 0; 249 forn(mask, 4){ 250 int nw = get(mask, mask ^ 3); 251 if (k >= nw) 252 ans = add(ans, dp[n][k - nw][mask]); 253 } 254 255 printf("%d\n", ans); 256 } 257 ``` 258 259 [1051E - Vasya and Big Integers](/contest/1051/problem/E "Educational Codeforces Round 51 (Rated for Div. 2)") 260 261 **Tutorial** 262 263 Tutorial is loading... 264 265 **Solution (Ajosteen)** 266 267 ``` 268 #include<bits/stdc++.h> 269 270 using namespace std; 271 272 #define sz(a) (int)(a.size()) 273 274 const int N = int(1e6) + 9; 275 const int MOD = 998244353; 276 277 int n; 278 string s, l, r; 279 int dp[N]; 280 int sumDP[N]; 281 282 int sum(int a, int b){ 283 a += b; 284 if(a >= MOD) a -= MOD; 285 return a; 286 } 287 288 vector <int> z_function(string s){ 289 int n = sz(s); 290 vector <int> z(n); 291 for(int i = 1, l = 0, r = 0; i < n; ++i){ 292 if(i <= r) 293 z[i] = min(r - i + 1, z[i - l]); 294 while(i + z[i] < n && s[z[i]] == s[i + z[i]]) 295 ++z[i]; 296 if(i + z[i] - 1 > r) 297 l = i, r = i + z[i] - 1; 298 } 299 return z; 300 } 301 302 //s[pos..] ? t 303 char cmp(vector <int> &zf, string &t, int pos){ 304 int len = sz(t); 305 assert(pos + len + 1 < sz(zf)); 306 if(sz(s) - pos < len) return '<'; 307 308 int x = zf[len + 1 + pos]; 309 assert(x <= len); 310 if(x == len) return '='; 311 assert(pos + x < sz(s)); 312 assert(s[pos + x] != t[x]); 313 if(s[pos + x] < t[x]) return '<'; 314 return '>'; 315 } 316 317 int main() { 318 //freopen("input.txt", "r", stdin); 319 320 ios_base::sync_with_stdio(false); 321 cin.tie(NULL); 322 323 cin >> s >> l >> r; 324 n = int(s.size()); 325 vector <int> zl = z_function(l + "#" + s); 326 vector <int> zr = z_function(r + "#" + s); 327 328 sumDP[n] = dp[n] = 1; 329 for(int i = n - 1; i >= 0; --i){ 330 if(s[i] == '0'){ 331 if(l == "0") dp[i] = dp[i + 1]; 332 else dp[i] = 0; 333 sumDP[i] = sum(dp[i], sumDP[i + 1]); 334 continue; 335 } 336 337 int L = sz(l) + i; 338 char cl = cmp(zl, l, i); 339 if(cl == '<') ++L; 340 341 int R = sz(r) + i; 342 char cr = cmp(zr, r, i); 343 if(cr == '>') --R; 344 345 int cur = 0; 346 if(L <= R && L <= n){ 347 R = min(R, n); 348 cur = sumDP[L]; 349 if(R != n) cur = sum(cur, MOD - sumDP[R + 1]); 350 } 351 dp[i] = cur; 352 sumDP[i] = sum(dp[i], sumDP[i + 1]); 353 } 354 355 cout << dp[0] << endl; 356 return 0; 357 } 358 ``` 359 360 [1051F - The Shortest Statement](/contest/1051/problem/F "Educational Codeforces Round 51 (Rated for Div. 2)") 361 362 **Tutorial** 363 364 Tutorial is loading... 365 366 **Solution (Ajosteen)** 367 368 ``` 369 #include <bits/stdc++.h> 370 371 using namespace std; 372 373 const int N = 300 * 1000 + 9; 374 const int LOGN = 19; 375 const int M = 21; 376 const long long INF64 = 1e18; 377 378 int n, m, q; 379 vector <pair<int, int> > g[N]; 380 int p[LOGN][N]; 381 int tin[N], tout[N], T; 382 long long h[N]; 383 set <pair<int, int> > badEdges; 384 long long d[M + M][N]; 385 bool u[N]; 386 387 void dfs(int v, int pr){ 388 tin[v] = T++; 389 p[0][v] = pr; 390 u[v] = true; 391 for(int i = 1; i < LOGN; ++i) 392 p[i][v] = p[i - 1][ p[i - 1][v] ]; 393 394 for(auto e : g[v]){ 395 int to = e.first, len = e.second; 396 if(!u[to]){ 397 h[to] = h[v] + len; 398 dfs(to, v); 399 400 if(v < to) 401 badEdges.erase(make_pair(v, to)); 402 else 403 badEdges.erase(make_pair(to, v)); 404 } 405 } 406 407 tout[v] = T; 408 } 409 410 bool isAncestor(int a, int b){ 411 return tin[a] <= tin[b] && tout[a] >= tout[b]; 412 } 413 414 int getLCA(int a, int b){ 415 if(isAncestor(a, b)) return a; 416 if(isAncestor(b, a)) return b; 417 418 for(int i = LOGN - 1; i >= 0; --i) 419 if(!isAncestor(p[i][a], b)) 420 a = p[i][a]; 421 422 return p[0][a]; 423 } 424 425 void dij(int st, long long d[N]){ 426 set<pair<long long, int> > q; 427 for(int i = 0; i < n; ++i) d[i] = INF64; 428 d[st] = 0; 429 q.insert(make_pair(d[st], st)); 430 431 while(!q.empty()){ 432 int v = q.begin()->second; 433 q.erase(q.begin()); 434 435 for(auto e : g[v]){ 436 int to = e.first, len = e.second; 437 if(d[to] > d[v] + len){ 438 q.erase(make_pair(d[to], to)); 439 d[to] = d[v] + len; 440 q.insert(make_pair(d[to], to)); 441 } 442 } 443 } 444 } 445 446 int main() { 447 //freopen("input.txt", "r", stdin); 448 449 scanf("%d %d", &n, &m); 450 for(int i = 0; i < m; ++i){ 451 int u, v, w; 452 scanf("%d %d %d", &u, &v, &w); 453 --u, --v; 454 g[u].push_back(make_pair(v, w)); 455 g[v].push_back(make_pair(u, w)); 456 } 457 458 for(int v = 0; v < n; ++v) 459 for(auto e : g[v]) 460 if(v < e.first) 461 badEdges.insert(make_pair(v, e.first)); 462 463 dfs(0, 0); 464 465 int cpos = 0; 466 for(auto e : badEdges) 467 dij(e.first, d[cpos++]); 468 scanf("%d", &q); 469 for(int tc = 0; tc < q; ++tc){ 470 int u, v; 471 scanf("%d %d", &u, &v); 472 --u, --v; 473 int lca = getLCA(u, v); 474 long long ans = h[u] + h[v] - 2 * h[lca]; 475 for(int i = 0; i < badEdges.size(); ++i) 476 ans = min(ans, d[i][u] + d[i][v]); 477 478 printf("%lld\n", ans); 479 } 480 return 0; 481 } 482 ``` 483 484 [1051G - Distinctification](/contest/1051/problem/G "Educational Codeforces Round 51 (Rated for Div. 2)") 485 486 **Tutorial** 487 488 Tutorial is loading... 489 490 **Solution (BledDest)** 491 492 ``` 493 #include <bits/stdc++.h> 494 495 using namespace std; 496 497 #define x first 498 #define y second 499 500 typedef long long li; 501 502 mt19937 rnd(time(NULL)); 503 504 struct node 505 { 506 int x; 507 int y; 508 li sum; 509 int siz; 510 node* l; 511 node* r; 512 node() {}; 513 node(int x, int y, li sum, int siz, node* l, node* r) : x(x), y(y), sum(sum), siz(siz), l(l), r(r) {}; 514 }; 515 516 typedef node* treap; 517 typedef pair<treap, treap> ptt; 518 519 int getSiz(treap t) 520 { 521 return (t ? t->siz : 0); 522 } 523 524 li getSum(treap t) 525 { 526 return (t ? t->sum : 0); 527 } 528 529 treap fix(treap t) 530 { 531 if(!t) return t; 532 t->sum = getSum(t->l) + t->x + getSum(t->r); 533 t->siz = getSiz(t->l) + 1 + getSiz(t->r); 534 return t; 535 } 536 537 ptt split(treap t, int l) 538 { 539 t = fix(t); 540 if(!t) return make_pair(t, t); 541 if(t->x < l) 542 { 543 auto z = split(t->r, l); 544 t->r = z.x; 545 return make_pair(fix(t), z.y); 546 } 547 else 548 { 549 auto z = split(t->l, l); 550 t->l = z.y; 551 return make_pair(z.x, fix(t)); 552 } 553 } 554 555 treap merge(treap a, treap b) 556 { 557 a = fix(a); 558 b = fix(b); 559 if(!a) return b; 560 if(!b) return a; 561 if(a->y > b->y) 562 { 563 a->r = merge(a->r, b); 564 return fix(a); 565 } 566 else 567 { 568 b->l = merge(a, b->l); 569 return fix(b); 570 } 571 } 572 573 struct comp 574 { 575 li cur_sum; 576 int beg; 577 li treap_sum; 578 treap t; 579 580 void upd() 581 { 582 cur_sum = treap_sum + beg * 1ll * getSum(t); 583 } 584 585 void insert(int bi) 586 { 587 ptt p = split(t, bi); 588 treap_sum += getSum(p.x) + getSiz(p.y) * 1ll * bi; 589 t = merge(p.x, merge(new node(bi, rnd(), bi, 1, NULL, NULL), p.y)); 590 upd(); 591 } 592 593 void fill_treap(treap t) 594 { 595 if(!t) return; 596 insert(t->x); 597 fill_treap(t->l); 598 fill_treap(t->r); 599 } 600 }; 601 602 comp merge(comp a, comp b) 603 { 604 if(getSiz(a.t) < getSiz(b.t)) 605 swap(a, b); 606 a.beg = min(a.beg, b.beg); 607 a.fill_treap(b.t); 608 delete b.t; 609 a.upd(); 610 return a; 611 } 612 613 set<int> free_pos; 614 615 const int N = 400043; 616 617 int p[N]; 618 int siz[N]; 619 comp cc[N]; 620 621 li start_sum = 0; 622 li end_sum = 0; 623 624 int get(int x) 625 { 626 return (p[x] == x ? x : (p[x] = get(p[x]))); 627 } 628 629 void merge(int x, int y) 630 { 631 x = get(x); 632 y = get(y); 633 if(x == y) return; 634 if(siz[x] < siz[y]) swap(x, y); 635 end_sum -= cc[x].cur_sum; 636 end_sum -= cc[y].cur_sum; 637 p[y] = x; 638 siz[x] += siz[y]; 639 cc[x] = merge(cc[x], cc[y]); 640 end_sum += cc[x].cur_sum; 641 } 642 643 void process(int ai, int bi) 644 { 645 start_sum += ai * 1ll * bi; 646 int pos = *free_pos.lower_bound(ai); 647 free_pos.erase(pos); 648 siz[pos] = 1; 649 p[pos] = pos; 650 cc[pos].beg = pos; 651 cc[pos].insert(bi); 652 end_sum += cc[pos].cur_sum; 653 if(!free_pos.count(pos - 1)) 654 merge(pos, pos - 1); 655 if(!free_pos.count(pos + 1)) 656 merge(pos, pos + 1); 657 printf("%lld\n", end_sum - start_sum); 658 } 659 660 int main() { 661 #ifdef _DEBUG 662 freopen("input.txt", "r", stdin); 663 freopen("output.txt", "w", stdout); 664 #endif 665 int n; 666 scanf("%d", &n); 667 for(int i = 0; i < N; i++) 668 free_pos.insert(i); 669 for(int i = 0; i < n; i++) 670 { 671 int a, b; 672 scanf("%d %d", &a, &b); 673 process(a, b); 674 } 675 return 0; 676 } 677 ```