1245.md (9874B)
1 Source: https://codeforces.com/blog/entry/71080 2 3 [1245A - Good ol' Numbers Coloring](/contest/1245/problem/A "Codeforces Round 597 (Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution** 10 11 ``` 12 #include <bits/stdc++.h> 13 using namespace std; 14 15 int gcd(int a, int b) 16 { 17 while (b) 18 { 19 a %= b; 20 swap(a, b); 21 } 22 23 return a; 24 } 25 26 int main() 27 { 28 int t; 29 for (cin >> t; t--;) 30 31 { 32 int a, b; 33 cin >> a >> b; 34 35 if (gcd(a, b) == 1) 36 cout << "Finite" << '\n'; 37 else 38 cout << "Infinite" << '\n'; 39 } 40 41 return 0; 42 } 43 ``` 44 45 [1245B - Restricted RPS](/contest/1245/problem/B "Codeforces Round 597 (Div. 2)") 46 47 **Tutorial** 48 49 Tutorial is loading... 50 51 **Solution** 52 53 ``` 54 #include <vector> 55 #include <string> 56 #include <iostream> 57 #include <cstdio> 58 #include <algorithm> 59 #include <stack> 60 #include <queue> 61 #include <deque> 62 #include <set> 63 #include <map> 64 using namespace std; 65 66 int main() 67 { 68 ios_base::sync_with_stdio(0); 69 cin.tie(0); 70 71 int q; 72 for (cin >> q; q--;) 73 { 74 int n; 75 cin >> n; 76 int a, b, c; 77 cin >> a >> b >> c; 78 string s; 79 cin >> s; 80 81 vector<int> count(26); 82 for (char x : s) 83 count[x - 'A']++; 84 85 int wins = min(a, count['S' - 'A']) + min(b, count['R' - 'A']) + min(c, count['P' - 'A']); 86 87 if (2 * wins < n) 88 { 89 cout << "NO" << '\n';continue; 90 } 91 92 cout << "YES" << '\n'; 93 string t; 94 for (int i = 0; i != n; ++i) 95 { 96 if (s[i] == 'S' && a) 97 { 98 t += 'R'; 99 a--; 100 } 101 else if (s[i] == 'R' && b) 102 { 103 t += 'P'; 104 b--; 105 } 106 else if (s[i] == 'P' && c) 107 { 108 t += 'S'; 109 c--; 110 } 111 else 112 t += '_'; 113 } 114 for (int i = 0; i != n; ++i) 115 { 116 if (t[i] != '_') 117 continue; 118 119 if (a) 120 { 121 t[i] = 'R'; 122 a--; 123 } 124 else if (b) 125 { 126 t[i] = 'P'; 127 b--; 128 } 129 else 130 { 131 t[i] = 'S'; 132 c--; 133 } 134 } 135 cout << t << '\n'; 136 } 137 138 return 0; 139 } 140 ``` 141 142 [1245C - Constanze's Machine](/contest/1245/problem/C "Codeforces Round 597 (Div. 2)") 143 144 **Tutorial** 145 146 Tutorial is loading... 147 148 **Solution** 149 150 ``` 151 #include <vector> 152 #include <string> 153 #include <iostream> 154 #include <cstdio> 155 #include <algorithm> 156 #include <stack> 157 #include <queue> 158 #include <deque> 159 #include <set> 160 #include <map> 161 using namespace std; 162 163 const int MOD = 1000000007; 164 165 int main() 166 { 167 ios_base::sync_with_stdio(0); 168 cin.tie(0); 169 170 string s; 171 cin >> s; 172 173 for (char x : s) 174 { 175 if (x == 'w' || x == 'm') 176 { 177 cout << 0 << '\n'; 178 return 0; 179 } 180 } 181 182 int n = s.size(); 183 vector<int> dp(n + 1); 184 dp[0] = 1; 185 dp[1] = 1; 186 for (int i = 2; i <= n; ++i) 187 { 188 dp[i] = dp[i - 1]; 189 if (s[i - 1] == s[i - 2] && (s[i - 1] == 'u' || s[i - 1] == 'n')) 190 dp[i] = (dp[i] + dp[i - 2]) % MOD; 191 } 192 193 cout << dp[n] << '\n'; 194 195 return 0; 196 } 197 ``` 198 199 **Solution (Arpa)** 200 201 ``` 202 // In the name of Allah. 203 // We're nothing and you're everything. 204 // Ya Ali! 205 206 #include <bits/stdc++.h> 207 using namespace std; 208 typedef long long ll; 209 210 const int maxn = 1e5 + 14, mod = 1e9 + 7; 211 212 int n, fib[maxn]; 213 214 int main(){ 215 ios::sync_with_stdio(0), cin.tie(0); 216 fib[0] = fib[1] = 1; 217 for(int i = 2; i < maxn; i++) 218 fib[i] = (fib[i - 1] + fib[i - 2]) % mod; 219 string s; 220 cin >> s; 221 n = s.size(); 222 if(s.find('m') != -1 || s.find('w') != -1) 223 return cout << "0\n", 0; 224 int ans = 1; 225 for(int i = 0, j = 0; i < n; i = j){ 226 while(j < n && s[j] == s[i]) 227 j++; 228 if(s[i] == 'n' || s[i] == 'u') 229 ans = (ll) ans * fib[j - i] % mod; 230 } 231 cout << ans << '\n'; 232 } 233 ``` 234 235 [1245D - Shichikuji and Power Grid](/contest/1245/problem/D "Codeforces Round 597 (Div. 2)") 236 237 **Tutorial** 238 239 Tutorial is loading... 240 241 **Solution** 242 243 ``` 244 #include <vector> 245 #include <string> 246 #include <iostream> 247 #include <cstdio> 248 #include <algorithm> 249 #include <stack> 250 #include <queue> 251 #include <deque> 252 #include <set> 253 #include <map> 254 using namespace std; 255 256 int main() 257 { 258 ios_base::sync_with_stdio(0); 259 cin.tie(0); 260 261 int n; 262 cin >> n; 263 pair<int, int> pos[n]; 264 for (int i = 0; i != n; ++i) 265 cin >> pos[i].first >> pos[i].second; 266 int c[n]; 267 for (int i = 0; i != n; ++i) 268 cin >> c[i]; 269 int k[n]; 270 for (int i = 0; i != n; ++i) 271 cin >> k[i]; 272 273 long long ans = 0; 274 vector<int> power_plants; 275 vector<pair<int, int>> connections; 276 277 vector<bool> done(n); 278 vector<int> parent(n, -1); 279 for (int _n = n; _n--;) 280 { 281 int mi = 2000000000; 282 int u = -1; 283 for (int i = 0; i != n; ++i) 284 { 285 if (done[i]) 286 continue; 287 288 if (c[i] < mi) 289 { 290 mi = c[i]; 291 u = i; 292 } 293 } 294 295 ans += mi; 296 done[u] = 1; 297 if (parent[u] == -1) 298 power_plants.push_back(u); 299 else 300 connections.push_back(make_pair(min(parent[u], u), max(parent[u], u))); 301 302 for (int i = 0; i != n; ++i) 303 if (1LL * (k[u] + k[i]) * (abs(pos[u].first - pos[i].first) + abs(pos[u].second - pos[i].second)) < c[i]) 304 { 305 c[i] = (k[u] + k[i]) * (abs(pos[u].first - pos[i].first) + abs(pos[u].second - pos[i].second)); 306 parent[i] = u; 307 } 308 } 309 310 cout << ans << '\n'; 311 cout << power_plants.size() << '\n'; 312 sort(power_plants.begin(), power_plants.end()); 313 for (int x : power_plants) 314 cout << x + 1 << ' '; 315 cout << '\n'; 316 cout << connections.size() << '\n'; 317 for (pair<int, int> x : connections) 318 cout << x.first + 1 << ' ' << x.second + 1 << '\n'; 319 320 return 0; 321 } 322 ``` 323 324 **Solution (PikMike)** 325 326 ``` 327 #include <bits/stdc++.h> 328 329 using namespace std; 330 331 #define forn(i, n) for(int i = 0; i < int(n); i++) 332 333 int main(){ 334 int n; 335 scanf("%d", &n); 336 vector<int> x(n), y(n); 337 forn(i, n) 338 scanf("%d%d", &x[i], &y[i]); 339 vector<int> c(n), k(n); 340 forn(i, n) 341 scanf("%d", &c[i]); 342 forn(i, n) 343 scanf("%d", &k[i]); 344 345 ++n; 346 vector<int> p(n, -1); 347 vector<int> d(n, int(1e9)); 348 vector<bool> used(n); 349 350 forn(i, n - 1){ 351 d[i] = c[i]; 352 p[i] = n - 1; 353 } 354 used[n - 1] = true; 355 356 long long ans = 0; 357 vector<int> vv; 358 vector<pair<int, int>> ee; 359 360 forn(_, n - 1){ 361 int v = -1; 362 forn(i, n) if (!used[i] && (v == -1 || d[v] > d[i])) 363 v = i; 364 365 if (p[v] == n - 1) 366 vv.push_back(v + 1); 367 else 368 ee.push_back(make_pair(v + 1, p[v] + 1)); 369 ans += d[v]; 370 371 used[v] = true; 372 forn(i, n) if (!used[i]){ 373 long long dist = (k[v] + k[i]) * 1ll * (abs(x[v] - x[i]) + abs(y[v] - y[i])); 374 if (dist < d[i]){ 375 d[i] = dist; 376 p[i] = v; 377 } 378 } 379 } 380 381 printf("%lld\n", ans); 382 printf("%d\n", int(vv.size())); 383 for (auto it : vv) 384 printf("%d ", it); 385 puts(""); 386 printf("%d\n", int(ee.size())); 387 for (auto it : ee) 388 printf("%d %d\n", it.first, it.second); 389 } 390 ``` 391 392 [1245E - Hyakugoku and Ladders](/contest/1245/problem/E "Codeforces Round 597 (Div. 2)") 393 394 **Tutorial** 395 396 Tutorial is loading... 397 398 **Solution** 399 400 ``` 401 #include <bits/stdc++.h> 402 using namespace std; 403 404 int main() 405 { 406 ios_base::sync_with_stdio(0); 407 cin.tie(0); 408 409 int grid[10][10]; 410 for (int i = 0; i != 10; ++i) 411 for (int j = 0; j != 10; ++j) 412 cin >> grid[i][j]; 413 414 int flat[10][10]; 415 for (int i = 0; i != 10; ++i) 416 for (int j = 0; j != 10; ++j) 417 flat[i][j] = (9 - i) * 10 + ((i & 1) ? j : 9 - j); 418 419 int d = 1; 420 int x = 9; 421 int y = 0; 422 int arr[100]; 423 for (int i = 0; i != 100; ++i) 424 { 425 arr[i] = flat[x - grid[x][y]][y]; 426 427 if (y + d == -1 || y + d == 10) 428 { 429 d *= -1; 430 x--; 431 } 432 else 433 y += d; 434 } 435 436 double dp[100]; 437 dp[99] = 0; 438 for (int i = 98; i >= 0; --i) 439 { 440 dp[i] = 1; 441 442 int c = 6; 443 for (int r = 1; r <= 6; ++r) 444 { 445 if (i + r >= 100) 446 continue; 447 dp[i] += min(dp[i + r], dp[arr[i + r]]) / 6; 448 c--; 449 } 450 451 dp[i] = 6 * dp[i] / (6 - c); 452 } 453 454 cout << setprecision(10) << fixed << dp[0] << '\n'; 455 456 return 0; 457 } 458 ``` 459 460 [1245F - Daniel and Spring Cleaning](/contest/1245/problem/F "Codeforces Round 597 (Div. 2)") 461 462 **Tutorial** 463 464 Tutorial is loading... 465 466 **Solution** 467 468 ``` 469 #include<bits/stdc++.h> 470 using namespace std; 471 472 int f(int a, int b) 473 { 474 int ret = 0; 475 int zeroes = 0; 476 477 for (int i = 1; i <= b; i <<= 1) 478 { 479 if (b & i) 480 { 481 b ^= i; 482 483 if (!(a & b)) 484 ret += 1 << zeroes; 485 } 486 487 if (!(a & i)) 488 zeroes++; 489 } 490 491 return ret; 492 } 493 494 long long rec(int a, int b) 495 { 496 if (a == b) 497 return 0; 498 if (a == 0) 499 return 2 * b - 1 + rec(1, b); 500 501 long long ret = 0; 502 if (a & 1) 503 { 504 ret += 2 * (f(a, b) - f(a, a)); 505 a++; 506 } 507 if (b & 1) 508 { 509 ret += 2 * (f(b - 1, b) - f(b - 1, a)); 510 b--; 511 } 512 513 return ret + 3 * rec(a / 2, b / 2); 514 } 515 516 int main() 517 { 518 int t; 519 for (cin >> t; t--;) 520 { 521 int a, b; 522 cin >> a >> b; 523 cout << rec(a, b + 1) << '\n'; 524 } 525 526 return 0; 527 } 528 ```