1216.md (10278B)
1 Source: https://codeforces.com/blog/entry/69954 2 3 All problems except the problem F are invented by [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm"). The problem F idea belongs to [BledDest](/profile/BledDest "International Grandmaster BledDest"). 4 5 [1216A - Prefixes](/contest/1216/problem/A "Codeforces Round 587 (Div. 3)") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 n, s = int(input()), list(input()) 15 ans = 0 16 for i in range(0, n, 2): 17 if (s[i] == s[i + 1]): 18 s[i] = chr(1 - ord(s[i]) + 2 * ord('a')) 19 ans += 1 20 print(ans) 21 print(''.join(s)) 22 ``` 23 24 [1216B - Shooting](/contest/1216/problem/B "Codeforces Round 587 (Div. 3)") 25 26 **Tutorial** 27 28 Tutorial is loading... 29 30 **Solution** 31 32 ``` 33 n, a = int(input()), list(map(int, input().split())) 34 res = [] 35 ans = 0 36 for i in range(n): 37 pos = -1 38 for j in range(n): 39 if (pos == -1 or a[j] > a[pos]): pos = j 40 res.append(pos + 1) 41 ans += i * a[pos] + 1 42 a[pos] = 0 43 print(ans) 44 print(' '.join([str(x) for x in res])) 45 ``` 46 47 [1216C - White Sheet](/contest/1216/problem/C "Codeforces Round 587 (Div. 3)") 48 49 **Tutorial** 50 51 Tutorial is loading... 52 53 **Solution 1** 54 55 ``` 56 #include <iostream> 57 #include <sstream> 58 #include <cstdio> 59 #include <vector> 60 #include <cmath> 61 #include <queue> 62 #include <string> 63 #include <cstring> 64 #include <cassert> 65 #include <iomanip> 66 #include <algorithm> 67 #include <set> 68 #include <map> 69 #include <ctime> 70 #include <cmath> 71 72 #define forn(i, n) for(int i=0;i<n;++i) 73 #define fore(i, l, r) for(int i = int(l); i <= int(r); ++i) 74 #define sz(v) int(v.size()) 75 #define all(v) v.begin(), v.end() 76 #define pb push_back 77 #define mp make_pair 78 #define x first 79 #define y1 ________y1 80 #define y second 81 #define ft first 82 #define sc second 83 #define pt pair<int, int> 84 85 template<typename X> inline X abs(const X& a) { return a < 0? -a: a; } 86 template<typename X> inline X sqr(const X& a) { return a * a; } 87 88 typedef long long li; 89 typedef long double ld; 90 91 using namespace std; 92 93 const int INF = 1000 * 1000 * 1000; 94 const ld EPS = 1e-9; 95 const ld PI = acos(-1.0); 96 97 int x1, y1, x2, y2, x3, y3, x4, y4, x5, y5, x6, y6; 98 99 inline void read() { 100 cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4 >> x5 >> y5 >> x6 >> y6; 101 x1 *= 2, y1 *= 2; 102 x2 *= 2, y2 *= 2; 103 x3 *= 2, y3 *= 2; 104 x4 *= 2, y4 *= 2; 105 x5 *= 2, y5 *= 2; 106 x6 *= 2, y6 *= 2; 107 } 108 109 inline bool ok(int x, int y, int x1, int y1, int x2, int y2) { 110 return x < x1 || x2 < x || y < y1 || y2 < y; 111 } 112 113 inline void solve() { 114 for (int x = x1; x <= x2; x++) { 115 if (ok(x, y1, x3, y3, x4, y4) && ok(x, y1, x5, y5, x6, y6)) { 116 cout << "YES" << endl; 117 return; 118 } 119 if (ok(x, y2, x3, y3, x4, y4) && ok(x, y2, x5, y5, x6, y6)) { 120 cout << "YES" << endl; 121 return; 122 } 123 } 124 for (int y = y1; y <= y2; y++) { 125 if (ok(x1, y, x3, y3, x4, y4) && ok(x1, y, x5, y5, x6, y6)) { 126 cout << "YES" << endl; 127 return; 128 } 129 if (ok(x2, y, x3, y3, x4, y4) && ok(x2, y, x5, y5, x6, y6)) { 130 cout << "YES" << endl; 131 return; 132 } 133 } 134 cout << "NO" << endl; 135 } 136 137 int main () { 138 #ifdef fcspartakm 139 freopen("input.txt", "r", stdin); 140 //freopen("output.txt", "w", stdout); 141 #endif 142 srand(time(NULL)); 143 cerr << setprecision(10) << fixed; 144 145 read(); 146 solve(); 147 148 //cerr << "TIME: " << clock() << endl; 149 } 150 ``` 151 152 **Solution 2** 153 154 ``` 155 #define _CRT_SECURE_NO_WARNINGS 156 157 #include <iostream> 158 #include <vector> 159 #include <algorithm> 160 #include <cstdio> 161 #include <random> 162 #include <ctime> 163 #include <string> 164 #include <iomanip> 165 #include <set> 166 #include <map> 167 #include <queue> 168 #include <stack> 169 170 using namespace std; 171 172 typedef long long li; 173 typedef unsigned long long uli; 174 typedef pair<int, int> pii; 175 typedef long double ld; 176 177 #define all(a) a.begin(), a.end() 178 #define rall(a) a.rbegin(), a.rend() 179 #define pb push_back 180 #define forn(i, n) for(int i = 0; i < int(n); ++i) 181 #define fore(i, l, r) for(int i = int(l); i < int(r); ++i) 182 #define forb(i, n) for(int i = int(n) - 1; i >= 0; --i) 183 #define vi vector<int> 184 #define x first 185 #define y second 186 187 const int INF = 2e9; 188 const li INF64 = 1e18; 189 const int M = 2 * 1000 * 1000; 190 const int N = 300 * 1000 + 100; 191 const int MOD = 1e9 + 7; 192 const double EPS = 1e-9; 193 const double PI = 3.14159265359; 194 195 pair<pii, pii> intersect(pii a, pii b, pii c, pii d) { 196 int lf, rg, up, dn; 197 lf = max(min(a.x, b.x), min(c.x, d.x)); 198 rg = min(max(a.x, b.x), max(c.x, d.x)); 199 up = min(max(a.y, b.y), max(c.y, d.y)); 200 dn = max(min(a.y, b.y), min(c.y, d.y)); 201 202 if (rg <= lf || up <= dn) return { {0, 0}, {0, 0} }; 203 204 return { { lf, dn }, { rg, up } }; 205 } 206 207 li square(pii a, pii b) { 208 return 1ll * abs(a.x - b.x) * abs(a.y - b.y); 209 } 210 211 int main() { 212 #ifdef _DEBUG 213 freopen("input.txt", "r", stdin); 214 freopen("output.txt", "w", stdout); 215 #endif 216 ios_base::sync_with_stdio(0); 217 cin.tie(0); 218 219 vector<pii> p(6); 220 221 forn(i, 6) 222 cin >> p[i].x >> p[i].y; 223 224 pair<pii, pii> wb1 = intersect(p[0], p[1], p[2], p[3]); 225 pair<pii, pii> wb2 = intersect(p[0], p[1], p[4], p[5]); 226 pair<pii, pii> inter = intersect(wb1.x, wb1.y, wb2.x, wb2.y); 227 228 li swhite = square(p[0], p[1]); 229 li swb1 = square(wb1.x, wb1.y); 230 li swb2 = square(wb2.x, wb2.y); 231 li sinter = square(inter.x, inter.y); 232 233 if (swhite > swb1 + swb2 - sinter) cout << "YES\n"; 234 else cout << "NO\n"; 235 } 236 ``` 237 238 [1216D - Swords](/contest/1216/problem/D "Codeforces Round 587 (Div. 3)") 239 240 **Tutorial** 241 242 Tutorial is loading... 243 244 **Solution** 245 246 ``` 247 #include <iostream> 248 #include <sstream> 249 #include <cstdio> 250 #include <vector> 251 #include <cmath> 252 #include <queue> 253 #include <string> 254 #include <cstring> 255 #include <cassert> 256 #include <iomanip> 257 #include <algorithm> 258 #include <set> 259 #include <map> 260 #include <ctime> 261 #include <cmath> 262 263 #define forn(i, n) for(int i=0;i<n;++i) 264 #define fore(i, l, r) for(int i = int(l); i <= int(r); ++i) 265 #define sz(v) int(v.size()) 266 #define all(v) v.begin(), v.end() 267 #define pb push_back 268 #define mp make_pair 269 #define x first 270 #define y1 ________y1 271 #define y second 272 #define ft first 273 #define sc second 274 #define pt pair<int, int> 275 276 template<typename X> inline X abs(const X& a) { return a < 0? -a: a; } 277 template<typename X> inline X sqr(const X& a) { return a * a; } 278 279 typedef long long li; 280 typedef long double ld; 281 282 using namespace std; 283 284 const int INF = 1000 * 1000 * 1000; 285 const ld EPS = 1e-9; 286 const ld PI = acos(-1.0); 287 288 const int N = 200 * 1000 + 13; 289 290 int n; 291 int a[N]; 292 293 inline void read() { 294 cin >> n; 295 for (int i = 0; i < n; i++) { 296 cin >> a[i]; 297 } 298 } 299 300 inline int gcd(int a, int b) { 301 while (a != 0 && b != 0) { 302 if (a > b) { 303 a %= b; 304 } else { 305 b %= a; 306 } 307 } 308 return max(a, b); 309 } 310 311 inline void solve() { 312 int ma = *max_element(a, a + n); 313 li sum = 0; 314 for (int i = 0; i < n; i++) { 315 sum += a[i]; 316 } 317 int g = ma - a[0]; 318 for (int i = 1; i < n; i++) { 319 g = gcd(g, ma - a[i]); 320 } 321 li ans = (ma * 1ll * n - sum) / g; 322 cout << ans << ' ' << g << endl; 323 } 324 325 int main () { 326 #ifdef fcspartakm 327 freopen("input.txt", "r", stdin); 328 //freopen("output.txt", "w", stdout); 329 #endif 330 srand(time(NULL)); 331 cerr << setprecision(10) << fixed; 332 333 read(); 334 solve(); 335 336 //cerr << "TIME: " << clock() << endl; 337 } 338 ``` 339 340 [1216E1 - Numerical Sequence (easy version)](/contest/1216/problem/E1 "Codeforces Round 587 (Div. 3)") 341 342 **Tutorial** 343 344 Tutorial is loading... 345 346 **Solution** 347 348 ``` 349 #include <bits/stdc++.h> 350 351 using namespace std; 352 353 int main() { 354 #ifdef _DEBUG 355 freopen("input.txt", "r", stdin); 356 // freopen("output.txt", "w", stdout); 357 #endif 358 359 int q; 360 cin >> q; 361 362 while (q--) { 363 long long k; 364 cin >> k; 365 --k; 366 long long lst = 0; 367 long long nxtpw = 1; 368 int numlen = 0; 369 for (long long i = 1; ; ++i) { 370 if (i == nxtpw) { 371 ++numlen; 372 nxtpw *= 10; 373 } 374 lst += numlen; 375 if (k >= lst) { 376 k -= lst; 377 } else { 378 long long nxtpw = 1; 379 int numlen = 0; 380 for (long long j = 1; j <= i; ++j) { 381 if (j == nxtpw) { 382 ++numlen; 383 nxtpw *= 10; 384 } 385 if (k >= numlen) { 386 k -= numlen; 387 } else { 388 cout << to_string(j)[k] << endl; 389 break; 390 } 391 } 392 break; 393 } 394 } 395 } 396 397 return 0; 398 } 399 ``` 400 401 [1216E2 - Numerical Sequence (hard version)](/contest/1216/problem/E2 "Codeforces Round 587 (Div. 3)") 402 403 **Tutorial** 404 405 Tutorial is loading... 406 407 **Solution** 408 409 ``` 410 #include <bits/stdc++.h> 411 412 using namespace std; 413 414 long long get(long long r) { 415 return (r + 1) * r / 2; 416 } 417 418 long long sumto(long long r, int need) { 419 long long pw = 1; 420 long long sum = 0; 421 long long add = 0; 422 for (int len = 1; ; ++len) { 423 if (pw * 10 - 1 < r) { 424 long long cnt = pw * 10 - pw; 425 if (need) { 426 sum += add * cnt + get(cnt) * len; 427 add += cnt * len; 428 } else { 429 sum += cnt * len; 430 } 431 } else { 432 long long cnt = r - pw + 1; 433 if (need) { 434 sum += add * cnt + get(cnt) * len; 435 } else { 436 sum += cnt * len; 437 } 438 break; 439 } 440 pw *= 10; 441 } 442 return sum; 443 } 444 445 int main() { 446 #ifdef _DEBUG 447 freopen("input.txt", "r", stdin); 448 // freopen("output.txt", "w", stdout); 449 #endif 450 451 int q; 452 cin >> q; 453 while (q--) { 454 long long k; 455 cin >> k; 456 --k; 457 458 long long l = 1 , r = 1e9; 459 long long res = -1; 460 while (r - l >= 0) { 461 long long mid = (l + r) >> 1; 462 if (sumto(mid, 1) > k) { 463 res = mid; 464 r = mid - 1; 465 } else { 466 l = mid + 1; 467 } 468 } 469 k -= sumto(res - 1, 1); 470 471 l = 1, r = res; 472 long long num = -1; 473 while (r - l >= 0) { 474 int mid = (l + r) >> 1; 475 if (sumto(mid, 0) > k) { 476 num = mid; 477 r = mid - 1; 478 } else { 479 l = mid + 1; 480 } 481 } 482 483 cout << to_string(num)[k - sumto(num - 1, 0)] << endl; 484 } 485 486 return 0; 487 } 488 ``` 489 490 [1216F - Wi-Fi](/contest/1216/problem/F "Codeforces Round 587 (Div. 3)") 491 492 **Tutorial** 493 494 Tutorial is loading... 495 496 **Solution** 497 498 ``` 499 #include <bits/stdc++.h> 500 501 using namespace std; 502 503 int main() { 504 #ifdef _DEBUG 505 freopen("input.txt", "r", stdin); 506 // freopen("output.txt", "w", stdout); 507 #endif 508 509 int n, k; 510 cin >> n >> k; 511 string s; 512 cin >> s; 513 514 vector<long long> dp(n + 1); 515 multiset<long long> mins, vals; 516 mins.insert(0); 517 vector<vector<long long>> del(n); 518 for (int i = n - 1; i >= 0; --i) { 519 dp[i] = i + 1 + dp[i + 1]; 520 if (i + k + 2 <= n) mins.erase(mins.find(dp[i + k + 2])); 521 for (auto it : del[i]) vals.erase(vals.find(it)); 522 if (!vals.empty()) dp[i] = min(dp[i], *vals.begin()); 523 if (s[i] == '1') { 524 long long val = (mins.empty() ? 0 : *mins.begin()) + i + 1; 525 dp[i] = min(dp[i], val); 526 vals.insert(val); 527 if (i - k - 1 >= 0) del[i - k - 1].push_back(val); 528 } 529 mins.insert(dp[i]); 530 } 531 532 cout << dp[0] << endl; 533 534 return 0; 535 } 536 ```