1185.md (13685B)
1 Source: https://codeforces.com/blog/entry/67829 2 3 Tutorial is loading... 4 5 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") and [geranazavr555](/profile/geranazavr555 "Эксперт geranazavr555") 6 7 **Authors' solution** 8 9 ``` 10 def solve(a, b, c, d): 11 return max(0, d - (b - a)) + max(0, d - (c - b)) 12 13 def main(): 14 a, b, c, d = map(int, input().split()) 15 a, b, c = sorted((a, b, c)) 16 print(solve(a, b, c, d)) 17 18 main() 19 ``` 20 21 Tutorial is loading... 22 23 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 24 25 **Authors' solution** 26 27 ``` 28 #include <bits/stdc++.h> 29 30 using namespace std; 31 32 #define forn(i, n) for (int i = 0; i < int(n); i++) 33 34 vector<pair<char,int>> split(string s) { 35 char c = s[0]; 36 int cnt = 1; 37 vector<pair<char,int>> result; 38 auto ss = s.c_str(); 39 for (int i = 1; i <= int(s.length()); i++) { 40 if (ss[i] != c) { 41 result.push_back({c, cnt}); 42 c = s[i]; 43 cnt = 1; 44 } else 45 cnt++; 46 } 47 return result; 48 } 49 50 int main() { 51 int n; 52 cin >> n; 53 forn(tt, n) { 54 string s, t; 55 cin >> s >> t; 56 auto sa(split(s)), ta(split(t)); 57 bool ok = sa.size() == ta.size(); 58 if (ok) 59 forn(i, sa.size()) 60 if (sa[i].first != ta[i].first || sa[i].second > ta[i].second) 61 ok = false; 62 cout << (ok ? "YES" : "NO") << endl; 63 } 64 } 65 ``` 66 67 Tutorial is loading... 68 69 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"), [cannor147](/profile/cannor147 "Специалист cannor147") and [geranazavr555](/profile/geranazavr555 "Эксперт geranazavr555") 70 71 **Authors' solution** 72 73 ``` 74 #include <bits/stdc++.h> 75 76 using namespace std; 77 78 const int T = 100; 79 80 int main() { 81 int n, m; 82 cin >> n >> m; 83 84 int sum = 0; 85 vector<int> t(n), count(T + 1, 0); 86 for (int i = 0; i < n; i++) { 87 cin >> t[i]; 88 } 89 90 for (int i = 0; i < n; i++) { 91 int d = sum + t[i] - m, k = 0; 92 if (d > 0) { 93 for (int j = T; j > 0; j--) { 94 int x = j * count[j]; 95 if (d <= x) { 96 k += (d + j - 1) / j; 97 break; 98 } 99 k += count[j]; 100 d -= x; 101 } 102 } 103 sum += t[i]; 104 count[t[i]]++; 105 cout << k << " "; 106 } 107 } 108 ``` 109 110 Tutorial is loading... 111 112 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"), [cannor147](/profile/cannor147 "Специалист cannor147") and [geranazavr555](/profile/geranazavr555 "Эксперт geranazavr555") 113 114 **Authors' solution** 115 116 ``` 117 #include <bits/stdc++.h> 118 119 using namespace std; 120 121 const int T = 100; 122 123 int main() { 124 int n, m; 125 cin >> n >> m; 126 127 int sum = 0; 128 vector<int> t(n), count(T + 1, 0); 129 for (int i = 0; i < n; i++) { 130 cin >> t[i]; 131 } 132 133 for (int i = 0; i < n; i++) { 134 int d = sum + t[i] - m, k = 0; 135 if (d > 0) { 136 for (int j = T; j > 0; j--) { 137 int x = j * count[j]; 138 if (d <= x) { 139 k += (d + j - 1) / j; 140 break; 141 } 142 k += count[j]; 143 d -= x; 144 } 145 } 146 sum += t[i]; 147 count[t[i]]++; 148 cout << k << " "; 149 } 150 } 151 ``` 152 153 Tutorial is loading... 154 155 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 156 157 **Authors' solution** 158 159 ``` 160 #include <bits/stdc++.h> 161 162 using namespace std; 163 164 int main() { 165 int n; 166 cin >> n; 167 168 vector<pair<int, int>> b(n); 169 for (int i = 0; i < n; i++) { 170 int x; 171 cin >> x; 172 b[i] = {x, i}; 173 } 174 sort(b.begin(), b.end()); 175 176 vector<int> d(n - 1); 177 for (int i = 1; i < n; i++) { 178 d[i - 1] = b[i].first - b[i - 1].first; 179 } 180 181 bool f = true; 182 for (int i = 2; i < n - 1; i++) { 183 f &= d[i] == d[1]; 184 } 185 if (f) { 186 cout << b[0].second + 1; 187 return 0; 188 } 189 190 f = true; 191 for (int i = 2; i < n - 1; i++) { 192 f &= d[i] == b[2].first - b[0].first; 193 } 194 if (f) { 195 cout << b[1].second + 1; 196 return 0; 197 } 198 199 int answer; 200 f = false; 201 for (int i = 1; i < n - 1; i++) { 202 if (d[i] == d[0]) continue; 203 if (f) { 204 cout << -1; 205 return 0; 206 } else { 207 if (i == n - 2) { 208 cout << b[n - 1].second + 1; 209 return 0; 210 } else { 211 if (b[i + 2].first - b[i].first == d[0]) { 212 answer = b[i + 1].second; 213 f = true; 214 i++; 215 } else { 216 cout << -1; 217 return 0; 218 } 219 } 220 } 221 } 222 223 if (f) { 224 cout << answer + 1; 225 } else { 226 cout << b[n - 1].second + 1; 227 } 228 } 229 ``` 230 231 Tutorial is loading... 232 233 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"), [cannor147](/profile/cannor147 "Специалист cannor147") and [geranazavr555](/profile/geranazavr555 "Эксперт geranazavr555") 234 235 **Authors' solution** 236 237 ``` 238 #include <bits/stdc++.h> 239 240 using namespace std; 241 242 #define forn(i, n) for (int i = 0; i < int(n); i++) 243 244 int min(int a, int b) { 245 return (a < b) ? a : b; 246 } 247 int max(int a, int b) { 248 return (a > b) ? a : b; 249 } 250 251 int main() { 252 int t; 253 cin >> t; 254 255 vector<string> lines(2000, ""); 256 vector<int> vertical_min(26, 2001), vertical_max(26, -1); 257 vector<int> horizontal_min(26, 2001), horizontal_max(26, -1); 258 259 for (int k = 0; k < t; k++) { 260 int n, m; 261 cin >> n >> m; 262 for (int i = 0; i < n; i++) { 263 cin >> lines[i]; 264 } 265 266 for (int b = 0; b < 26; b++) { 267 vertical_min[b] = 2001; 268 horizontal_min[b] = 2001; 269 vertical_max[b] = -1; 270 horizontal_max[b] = -1; 271 } 272 for (int i = 0; i < n; i++) { 273 for (int j = 0; j < m; j++) { 274 if (lines[i][j] != '.') { 275 int b = (int) (lines[i][j] - 'a'); 276 vertical_min[b] = min(vertical_min[b], i); 277 vertical_max[b] = max(vertical_max[b], i); 278 horizontal_min[b] = min(horizontal_min[b], j); 279 horizontal_max[b] = max(horizontal_max[b], j); 280 } 281 } 282 } 283 284 bool f = true, q = false; 285 int count = 26; 286 for (int b = 25; b >= 0; b--) { 287 if (vertical_max[b] == -1) { 288 if (!q) { 289 count--; 290 continue; 291 } else { 292 vertical_min[b] = vertical_min[b + 1]; 293 vertical_max[b] = vertical_max[b + 1]; 294 horizontal_min[b] = horizontal_min[b + 1]; 295 horizontal_max[b] = horizontal_max[b + 1]; 296 continue; 297 } 298 } 299 300 q = true; 301 if (vertical_max[b] == vertical_min[b]) { 302 for (int j = horizontal_min[b]; j <= horizontal_max[b]; j++) { 303 if (lines[vertical_max[b]][j] == 'a' + b || (q && lines[vertical_max[b]][j] == '*')) { 304 lines[vertical_max[b]][j] = '*'; 305 } else { 306 f = false; 307 break; 308 } 309 } 310 } else if (horizontal_max[b] == horizontal_min[b]) { 311 for (int i = vertical_min[b]; i <= vertical_max[b]; i++) { 312 if (lines[i][horizontal_max[b]] == 'a' + b || (q && lines[i][horizontal_max[b]] == '*')) { 313 lines[i][horizontal_max[b]] = '*'; 314 } else { 315 f = false; 316 break; 317 } 318 } 319 } else { 320 f = false; 321 } 322 if (!f) { 323 break; 324 } 325 } 326 327 if (f) { 328 cout << "YES" << endl; 329 cout << count << endl; 330 for (int i = 0; i < count; i++) { 331 cout << vertical_min[i] + 1 << " " << horizontal_min[i] + 1 << " " << vertical_max[i] + 1 << " " << horizontal_max[i] + 1 << endl; 332 } 333 } else { 334 cout << "NO" << endl; 335 } 336 } 337 } 338 ``` 339 340 Tutorial is loading... 341 342 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"), [cannor147](/profile/cannor147 "Специалист cannor147") and [geranazavr555](/profile/geranazavr555 "Эксперт geranazavr555") 343 344 **Authors' solution** 345 346 ``` 347 #include <bits/stdc++.h> 348 349 using namespace std; 350 351 #define x first 352 #define y second 353 #define pb push_back 354 #define mp make_pair 355 #define sqr(a) ((a) * (a)) 356 #define sz(a) int((a).size()) 357 #define all(a) (a).begin(), (a).end() 358 #define forn(i, n) for (int i = 0; i < int(n); ++i) 359 #define fore(i, l, r) for (int i = int(l); i < int(r); ++i) 360 361 template<class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) { 362 return out << "(" << a.x << ", " << a.y << ")"; 363 } 364 365 template<class A> ostream& operator << (ostream& out, const vector<A> &a) { 366 out << "["; 367 for (auto it = a.begin(); it != a.end(); ++it) { 368 if (it != a.begin()) 369 out << ", "; 370 out << *it; 371 } 372 return out << "]"; 373 } 374 375 typedef long long li; 376 typedef long double ld; 377 typedef pair<int, int> pt; 378 379 const int INF = 1e9; 380 const li INF64 = 1e18; 381 const int MOD = 1e9 + 7; 382 const ld PI = acosl(-1.0); 383 const ld EPS = 1e-9; 384 385 mt19937 rnd(time(NULL)); 386 mt19937_64 rnd64(time(NULL)); 387 388 const int N = 100 * 1000 + 11; 389 const int MSK = 1 << 9; 390 391 int n, m; 392 int cnt[MSK]; 393 vector<pt> pz[N]; 394 395 bool read() { 396 if (scanf("%d %d", &n, &m) != 2) 397 return false; 398 forn(i, n) { 399 int k; 400 scanf("%d", &k); 401 int msk = 0; 402 forn(j, k) { 403 int pos; 404 scanf("%d", &pos); 405 --pos; 406 msk |= (1 << pos); 407 } 408 ++cnt[msk]; 409 } 410 return true; 411 } 412 413 void solve() { 414 forn(i, m) { 415 int c; 416 scanf("%d", &c); 417 int msk = 0; 418 int k; 419 scanf("%d", &k); 420 forn(j, k) { 421 int pos; 422 scanf("%d", &pos); 423 --pos; 424 msk |= (1 << pos); 425 } 426 pz[msk].pb(mp(c, i)); 427 sort(all(pz[msk])); 428 while (sz(pz[msk]) > 2) pz[msk].pop_back(); 429 } 430 int ans = 0, cost = 2 * INF + 1; 431 pt res = mp(-1, -1); 432 forn(p1, MSK) forn(p2, MSK) { 433 int curcost = 0; 434 int pos1, pos2; 435 if (p1 == p2) { 436 if (sz(pz[p1]) < 2) continue; 437 curcost = pz[p1][0].x + pz[p1][1].x; 438 pos1 = pz[p1][0].y; 439 pos2 = pz[p1][1].y; 440 } else { 441 if (sz(pz[p1]) == 0 || sz(pz[p2]) == 0) continue; 442 curcost = pz[p1][0].x + pz[p2][0].x; 443 pos1 = pz[p1][0].y; 444 pos2 = pz[p2][0].y; 445 } 446 int curans = 0; 447 int curmask = p1 | p2; 448 forn(pp, MSK) { 449 if ((curmask & pp) == pp) { 450 curans += cnt[pp]; 451 } 452 } 453 if (curans > ans || (curans == ans && curcost < cost)) { 454 ans = curans; 455 cost = curcost; 456 res = mp(pos1, pos2); 457 } 458 } 459 cout << res.x + 1 << " " << res.y + 1 << endl; 460 } 461 462 int main() { 463 #ifdef _DEBUG 464 freopen("input.txt", "r", stdin); 465 //freopen("output.txt", "w", stdout); 466 467 int tt = clock(); 468 #endif 469 470 cout << fixed << setprecision(10); 471 cerr << fixed << setprecision(10); 472 473 #ifdef _DEBUG 474 while (read()) { 475 #else 476 if (read()) { 477 #endif 478 solve(); 479 480 #ifdef _DEBUG 481 cerr << "TIME = " << clock() - tt << endl; 482 tt = clock(); 483 #endif 484 } 485 } 486 ``` 487 488 Tutorial is loading... 489 490 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"), [cannor147](/profile/cannor147 "Специалист cannor147") and [geranazavr555](/profile/geranazavr555 "Эксперт geranazavr555") 491 492 **Authors' solution** 493 494 ``` 495 #include <bits/stdc++.h> 496 497 using namespace std; 498 499 #define forn(i, n) for (int i = 0; i < int(n); i++) 500 501 const int M = 1000000007; 502 const int N = 16; 503 504 int d[1 << N][4]; 505 506 int main() { 507 int n, T; 508 cin >> n >> T; 509 vector<int> durs(n), types(n); 510 forn(i, n) { 511 cin >> durs[i] >> types[i]; 512 types[i]--; 513 } 514 515 int result = 0; 516 d[0][3] = 1; 517 forn(mask, 1 << n) 518 forn(lst, 4) { 519 forn(j, n) 520 if (types[j] != lst && ((mask & (1 << j)) == 0)) 521 d[mask ^ (1 << j)][types[j]] = (d[mask ^ (1 << j)][types[j]] + d[mask][lst]) % M; 522 int sum = 0; 523 forn(i, n) 524 if (mask & (1 << i)) 525 sum += durs[i]; 526 if (sum == T) 527 result = (result + d[mask][lst]) % M; 528 } 529 530 cout << result << endl; 531 } 532 ``` 533 534 Tutorial is loading... 535 536 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"), [cannor147](/profile/cannor147 "Специалист cannor147") and [geranazavr555](/profile/geranazavr555 "Эксперт geranazavr555") 537 538 **Authors' solution** 539 540 ``` 541 #include <bits/stdc++.h> 542 543 using namespace std; 544 545 #define forn(i, n) for (int i = 0; i < int(n); i++) 546 547 const int M = 1000000007; 548 const int N = 51; 549 const int S = 2501; 550 551 void inc(int& a, int d) { 552 a += d; 553 if (a >= M) 554 a -= M; 555 } 556 557 int a[N][S]; 558 int bc[N][N][S]; 559 int ways[N][N][N][4]; 560 561 int main() { 562 int n, T; 563 cin >> n >> T; 564 565 vector<int> cnts(4); 566 vector<int> durs(4); 567 568 a[0][0] = bc[0][0][0] = 1; 569 forn(i, n) { 570 int dur, type; 571 cin >> dur >> type; 572 type--; 573 if (type == 0) { 574 for (int cnts0 = cnts[0]; cnts0 >= 0; cnts0--) 575 forn(durs0, durs[0] + 1) 576 inc(a[cnts0 + 1][durs0 + dur], a[cnts0][durs0]); 577 } else { 578 for (int cnts1 = cnts[1]; cnts1 >= 0; cnts1--) 579 for (int cnts2 = cnts[2]; cnts2 >= 0; cnts2--) 580 forn(durs12, durs[1] + durs[2] + 1) 581 inc(bc[cnts1 + (type == 1)][cnts2 + (type == 2)][durs12 + dur], 582 bc[cnts1][cnts2][durs12]); 583 } 584 cnts[type]++; 585 durs[type] += dur; 586 } 587 588 ways[0][0][0][3] = 1; 589 vector<int> c(3); 590 for (c[0] = 0; c[0] <= cnts[0]; c[0]++) 591 for (c[1] = 0; c[1] <= cnts[1]; c[1]++) 592 for (c[2] = 0; c[2] <= cnts[2]; c[2]++) 593 forn(lst, 4) 594 if (ways[c[0]][c[1]][c[2]][lst] != 0) { 595 forn(nxt, 3) 596 if (nxt != lst && c[nxt] + 1 <= cnts[nxt]) { 597 vector<int> cn(c); 598 cn[nxt]++; 599 inc(ways[cn[0]][cn[1]][cn[2]][nxt], ways[c[0]][c[1]][c[2]][lst]); 600 } 601 } 602 603 vector<int> f(N + 1, 1); 604 forn(i, N) 605 f[i + 1] = ((long long) f[i]) * (i + 1) % M; 606 607 int result = 0; 608 for (c[0] = 0; c[0] <= cnts[0]; c[0]++) 609 forn(durs0, durs[0] + 1) 610 if (T - durs0 >= 0) 611 for (c[1] = 0; c[1] <= cnts[1]; c[1]++) 612 for (c[2] = 0; c[2] <= cnts[2]; c[2]++) { 613 long long extra = (long long)(a[c[0]][durs0]) * bc[c[1]][c[2]][T - durs0] % M; 614 forn(i, 3) 615 extra = extra * f[c[i]] % M; 616 forn(lst, 3) 617 if (c[lst] > 0) 618 inc(result, extra * ways[c[0]][c[1]][c[2]][lst] % M); 619 } 620 621 cout << result << endl; 622 } 623 ```