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