1846.md (10712B)
1 Source: https://codeforces.com/blog/entry/118044 2 3 [1846A - Rudolph and Cut the Rope](/contest/1846/problem/A "Codeforces Round 883 (Div. 3)") 4 5 Author: [Sasha0738](/profile/Sasha0738 "Expert Sasha0738") 6 7 **Hint 1** 8 9 What if the nail with the rope is the only one? 10 11 **Hint 2** 12 13 How long should be rope to reach the ground? 14 15 **Tutorial** 16 17 Tutorial is loading... 18 19 **Solution** 20 21 ``` 22 #include <iostream> 23 24 using namespace std; 25 26 int main() { 27 int test_cases; 28 cin >> test_cases; 29 30 for (int test_case = 0; test_case < test_cases; test_case++) { 31 int n; 32 cin >> n; 33 int ans = 0; 34 for (int i = 0; i < n; i++) { 35 int a, b; 36 cin >> a >> b; 37 if (a > b) 38 ans++; 39 } 40 cout << ans << endl; 41 } 42 43 return 0; 44 } 45 ``` 46 47 **Rate the problem** 48 49 * Didn't solve 50 * Good task 51 * Average task 52 * Bad task 53 54 [1846B - Rudolph and Tic-Tac-Toe](/contest/1846/problem/B "Codeforces Round 883 (Div. 3)") 55 56 Author: [Sasha0738](/profile/Sasha0738 "Expert Sasha0738") 57 58 **Hint 1** 59 60 What is the win condition to be checked? 61 62 **Tutorial** 63 64 Tutorial is loading... 65 66 **Solution** 67 68 ``` 69 #include <iostream> 70 #include <vector> 71 #include <string> 72 73 using namespace std; 74 75 int main() { 76 int test_cases; 77 cin >> test_cases; 78 for (int test_case = 0; test_case < test_cases; test_case++) { 79 vector<string> v(3); 80 for (int i = 0; i < 3; i++) 81 cin >> v[i]; 82 string ans = "DRAW"; 83 for(int i = 0; i < 3; i++) { 84 if (v[i][0] == v[i][1] && v[i][1] == v[i][2] && v[i][0] != '.') 85 ans=v[i][0]; 86 } 87 for (int i = 0; i < 3; i++) { 88 if (v[0][i] == v[1][i] && v[1][i] == v[2][i] && v[0][i] != '.') 89 ans=v[0][i]; 90 } 91 if (v[0][0] == v[1][1] && v[1][1] == v[2][2] && v[0][0] != '.') 92 ans=v[0][0]; 93 if (v[0][2] == v[1][1] && v[1][1] == v[2][0] && v[0][2] != '.') 94 ans=v[0][2]; 95 cout << ans << endl; 96 } 97 return 0; 98 } 99 ``` 100 101 **Rate the problem** 102 103 * Didn't solve 104 * Good task 105 * Average task 106 * Bad task 107 108 [1846C - Rudolf and the Another Competition](/contest/1846/problem/C "Codeforces Round 883 (Div. 3)") 109 110 Author: [vladmart](/profile/vladmart "Master vladmart") 111 112 **Hint 1** 113 114 What is the optimal order of task solving? 115 116 **Hint 2** 117 118 t1 ≤ t2 ≤ t3 ≤ ... ≤ tm 119 120 **Tutorial** 121 122 Tutorial is loading... 123 124 **Solution** 125 126 ``` 127 #include <bits/stdc++.h> 128 129 #define int long long 130 131 using namespace std; 132 133 signed main() { 134 ios::sync_with_stdio(false); 135 cin.tie(nullptr); 136 cout.tie(nullptr); 137 int ttt; 138 cin >> ttt; 139 while(ttt--){ 140 int n, m, h; 141 cin >> n >> m >> h; 142 pair<int, long long> rud; 143 int ans = 1; 144 for(int i = 0; i < n; i++){ 145 vector<int> cur(m); 146 for(int j = 0; j < m; j++){ 147 cin >> cur[j]; 148 } 149 std::sort(cur.begin(), cur.end()); 150 int task_cnt = 0; 151 long long penalty = 0, sum = 0; 152 for(int j = 0; j < m; j++){ 153 if (sum + cur[j] > h) break; 154 sum += cur[j]; 155 penalty += sum; 156 task_cnt++; 157 } 158 if (i){ 159 if (make_pair(-task_cnt, penalty) < rud) ans++; 160 } else rud = {-task_cnt, penalty}; 161 } 162 cout << ans << '\n'; 163 } 164 return 0; 165 } 166 ``` 167 168 **Rate the problem** 169 170 * Didn't solve 171 * Good task 172 * Average task 173 * Bad task 174 175 [1846D - Rudolph and Christmas Tree](/contest/1846/problem/D "Codeforces Round 883 (Div. 3)") 176 177 Author: [vladmart](/profile/vladmart "Master vladmart") 178 179 **Hint 1** 180 181 Consider all the triangles in order from bottom to top. 182 183 **Hint 2** 184 185 What if the current triangle intersects with the next one? 186 187 **Hint 3** 188 189 Trapezoid 190 191 **Tutorial** 192 193 Tutorial is loading... 194 195 **Solution** 196 197 ``` 198 #include <bits/stdc++.h> 199 200 using namespace std; 201 202 int main() { 203 ios::sync_with_stdio(false); 204 cin.tie(nullptr); 205 cout.tie(nullptr); 206 cout.precision(10); cout.setf(ios::fixed); 207 int ttt; 208 cin >> ttt; 209 while (ttt--) { 210 int n, d, h; 211 cin >> n >> d >> h; 212 vector<int> y(n); 213 for(int i = 0; i < n; i++){ 214 cin >> y[i]; 215 } 216 long double ans = (long double)d * h / 2.0; 217 for (int i = 0; i + 1 < n; ++i) { 218 if (y[i + 1] >= y[i] + h) ans += (long double)d * h / 2.0; 219 else{ 220 long double d2 = (long double)d * (y[i] + h - y[i + 1]) / h; 221 long double nh = y[i + 1] - y[i]; 222 ans += (d + d2) / 2.0 * nh; 223 } 224 } 225 cout << ans << '\n'; 226 } 227 return 0; 228 } 229 ``` 230 231 **Rate the problem** 232 233 * Didn't solve 234 * Good task 235 * Average task 236 * Bad task 237 238 [1846E1 - Rudolf and Snowflakes (simple version)](/contest/1846/problem/E1 "Codeforces Round 883 (Div. 3)") 239 240 Author: [natalina](/profile/natalina "Expert natalina") 241 242 **Hint 1** 243 244 1 + k + k2 + k3 + ... + kp 245 246 **Hint 2** 247 248 What maximum value of k can be reached for the current constrains on n? 249 250 **Hint 3** 251 252 Can we precalculate for each n if there is appropriate k? 253 254 **Tutorial** 255 256 Tutorial is loading... 257 258 **Solution** 259 260 ``` 261 #include<bits/stdc++.h> 262 263 using namespace std; 264 265 using LL = long long; 266 267 set<long long> nums; 268 269 int main() { 270 271 for (long long k = 2; k <= 1000; ++k) { 272 long long val = 1 + k; 273 long long p = k*k; 274 for (int cnt = 2; cnt <= 20; ++cnt) { 275 val += p; 276 if (val > 1e6) break; 277 nums.insert(val); 278 p *= k; 279 } 280 } 281 282 int _ = 0, __ = 1; 283 cin >> __; 284 285 for (int _ = 0; _ < __; ++_) { 286 long long n; 287 cin >> n; 288 289 290 if (nums.count(n)) cout << "YES" << endl; 291 else cout << "NO" << endl; 292 293 } 294 295 return 0; 296 } 297 ``` 298 299 **Rate the problem** 300 301 * Didn't solve 302 * Good task 303 * Average task 304 * Bad task 305 306 [1846E2 - Rudolf and Snowflakes (hard version)](/contest/1846/problem/E2 "Codeforces Round 883 (Div. 3)") 307 308 Author: [natalina](/profile/natalina "Expert natalina") 309 310 **Hint 1** 311 312 1 + k + k2 + k3 + ... + kp 313 314 **Hint 2** 315 316 What maximum value of k can be reached for the current constrains on n? 317 318 **Hint 3** 319 320 Can we precalculate for some n and snowflakes with 4 or more levels if there is appropriate k? 321 322 **Hint 4** 323 324 How can we check snowflakes with 3 levels separately? 325 326 **Tutorial** 327 328 Tutorial is loading... 329 330 **Solution** 331 332 ``` 333 #include<bits/stdc++.h> 334 335 using namespace std; 336 337 using LL = long long; 338 339 set<long long> nums; 340 341 int main() { 342 343 for (long long k = 2; k <= 1000000; ++k) { 344 long long val = 1 + k; 345 long long p = k*k; 346 for (int cnt = 3; cnt <= 63; ++cnt) { 347 val += p; 348 if (val > 1e18) break; 349 nums.insert(val); 350 if (p > (long long)(1e18) / k) break; 351 p *= k; 352 } 353 } 354 355 int _ = 0, __ = 1; 356 cin >> __; 357 358 for (int _ = 0; _ < __; ++_) { 359 long long n; 360 cin >> n; 361 if (n < 3) 362 { 363 cout << "NO" << endl; 364 continue; 365 } 366 long long d = 4*n - 3; 367 long long sq = sqrt(d); 368 long long sqd = -1; 369 for (long long i = max(0ll, sq - 5); i <= sq + 5; ++i) { 370 if (i*i == d) 371 { 372 sqd = i; 373 break; 374 } 375 } 376 if (sqd != -1 && (sqd - 1) % 2 == 0 && (sqd - 1) / 2 > 1) 377 { 378 cout << "YES" << endl; 379 continue; 380 } 381 382 if (nums.count(n)) cout << "YES" << endl; 383 else cout << "NO" << endl; 384 385 } 386 387 return 0; 388 } 389 ``` 390 391 **Rate the problem** 392 393 * Didn't solve 394 * Good task 395 * Average task 396 * Bad task 397 398 [1846F - Rudolph and Mimic](/contest/1846/problem/F "Codeforces Round 883 (Div. 3)") 399 400 Author: [Sasha0738](/profile/Sasha0738 "Expert Sasha0738") 401 402 **Hint 1** 403 404 How number of objects of each type will change after the mimic transformation? 405 406 **Hint 2** 407 408 What if all the current objects have the same value? 409 410 **Tutorial** 411 412 Tutorial is loading... 413 414 **Solution** 415 416 ``` 417 #include <iostream> 418 #include <vector> 419 #include <map> 420 421 using namespace std; 422 423 int main() { 424 int test_cases; 425 cin >> test_cases; 426 for (int test_case = 0; test_case < test_cases; test_case++) { 427 int n; 428 cin >> n; 429 vector<int> v(n); 430 map<int, int> m; 431 for (int i = 0; i < n; i++) { 432 cin >> v[i]; 433 m[v[i]]++; 434 } 435 vector<int> elements_to_erase; 436 int ans; 437 for (int i = 0; i < 5; i++) { 438 if (v.size() - elements_to_erase.size() == 1) { 439 cout << "! " << ans << endl; 440 break; 441 } 442 cout << "- " << elements_to_erase.size() << " "; 443 for (int j = 0; j < elements_to_erase.size(); j++) { 444 cout << elements_to_erase[j] << " "; 445 } 446 cout << endl; 447 vector<int> new_v; 448 map<int, int> new_m; 449 for (int j = 0; j < v.size() - elements_to_erase.size(); j++) { 450 int x; 451 cin >> x; 452 new_v.push_back(x); 453 new_m[x]++; 454 } 455 elements_to_erase.clear(); 456 int tm = -1; 457 for (auto& k : new_m) { 458 if (k.second > m[k.first]) { 459 tm = k.first; 460 } 461 } 462 if (tm != -1) { 463 for (int j = 0; j < new_v.size(); j++) { 464 if (new_v[j] != tm) 465 elements_to_erase.push_back(j + 1); 466 else 467 ans = j + 1; 468 } 469 m.clear(); 470 m[tm] = new_m[tm]; 471 } 472 v = new_v; 473 } 474 } 475 return 0; 476 } 477 ``` 478 479 **Rate the problem** 480 481 * Didn't solve 482 * Good task 483 * Average task 484 * Bad task 485 486 [1846G - Rudolf and CodeVid-23](/contest/1846/problem/G "Codeforces Round 883 (Div. 3)") 487 488 Author: [vladmart](/profile/vladmart "Master vladmart") 489 490 **Hint 1** 491 492 Bitmasks 493 494 **Hint 2** 495 496 Weighted graph 497 498 **Hint 3** 499 500 Dijkstra's algorithm 501 502 **Tutorial** 503 504 Tutorial is loading... 505 506 **Solution** 507 508 ``` 509 #include <bits/stdc++.h> 510 511 using namespace std; 512 513 int main() { 514 ios::sync_with_stdio(false); 515 cin.tie(nullptr); 516 cout.tie(nullptr); 517 int ttt; 518 cin >> ttt; 519 while (ttt--) { 520 int n, m; 521 cin >> n >> m; 522 bitset<10> tmp; 523 cin >> tmp; 524 int s = (int) tmp.to_ulong(); 525 vector<pair<pair<int, int>, int>> edges(m); 526 for (int i = 0; i < m; i++) { 527 cin >> edges[i].second; 528 cin >> tmp; 529 edges[i].first.first = ((1 << n) - 1) ^ (int) tmp.to_ulong(); 530 cin >> tmp; 531 edges[i].first.second = (int) tmp.to_ulong(); 532 } 533 vector<int> dist(1 << n, INT_MAX); 534 dist[s] = 0; 535 set<pair<int, int>> q = {{0, s}}; 536 while (!q.empty()) { 537 auto [d, v] = *q.begin(); 538 q.erase(q.begin()); 539 for (int i = 0; i < m; i++) { 540 int to = v & edges[i].first.first; 541 to |= edges[i].first.second; 542 if (dist[to] > d + edges[i].second) { 543 q.erase({dist[to], to}); 544 dist[to] = d + edges[i].second; 545 q.insert({dist[to], to}); 546 } 547 } 548 } 549 if (dist[0] == INT_MAX) dist[0] = -1; 550 cout << dist[0] << '\n'; 551 } 552 return 0; 553 } 554 ``` 555 556 **Rate the problem** 557 558 * Didn't solve 559 * Good task 560 * Average task 561 * Bad task