2245.md (12428B)
1 Source: https://codeforces.com/blog/entry/155232 2 3 We hope you enjoyed the problems! 4 5 **Rate the contest!** 6 7 **Quality** 8 9 * Excellent contest 10 * Good contest 11 * Average contest 12 * Bad contest 13 * Horrible contest 14 15 **Difficulty** 16 17 * Trivial contest 18 * Easy contest 19 * Average contest 20 * Hard contest 21 * Impossible contest 22 23 [2245A - Кто сторожит свиносторожей?](/contest/2245/problem/A) 24 25 **Solution** 26 27 Tutorial is loading... 28 29 **Code** 30 31 ``` 32 for _ in range(int(input())): 33 n, k = map(int, input().split()) 34 s = input() 35 if k * 2 > n: 36 print(-1) 37 continue 38 ans = 0 39 for i in range(k): 40 ans += int(s[i] != 'R') + int(s[n - i - 1] != 'L') 41 print(ans) 42 ``` 43 44 **Rate the problem!** 45 46 **Quality** 47 48 * Excellent problem 49 * Good problem 50 * Average problem 51 * Bad problem 52 * Horrible problem 53 54 **Difficulty** 55 56 * Trivial problem 57 * Easy problem 58 * Average problem 59 * Hard problem 60 * Impossible problem 61 62 [2245B - Удалить и сконкатенировать](/contest/2245/problem/B) 63 64 **Solution** 65 66 Tutorial is loading... 67 68 **Code** 69 70 ``` 71 for _ in range(int(input())): 72 n, c = map(int, input().split()) 73 a = list(map(int, input().split())) 74 a.sort() 75 for i in range(n): 76 a[i] -= c 77 for i in range(n // 2): 78 a[i] = max(a[i], 0) 79 print(sum(a)) 80 ``` 81 82 **Rate the problem!** 83 84 **Quality** 85 86 * Excellent problem 87 * Good problem 88 * Average problem 89 * Bad problem 90 * Horrible problem 91 92 **Difficulty** 93 94 * Trivial problem 95 * Easy problem 96 * Average problem 97 * Hard problem 98 * Impossible problem 99 100 [2245C - MEXOR](/contest/2245/problem/C) 101 102 **Solution** 103 104 Tutorial is loading... 105 106 **Code** 107 108 ``` 109 for _ in range(int(input())): 110 n, k = map(int, input().split()) 111 if n == 1: 112 if k == 1: 113 print("YES") 114 print(0) 115 else: 116 print("NO") 117 continue 118 k ^= n 119 if k.bit_length() > (n - 1).bit_length(): 120 print("NO") 121 continue 122 s = list() 123 if 0 < k <= n - 1: 124 s.append(k) 125 elif k: 126 s.append(n - 1) 127 s.append((n - 1) ^ k) 128 s.append(0) 129 a = s[:] 130 for i in range(n): 131 if i not in s: 132 a.append(i) 133 print("YES") 134 print(*reversed(a)) 135 ``` 136 137 **Rate the problem!** 138 139 **Quality** 140 141 * Excellent problem 142 * Good problem 143 * Average problem 144 * Bad problem 145 * Horrible problem 146 147 **Difficulty** 148 149 * Trivial problem 150 * Easy problem 151 * Average problem 152 * Hard problem 153 * Impossible problem 154 155 [2245D1 - Построение массива (простая версия)](/contest/2245/problem/D1) 156 157 **Solution** 158 159 Tutorial is loading... 160 161 **Code** 162 163 ``` 164 #include <bits/stdc++.h> 165 166 void solve() { 167 int n, m; 168 std::cin >> n >> m; 169 std::vector b(n, std::vector<int>(n)); 170 while (m--) { 171 int o, i, j; 172 std::cin >> o >> i >> j; 173 i--; 174 j--; 175 b[i][j] = b[j][i] = o; 176 } 177 std::vector<std::vector<int>> g(n); 178 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { 179 if (b[i][i] == 1 && b[j][j] == 2) { 180 if (b[i][j] == 1) g[j].push_back(i); 181 else g[i].push_back(j); 182 } 183 } 184 std::vector<int> d(n), ans(n); 185 for (int u = 0; u < n; u++) for (auto v : g[u]) d[v]++; 186 int cnt = 0; 187 std::queue<int> q; 188 for (int u = 0; u < n; u++) if (!d[u]) q.push(u); 189 while (!q.empty()) { 190 int u = q.front(); 191 q.pop(); 192 if (b[u][u] == 1) ans[u] = ++cnt; 193 else ans[u] = -(++cnt); 194 for (auto v : g[u]) if (!--d[v]) q.push(v); 195 } 196 if (cnt == n) { 197 for (int i = 0; i < n; i++) for (int j = i; j < n; j++) { 198 if (b[i][j] == 1 && ans[i] + ans[j] < 0) return void(std::cout << "NO\n"); 199 if (b[i][j] == 2 && ans[i] + ans[j] >= 0) return void(std::cout << "NO\n"); 200 } 201 std::cout << "YES\n"; 202 for (int i = 0; i < n; i++) std::cout << ans[i] << " \n"[i + 1 == n]; 203 } else { 204 std::cout << "NO\n"; 205 } 206 } 207 208 int main() { 209 std::ios::sync_with_stdio(0); 210 std::cin.tie(0); 211 212 int t; 213 std::cin >> t; 214 while (t--) solve(); 215 } 216 ``` 217 218 **Rate the problem!** 219 220 **Quality** 221 222 * Excellent problem 223 * Good problem 224 * Average problem 225 * Bad problem 226 * Horrible problem 227 228 **Difficulty** 229 230 * Trivial problem 231 * Easy problem 232 * Average problem 233 * Hard problem 234 * Impossible problem 235 236 [2245D2 - Построение массива (сложная версия)](/contest/2245/problem/D2) 237 238 **Solution** 239 240 Tutorial is loading... 241 242 **Code** 243 244 ``` 245 #include <bits/stdc++.h> 246 247 void solve() { 248 int n, m; 249 std::cin >> n >> m; 250 std::vector d(2, std::vector<int>(n)); 251 std::vector<std::vector<std::pair<int, int>>> g(n); 252 while (m--) { 253 int o, i, j; 254 std::cin >> o >> i >> j; 255 o--; 256 i--; 257 j--; 258 g[i].emplace_back(j, o); 259 g[j].emplace_back(i, o); 260 d[o][i]++; 261 d[o][j]++; 262 } 263 std::queue<int> q; 264 std::vector<bool> vis(n); 265 for (int i = 0; i < n; i++) if (d[0][i] == 0 || d[1][i] == 0) q.push(i), vis[i] = true; 266 std::vector<std::pair<int, int>> t; 267 while (!q.empty()) { 268 int u = q.front(); 269 q.pop(); 270 if (d[0][u] == 0) t.emplace_back(u, -1); 271 else t.emplace_back(u, 1); 272 for (auto [v, o] : g[u]) if (!--d[o][v] && !vis[v]) { 273 vis[v] = true; 274 q.push(v); 275 } 276 } 277 if (t.size() < n) return void(std::cout << "NO\n"); 278 std::cout << "YES\n"; 279 std::vector<int> ans(n); 280 std::reverse(t.begin(), t.end()); 281 for (int i = 0; i < n; i++) ans[t[i].first] = (i + 1) * t[i].second; 282 for (int i = 0; i < n; i++) std::cout << ans[i] << " \n"[i + 1 == n]; 283 } 284 285 int main() { 286 std::ios::sync_with_stdio(0); 287 std::cin.tie(0); 288 289 int t; 290 std::cin >> t; 291 while (t--) solve(); 292 } 293 ``` 294 295 **Rate the problem!** 296 297 **Quality** 298 299 * Excellent problem 300 * Good problem 301 * Average problem 302 * Bad problem 303 * Horrible problem 304 305 **Difficulty** 306 307 * Trivial problem 308 * Easy problem 309 * Average problem 310 * Hard problem 311 * Impossible problem 312 313 [2245E - Том и Джерри](/contest/2245/problem/E) 314 315 **Solution** 316 317 Tutorial is loading... 318 319 **Code** 320 321 ``` 322 #include <bits/stdc++.h> 323 324 void solve() { 325 int n; 326 std::cin >> n; 327 std::vector<std::vector<int>> g(n); 328 for (int i = 0; i < n - 1; i++) { 329 int u, v; 330 std::cin >> u >> v; 331 u--; 332 v--; 333 g[u].push_back(v); 334 g[v].push_back(u); 335 } 336 std::vector<bool> vis(n); 337 long long ans = 0; 338 int c = 0; 339 auto dfs = [&](auto&& self, int u) -> void { 340 vis[u] = true; 341 for (auto v : g[u]) { 342 if (g[v].size() & 1) ans += c++; 343 else if (!vis[v]) self(self, v); 344 } 345 }; 346 for (int u = 0; u < n; u++) if (~g[u].size() & 1 && !vis[u]) { 347 c = 0; 348 dfs(dfs, u); 349 } 350 for (int u = 0; u < n; u++) for (auto v : g[u]) if (v > u) ans += g[u].size() & g[v].size() & 1; 351 std::cout << ans << "\n"; 352 } 353 354 int main() { 355 std::ios::sync_with_stdio(0); 356 std::cin.tie(0); 357 358 int t; 359 std::cin >> t; 360 while (t--) solve(); 361 } 362 ``` 363 364 **Rate the problem!** 365 366 **Quality** 367 368 * Excellent problem 369 * Good problem 370 * Average problem 371 * Bad problem 372 * Horrible problem 373 374 **Difficulty** 375 376 * Trivial problem 377 * Easy problem 378 * Average problem 379 * Hard problem 380 * Impossible problem 381 382 [2245F - Знакомо?](/contest/2245/problem/F) 383 384 **Solution** 385 386 Tutorial is loading... 387 388 **Code** 389 390 ``` 391 M = 998244353 392 N = 501 393 fac = [0] * N 394 fac[0] = 1 395 for i in range(1, N): 396 fac[i] = fac[i - 1] * i % M 397 inv = [0] * N 398 inv[-1] = pow(fac[-1], M - 2, M) 399 for i in range(N - 2, -1, -1): 400 inv[i] = inv[i + 1] * (i + 1) % M 401 def comb(n, k): 402 if k < 0 or k > n: 403 return 0 404 return fac[n] * inv[k] % M * inv[n - k] % M 405 406 for _ in range(int(input())): 407 n = int(input()) 408 a = list(map(int, input().split())) 409 if sum(max(0, v) for v in a) >= n: 410 print(0) 411 continue 412 a.append(-1) 413 f = [[[0] for _ in range(n)] for _ in range(n + 1)] 414 g = [[0] * n for _ in range(n + 1)] 415 for r in range(n): 416 if a[r + 1] != -1: 417 for l in range(n): 418 f[l][r] = [0] * (a[r + 1] + 1) 419 for i in range(1, n + 1): 420 f[i][i - 1][0] = 1 421 g[i][i - 1] = 1 422 def w(i, k): 423 if i == k: 424 return 1 if a[k] <= 0 else 0 425 else: 426 return f[i][k - 1][a[k]] if a[k] != -1 else g[i][k - 1] 427 for l in range(n - 1, -1, -1): 428 for r in range(l, n): 429 if a[r + 1] == -1: 430 for k in range(l, r + 1): 431 g[l][r] = (g[l][r] + comb(r - l, k - l) * w(l, k) % M * g[k + 1][r] % M) % M 432 else: 433 for c in range(1, a[r + 1] + 1): 434 for k in range(l, r + 1): 435 f[l][r][c] = (f[l][r][c] + comb(r - l, k - l) * w(l, k) % M * f[k + 1][r][c - 1] % M) % M 436 print(w(0, n)) 437 ``` 438 439 **Rate the problem!** 440 441 **Quality** 442 443 * Excellent problem 444 * Good problem 445 * Average problem 446 * Bad problem 447 * Horrible problem 448 449 **Difficulty** 450 451 * Trivial problem 452 * Easy problem 453 * Average problem 454 * Hard problem 455 * Impossible problem 456 457 [2245G - NPC-челлендж](/contest/2245/problem/G) 458 459 **Solution** 460 461 Tutorial is loading... 462 463 **Code** 464 465 ``` 466 #include <bits/stdc++.h> 467 468 std::string query(const std::vector<int>& a) { 469 std::cout << "? " << a.size(); 470 for (auto v : a) std::cout << " " << v + 1; 471 std::cout << std::endl; 472 std::string s; 473 std::cin >> s; 474 return s; 475 } 476 477 std::vector<int> work(const std::vector<int>& a, const std::vector<int>& b) { 478 if (a.empty() || b.empty()) return {}; 479 std::vector<int> s; 480 for (auto v : a) s.push_back(v); 481 for (auto v : b) s.push_back(v); 482 std::string t = query(s); 483 std::vector<int> r; 484 for (int i = 0; i < b.size(); i++) if (t[i + a.size()] == '0') r.push_back(b[i]); 485 return r; 486 } 487 488 void solve() { 489 int n; 490 std::cin >> n; 491 std::vector<std::vector<int>> g(n); 492 auto find = [&](auto&& self, std::vector<int> a, std::vector<int> b) -> void { 493 if (a.empty() || b.empty()) return; 494 if (a.size() == 1) { 495 for (auto v : b) g[v].push_back(a[0]), g[a[0]].push_back(v); 496 return; 497 } 498 int m = a.size() / 2; 499 std::vector a1(a.begin(), a.begin() + m), a2(a.begin() + m, a.end()); 500 auto p1 = work(a1, b); 501 std::set<int> vis(p1.begin(), p1.end()); 502 std::vector<int> nb, p2; 503 for (auto v : b) { 504 if (vis.count(v)) nb.push_back(v); 505 else p2.push_back(v); 506 } 507 self(self, a1, p1); 508 for (auto v : work(a2, nb)) p2.push_back(v); 509 self(self, a2, p2); 510 }; 511 auto dfs = [&](auto&& self, std::vector<int> a) -> void { 512 if (a.size() <= 1) return; 513 std::string t = query(a); 514 std::vector<int> p1, p2; 515 for (int i = 0; i < a.size(); i++) { 516 if (t[i] == '0') p2.push_back(a[i]); 517 else p1.push_back(a[i]); 518 } 519 self(self, p2); 520 std::vector<int> col(n, -1); 521 std::vector<std::vector<int>> b(2); 522 for (auto w : p2) if (col[w] == -1) { 523 std::queue<int> q; 524 q.push(w); 525 col[w] = 0; 526 while (!q.empty()) { 527 int u = q.front(); 528 q.pop(); 529 b[col[u]].push_back(u); 530 for (auto v : g[u]) if (col[v] == -1) { 531 col[v] = col[u] ^ 1; 532 q.push(v); 533 } 534 } 535 } 536 for (int i = 0; i < 2; i++) { 537 find(find, b[i], work(b[i], p1)); 538 } 539 }; 540 std::vector<int> a(n); 541 std::iota(a.begin(), a.end(), 0); 542 dfs(dfs, a); 543 std::cout << "!" << std::endl; 544 for (int u = 0; u < n; u++) for (auto v : g[u]) if (v > u) std::cout << u + 1 << " " << v + 1 << std::endl; 545 } 546 547 int main() { 548 std::ios::sync_with_stdio(0); 549 std::cin.tie(0); 550 551 int t; 552 std::cin >> t; 553 while (t--) solve(); 554 } 555 ``` 556 557 **Rate the problem!** 558 559 **Quality** 560 561 * Excellent problem 562 * Good problem 563 * Average problem 564 * Bad problem 565 * Horrible problem 566 567 **Difficulty** 568 569 * Trivial problem 570 * Easy problem 571 * Average problem 572 * Hard problem 573 * Impossible problem 574 575 [2245H - Видимые соединения](/contest/2245/problem/H) 576 577 **Solution** 578 579 Tutorial will be added after the first official (human) solve. 580 581 **Code** 582 583 **Rate the problem!** 584 585 **Quality** 586 587 * Excellent problem 588 * Good problem 589 * Average problem 590 * Bad problem 591 * Horrible problem 592 593 **Difficulty** 594 595 * Trivial problem 596 * Easy problem 597 * Average problem 598 * Hard problem 599 * Impossible problem