2238.md (8260B)
1 Source: https://codeforces.com/blog/entry/154829 2 3 Thank you for participating in the round! We hope you enjoyed the problems. We worked very hard while preparing this contest :) 4 5 Hints for the problems will be published a bit later. 6 7 **Rate the round** 8 9 Excellent round 10 11 Good round 12 13 Average round 14 15 Bad round 16 17 Awful round 18 19 [2238A - Another Puzzle from Papyrus](/contest/2238/problem/A "Codeforces Round 1106 (Div. 2)") 20 21 Idea: [Friendiks](/profile/Friendiks "Grandmaster Friendiks") 22 23 **Solution** 24 25 Tutorial is loading... 26 27 **Code** 28 29 ``` 30 #include<bits/stdc++.h> 31 32 using namespace std; 33 34 int main() { 35 int t; 36 cin >> t; 37 while (t--) { 38 int n, C; 39 cin >> n >> C; 40 int ans = 0; 41 vector<int> a(n), b(n); 42 for (int i = 0; i < n; ++i) cin >> a[i]; 43 for (int i = 0; i < n; ++i) cin >> b[i]; 44 bool needReorder = false; 45 for (int i = 0; i < n; ++i) { 46 if (a[i] < b[i]) needReorder = true; 47 ans += a[i]; 48 ans -= b[i]; 49 } 50 if (needReorder) { 51 needReorder = false; 52 ans += C; 53 sort(a.begin(), a.end()); 54 sort(b.begin(), b.end()); 55 for (int i = 0; i < n; ++i) { 56 if (a[i] < b[i]) { 57 needReorder = true; 58 } 59 } 60 } 61 if (needReorder) cout << "-1\n"; 62 else cout << ans << "\n"; 63 } 64 } 65 ``` 66 67 **Rate the problem** 68 69 Excellent problem 70 71 Good problem 72 73 Average problem 74 75 Bad problem 76 77 Awful problem 78 79 [2238B - Crimson Triples](/contest/2238/problem/B "Codeforces Round 1106 (Div. 2)") 80 81 Idea: [KotlechkovEgor](/profile/KotlechkovEgor "Master KotlechkovEgor") 82 83 **Solution** 84 85 Tutorial is loading... 86 87 **Code** 88 89 ``` 90 #include <bits/stdc++.h> 91 92 using namespace std; 93 94 void solve() { 95 int n; 96 cin >> n; 97 long long an = 0; 98 for (int b = 1; b <= n; b++) { 99 an += 1ll * (n / b) * (n / b); 100 } 101 cout << an << '\n'; 102 } 103 104 signed main() { 105 signed t_ = 1; 106 cin >> t_; 107 while (t_--) { 108 solve(); 109 } 110 } 111 ``` 112 113 **Rate the problem** 114 115 Excellent problem 116 117 Good problem 118 119 Average problem 120 121 Bad problem 122 123 Awful problem 124 125 [2238C - Village Guilds](/contest/2238/problem/C "Codeforces Round 1106 (Div. 2)") 126 127 Idea: [lewc](/profile/lewc "Grandmaster lewc") 128 129 **Solution** 130 131 Tutorial is loading... 132 133 **Code** 134 135 ``` 136 #include <bits/stdc++.h> 137 138 using namespace std; 139 140 const int maxn = 2e5; 141 vector<int> g[maxn]; 142 int depth[maxn], dp[maxn]; 143 long long ans[maxn]; 144 145 void dfs(int v, int p = -1) { 146 ans[v] = 0; 147 dp[v] = depth[v]; 148 int m1 = depth[v], m2 = depth[v]; 149 for (auto u : g[v]) { 150 if (u != p) { 151 depth[u] = depth[v] + 1; 152 dfs(u, v); 153 dp[v] = max(dp[v], dp[u]); 154 ans[v] += ans[u]; 155 if (dp[u] >= m1) { 156 m2 = m1; 157 m1 = dp[u]; 158 } else if (dp[u] >= m2) { 159 m2 = dp[u]; 160 } 161 } 162 } 163 ans[v] += m2 - depth[v] + 1; 164 } 165 166 void solve() { 167 int n; 168 cin >> n; 169 for (int i = 1; i < n; ++i) { 170 int p; 171 cin >> p; 172 g[p - 1].push_back(i); 173 } 174 dfs(0); 175 cout << ans[0] << '\n'; 176 for (int i = 0; i < n; ++i) { 177 g[i].clear(); 178 } 179 } 180 181 int main() { 182 cin.tie(0); 183 ios::sync_with_stdio(0); 184 185 int t = 1; 186 cin >> t; 187 while (t--) { 188 solve(); 189 } 190 191 return 0; 192 } 193 ``` 194 195 **Rate the problem** 196 197 Excellent problem 198 199 Good problem 200 201 Average problem 202 203 Bad problem 204 205 Awful problem 206 207 [2238D - Storming Arasaka](/contest/2238/problem/D "Codeforces Round 1106 (Div. 2)") 208 209 Idea: [Friendiks](/profile/Friendiks "Grandmaster Friendiks") 210 211 **Solution** 212 213 Tutorial is loading... 214 215 **Code** 216 217 ``` 218 #include <bits/stdc++.h> 219 220 using namespace std; 221 222 const int maxn = 1e6 + 7; 223 224 int m[maxn], A[maxn], prime[maxn], nxt[maxn]; 225 226 int main() { 227 for (int p = 2; p < maxn; ++p) { 228 if (prime[p] == 0) { 229 for (int x = p; x < maxn; x += p) { 230 if (prime[x] == 0) prime[x] = p; 231 } 232 } 233 if (prime[p / prime[p]] == prime[p]) nxt[p] = nxt[p / prime[p]]; 234 else nxt[p] = p / prime[p]; 235 m[p] = m[nxt[p]] + 1; 236 A[p] = A[p / prime[p]] + 1; 237 } 238 int t; 239 cin >> t; 240 while (t--) { 241 int n; 242 cin >> n; 243 cout << m[n] + A[n] - 1 << "\n"; 244 } 245 return 0; 246 } 247 ``` 248 249 **Rate the problem** 250 251 Excellent problem 252 253 Good problem 254 255 Average problem 256 257 Bad problem 258 259 Awful problem 260 261 [2238E - Cake Trial](/contest/2238/problem/E "Codeforces Round 1106 (Div. 2)") 262 263 Idea: [lewc](/profile/lewc "Grandmaster lewc") 264 265 **Solution** 266 267 Tutorial is loading... 268 269 **Code** 270 271 ``` 272 #include <bits/stdc++.h> 273 274 using namespace std; 275 276 void solve() { 277 int n; 278 string s; 279 cin >> n >> s; 280 vector<vector<int>> dp(n + 1, vector<int> (n + 1, 1e9)); 281 dp[0][0] = 0; 282 for (int i = 0; i < n; ++i) { 283 vector<vector<int>> ndp(n + 1, vector<int> (n + 1, 1e9)); 284 for (int cnt_f = 0; cnt_f <= i; ++cnt_f) { 285 for (int cur_s = 0; cur_s <= i; ++cur_s) { 286 if (s[i] != 'T') { 287 ndp[cnt_f + 1][cur_s + 1] = min(ndp[cnt_f + 1][cur_s + 1], max(dp[cnt_f][cur_s], cur_s + 1)); 288 } 289 if (s[i] != 'F') { 290 ndp[cnt_f][max(0, cur_s - 1)] = min(ndp[cnt_f][max(0, cur_s - 1)], dp[cnt_f][cur_s]); 291 } 292 } 293 } 294 swap(dp, ndp); 295 } 296 int rs = 0; 297 for (int i = 0; i <= n; ++i) { 298 for (int j = 0; j <= n; ++j) { 299 rs = max(rs, i - dp[i][j]); 300 } 301 } 302 cout << rs << '\n'; 303 } 304 305 int main(){ 306 cin.tie(0); 307 ios::sync_with_stdio(0); 308 309 int t; 310 cin >> t; 311 while (t--) { 312 solve(); 313 } 314 315 return 0; 316 } 317 ``` 318 319 **Rate the problem** 320 321 Excellent problem 322 323 Good problem 324 325 Average problem 326 327 Bad problem 328 329 Awful problem 330 331 [2238F - Infinite Work](/contest/2238/problem/F "Codeforces Round 1106 (Div. 2)") 332 333 Idea: [KotlechkovEgor](/profile/KotlechkovEgor "Master KotlechkovEgor") 334 335 **Solution** 336 337 Tutorial is loading... 338 339 **Code** 340 341 ``` 342 #include <bits/stdc++.h> 343 344 using namespace std; 345 346 using ll = long long; 347 348 const int maxn = 2e6 + 1; 349 const ll mod = 1e9 + 7; 350 351 struct md { 352 ll x; 353 354 md(ll p) { 355 x = p % mod; 356 } 357 358 md operator+(md other) { 359 int p = x + other.x; 360 if (p >= mod) { 361 p -= mod; 362 } 363 if (p >= mod) { 364 p %= mod; 365 } 366 return {p}; 367 } 368 369 md operator-(md other) { 370 int p = x - other.x; 371 if (p < 0) { 372 p += mod; 373 } 374 if (p < 0) { 375 p = (p % mod + mod) % mod; 376 } 377 return {p}; 378 } 379 380 md operator*(md other) { 381 return {1ll * x * other.x % mod}; 382 } 383 384 md operator^(int x) { 385 if (x == 0) { 386 return {1}; 387 } 388 if (x % 2 == 0) { 389 md p = *this ^ (x / 2); 390 return {p * p}; 391 } 392 return *this * (*this ^ (x - 1)); 393 } 394 395 md operator/(md p) { 396 return *this * (p ^ (mod - 2)); 397 } 398 }; 399 400 vector<md> fact(1, md(1)); 401 vector<md> rfact = fact; 402 403 void prec() { 404 fact.resize(maxn, md(1)); 405 rfact = fact; 406 for (int i = 1; i < fact.size(); ++i) { 407 fact[i] = fact[i - 1] * md(i); 408 } 409 rfact[maxn - 1] = md(1) / fact[maxn - 1]; 410 for (int i = maxn - 2; i >= 0; --i) { 411 rfact[i] = rfact[i + 1] * (i + 1); 412 } 413 } 414 415 md c(int n, int k) { 416 if (n < 0 || k < 0 || k > n)return md(1); 417 return fact[n] * rfact[k] * rfact[n - k]; 418 } 419 420 md catalan(int n) { 421 if(n == 0){ 422 return 1; 423 } 424 return c(2 * n, n) - c(2 * n, n - 1); 425 } 426 427 void solve() { 428 ll n, k; 429 cin >> n >> k; 430 k++; 431 vector<ll> bits(61); 432 for (int i = 0; i < 61; ++i) { 433 bits[i] = k >> i & 1; 434 } 435 for (ll x = 60; x >= n; x--) { 436 bits[x - 1] += 2 * bits[x]; 437 bits[x] = 0; 438 } 439 int sm = 0; 440 for (int i = 0; i < 61; ++i) { 441 sm += bits[i]; 442 } 443 md an = catalan(sm - 1) * fact[sm]; 444 for (int i = 0; i < 61; ++i) { 445 if (bits[i] >= 2) { 446 an = an * rfact[bits[i]]; 447 } 448 } 449 cout << an.x << '\n'; 450 } 451 452 signed main() { 453 prec(); 454 signed t_ = 1; 455 cin >> t_; 456 while (t_--) { 457 solve(); 458 } 459 } 460 ``` 461 462 **Rate the problem** 463 464 Excellent problem 465 466 Good problem 467 468 Average problem 469 470 Bad problem 471 472 Awful problem