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