1118.md (9156B)
1 Source: https://codeforces.com/blog/entry/65396 2 3 [1118A - Water Buying](/contest/1118/problem/A "Codeforces Round 540 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 #ifdef _DEBUG 20 freopen("input.txt", "r", stdin); 21 // freopen("output.txt", "w", stdout); 22 #endif 23 24 int q; 25 cin >> q; 26 27 for (int i = 0; i < q; ++i) { 28 long long n; 29 int a, b; 30 cin >> n >> a >> b; 31 cout << (n / 2) * min(2 * a, b) + (n % 2) * a << endl; 32 } 33 34 return 0; 35 } 36 ``` 37 38 [1118B - Tanya and Candies](/contest/1118/problem/B "Codeforces Round 540 (Div. 3)") 39 40 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 41 42 **Tutorial** 43 44 Tutorial is loading... 45 46 **Solution** 47 48 ``` 49 #include <bits/stdc++.h> 50 51 using namespace std; 52 53 int main() { 54 #ifdef _DEBUG 55 freopen("input.txt", "r", stdin); 56 // freopen("output.txt", "w", stdout); 57 #endif 58 59 int n; 60 cin >> n; 61 62 vector<int> a(n); 63 64 int ePref = 0, oPref = 0, eSuf = 0, oSuf = 0; 65 for (int i = 0; i < n; ++i) { 66 cin >> a[i]; 67 if (i & 1) eSuf += a[i]; 68 else oSuf += a[i]; 69 } 70 71 int ans = 0; 72 for (int i = 0; i < n; ++i) { 73 if (i & 1) eSuf -= a[i]; 74 else oSuf -= a[i]; 75 if (ePref + oSuf == oPref + eSuf) { 76 ++ans; 77 } 78 if (i & 1) ePref += a[i]; 79 else oPref += a[i]; 80 } 81 82 cout << ans << endl; 83 84 return 0; 85 } 86 ``` 87 88 [1118C - Palindromic Matrix](/contest/1118/problem/C "Codeforces Round 540 (Div. 3)") 89 90 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 91 92 I should mention [this](//codeforces.com/blog/entry/65383) blog because it is amazing! This is a tutorial of this problem from [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"). 93 94 **Tutorial** 95 96 Tutorial is loading... 97 98 **Solution** 99 100 ``` 101 #include <bits/stdc++.h> 102 103 #define forn(i, n) for (int i = 0; i < int(n); i++) 104 105 using namespace std; 106 107 typedef pair<int, int> pt; 108 109 const int N = 1000 + 7; 110 111 int cnt[N]; 112 int a[20][20]; 113 114 int main() { 115 int n; 116 scanf("%d", &n); 117 forn(i, n * n){ 118 int x; 119 scanf("%d", &x); 120 ++cnt[x]; 121 } 122 123 vector<pair<int, pt>> cells; 124 forn(i, (n + 1) / 2) forn(j, (n + 1) / 2){ 125 if (i != n - i - 1 && j != n - j - 1) 126 cells.push_back({4, {i, j}}); 127 else if ((i != n - i - 1) ^ (j != n - j - 1)) 128 cells.push_back({2, {i, j}}); 129 else 130 cells.push_back({1, {i, j}}); 131 } 132 133 for (auto cur : {4, 2, 1}){ 134 int lst = 1; 135 for (auto it : cells){ 136 if (it.first != cur) continue; 137 int i = it.second.first; 138 int j = it.second.second; 139 while (lst < N && cnt[lst] < cur) 140 ++lst; 141 if (lst == N){ 142 puts("NO"); 143 return 0; 144 } 145 a[i][j] = a[n - i - 1][j] = a[i][n - j - 1] = a[n - i - 1][n - j - 1] = lst; 146 cnt[lst] -= cur; 147 } 148 } 149 150 puts("YES"); 151 forn(i, n){ 152 forn(j, n) 153 printf("%d ", a[i][j]); 154 puts(""); 155 } 156 return 0; 157 } 158 ``` 159 160 [1118D1 - Coffee and Coursework (Easy version)](/contest/1118/problem/D1 "Codeforces Round 540 (Div. 3)") 161 162 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 163 164 **Tutorial** 165 166 Tutorial is loading... 167 168 **Solution** 169 170 ``` 171 #include <bits/stdc++.h> 172 173 using namespace std; 174 175 int main() { 176 #ifdef _DEBUG 177 freopen("input.txt", "r", stdin); 178 // freopen("output.txt", "w", stdout); 179 #endif 180 181 int n, m; 182 cin >> n >> m; 183 184 vector<int> a(n); 185 for (int i = 0; i < n; ++i) { 186 cin >> a[i]; 187 } 188 sort(a.rbegin(), a.rend()); 189 190 for (int i = 1; i <= n; ++i) { 191 int sum = 0; 192 for (int j = 0; j < n; ++j) { 193 sum += max(a[j] - j / i, 0); 194 } 195 if (sum >= m) { 196 cout << i << endl; 197 return 0; 198 } 199 } 200 201 cout << -1 << endl; 202 203 return 0; 204 } 205 ``` 206 207 [1118D2 - Coffee and Coursework (Hard Version)](/contest/1118/problem/D2 "Codeforces Round 540 (Div. 3)") 208 209 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 210 211 **Tutorial** 212 213 Tutorial is loading... 214 215 **Solution** 216 217 ``` 218 #include <bits/stdc++.h> 219 220 using namespace std; 221 222 int n, m; 223 vector<int> a; 224 225 bool can(int i) { 226 long long sum = 0; // there can be a bug 227 for (int j = 0; j < n; ++j) { 228 sum += max(a[j] - j / i, 0); 229 } 230 return sum >= m; 231 } 232 233 int main() { 234 #ifdef _DEBUG 235 freopen("input.txt", "r", stdin); 236 // freopen("output.txt", "w", stdout); 237 #endif 238 239 cin >> n >> m; 240 241 a = vector<int>(n); 242 for (int i = 0; i < n; ++i) { 243 cin >> a[i]; 244 } 245 sort(a.rbegin(), a.rend()); 246 247 int l = 1, r = n; 248 while (r - l > 1) { 249 int mid = (l + r) >> 1; 250 if (can(mid)) r = mid; 251 else l = mid; 252 } 253 254 if (can(l)) cout << l << endl; 255 else if (can(r)) cout << r << endl; 256 else cout << -1 << endl; 257 258 return 0; 259 } 260 ``` 261 262 [1118E - Yet Another Ball Problem](/contest/1118/problem/E "Codeforces Round 540 (Div. 3)") 263 264 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 265 266 **Tutorial** 267 268 Tutorial is loading... 269 270 **Solution** 271 272 ``` 273 #include <bits/stdc++.h> 274 275 using namespace std; 276 277 int main() { 278 #ifdef _DEBUG 279 freopen("input.txt", "r", stdin); 280 // freopen("output.txt", "w", stdout); 281 #endif 282 283 int n, k; 284 cin >> n >> k; 285 286 if (n > k * 1ll * (k - 1)) { 287 cout << "NO" << endl; 288 } else { 289 cout << "YES" << endl; 290 int cur = 0; 291 for (int i = 0; i < n; ++i) { 292 cur += (i % k == 0); 293 cout << i % k + 1 << " " << (cur + i % k) % k + 1 << endl; 294 } 295 } 296 297 return 0; 298 } 299 ``` 300 301 [1118F1 - Tree Cutting (Easy Version)](/contest/1118/problem/F1 "Codeforces Round 540 (Div. 3)") 302 303 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 304 305 **Tutorial** 306 307 Tutorial is loading... 308 309 **Solution** 310 311 ``` 312 #include <bits/stdc++.h> 313 314 #define forn(i, n) for (int i = 0; i < int(n); i++) 315 316 using namespace std; 317 318 const int N = 300 * 1000 + 13; 319 320 int n; 321 int a[N]; 322 vector<int> g[N]; 323 int red, blue; 324 int ans; 325 326 pair<int, int> dfs(int v, int p = -1){ 327 int r = (a[v] == 1), b = (a[v] == 2); 328 for (auto u : g[v]) if (u != p){ 329 auto tmp = dfs(u, v); 330 ans += (tmp.first == red && tmp.second == 0); 331 ans += (tmp.first == 0 && tmp.second == blue); 332 r += tmp.first; 333 b += tmp.second; 334 } 335 return make_pair(r, b); 336 } 337 338 int main() { 339 int n; 340 scanf("%d", &n); 341 342 forn(i, n){ 343 scanf("%d", &a[i]); 344 red += (a[i] == 1); 345 blue += (a[i] == 2); 346 } 347 348 forn(i, n - 1){ 349 int v, u; 350 scanf("%d%d", &v, &u); 351 --v, --u; 352 g[v].push_back(u); 353 g[u].push_back(v); 354 } 355 356 ans = 0; 357 dfs(0); 358 printf("%d\n", ans); 359 return 0; 360 } 361 ``` 362 363 [1118F2 - Tree Cutting (Hard Version)](/contest/1118/problem/F2 "Codeforces Round 540 (Div. 3)") 364 365 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 366 367 **Tutorial** 368 369 Tutorial is loading... 370 371 **Solution** 372 373 ``` 374 #include <bits/stdc++.h> 375 376 #define forn(i, n) for (int i = 0; i < int(n); i++) 377 378 using namespace std; 379 380 const int N = 300 * 1000 + 13; 381 const int LOGN = 19; 382 const int MOD = 998244353; 383 384 int add(int a, int b){ 385 a += b; 386 if (a >= MOD) 387 a -= MOD; 388 if (a < 0) 389 a += MOD; 390 return a; 391 } 392 393 int mul(int a, int b){ 394 return a * 1ll * b % MOD; 395 } 396 397 int a[N]; 398 vector<int> g[N]; 399 int up[N][LOGN]; 400 int d[N]; 401 402 void init(int v, int p = -1){ 403 for (auto u : g[v]) if (u != p){ 404 up[u][0] = v; 405 for (int i = 1; i < LOGN; ++i) 406 up[u][i] = up[up[u][i - 1]][i - 1]; 407 d[u] = d[v] + 1; 408 init(u, v); 409 } 410 } 411 412 int lca(int v, int u){ 413 if (d[v] < d[u]) swap(v, u); 414 for (int i = LOGN - 1; i >= 0; --i) 415 if (d[up[v][i]] >= d[u]) 416 v = up[v][i]; 417 if (v == u) return v; 418 for (int i = LOGN - 1; i >= 0; --i) 419 if (up[v][i] != up[u][i]){ 420 v = up[v][i]; 421 u = up[u][i]; 422 } 423 return up[v][0]; 424 } 425 426 int l[N]; 427 int dp[N][2]; 428 429 int dfs(int v, int p = -1){ 430 vector<pair<int, int>> cur; 431 for (auto u : g[v]) if (u != p){ 432 int c = dfs(u, v); 433 if (c != 0) 434 cur.push_back(make_pair(c, u)); 435 } 436 437 vector<int> vals; 438 forn(i, cur.size()) if (cur[i].first > 0) 439 vals.push_back(cur[i].first); 440 441 sort(vals.begin(), vals.end()); 442 vals.resize(unique(vals.begin(), vals.end()) - vals.begin()); 443 444 if (int(vals.size()) > 1){ 445 puts("0"); 446 exit(0); 447 } 448 449 if (a[v] != 0 && !vals.empty() && vals[0] != a[v]){ 450 puts("0"); 451 exit(0); 452 } 453 454 if (a[v] == 0 && cur.empty()) 455 return 0; 456 457 if (a[v] == 0 && vals.empty()){ 458 vector<int> pr(1, 1), su(1, 1); 459 forn(i, cur.size()) 460 pr.push_back(mul(pr.back(), add(dp[cur[i].second][0], dp[cur[i].second][1]))); 461 for (int i = int(cur.size()) - 1; i >= 0; --i) 462 su.push_back(mul(su.back(), add(dp[cur[i].second][0], dp[cur[i].second][1]))); 463 reverse(su.begin(), su.end()); 464 dp[v][1] = 0; 465 forn(i, cur.size()) 466 dp[v][1] = add(dp[v][1], mul(mul(pr[i], su[i + 1]), dp[cur[i].second][1])); 467 dp[v][0] = add(dp[v][0], pr[cur.size()]); 468 return -1; 469 } 470 471 dp[v][1] = 1; 472 for (auto it : cur){ 473 if (it.first == -1) 474 dp[v][1] = mul(dp[v][1], add(dp[it.second][0], dp[it.second][1])); 475 else 476 dp[v][1] = mul(dp[v][1], dp[it.second][1]); 477 } 478 479 if (a[v] == 0) 480 return vals[0]; 481 482 return (l[a[v]] == v ? -1 : a[v]); 483 } 484 485 int main() { 486 int n, k; 487 scanf("%d%d", &n, &k); 488 489 forn(i, n) 490 scanf("%d", &a[i]); 491 492 forn(i, n - 1){ 493 int v, u; 494 scanf("%d%d", &v, &u); 495 --v, --u; 496 g[v].push_back(u); 497 g[u].push_back(v); 498 } 499 500 init(0); 501 502 memset(l, -1, sizeof(l)); 503 forn(i, n) if (a[i] != 0) 504 l[a[i]] = (l[a[i]] == -1 ? i : lca(l[a[i]], i)); 505 506 for (int i = 1; i <= k; ++i){ 507 if (a[l[i]] != 0 && a[l[i]] != i){ 508 puts("0"); 509 exit(0); 510 } 511 a[l[i]] = i; 512 } 513 514 dfs(0); 515 516 printf("%d\n", dp[0][1]); 517 return 0; 518 } 519 ```