2125.md (8746B)
1 Source: https://codeforces.com/blog/entry/144998 2 3 [2125A - Difficult Contest](/contest/2125/problem/A "Educational Codeforces Round 181 (Rated for Div. 2)") 4 5 Idea: [FelixArg](/profile/FelixArg "Master FelixArg") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (awoo)** 12 13 ``` 14 #include<bits/stdc++.h> 15 using namespace std; 16 17 int main(){ 18 int tc; 19 cin >> tc; 20 while (tc--){ 21 string s; 22 cin >> s; 23 sort(s.begin(), s.end()); 24 reverse(s.begin(), s.end()); 25 cout << s << '\n'; 26 } 27 } 28 ``` 29 30 [2125B - Left and Down](/contest/2125/problem/B "Educational Codeforces Round 181 (Rated for Div. 2)") 31 32 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 33 34 **Tutorial** 35 36 Tutorial is loading... 37 38 **Solution (ifive)** 39 40 ``` 41 from math import gcd 42 for _ in range(int(input())): 43 a, b, k = map(int, input().split()) 44 g = gcd(a, b) 45 print(1 if a // g <= k and b // g <= k else 2) 46 ``` 47 48 [2125C - Count Good Numbers](/contest/2125/problem/C "Educational Codeforces Round 181 (Rated for Div. 2)") 49 50 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 51 52 **Tutorial** 53 54 Tutorial is loading... 55 56 **Solution 1 (BledDest)** 57 58 ``` 59 def good(x): 60 return x % 2 > 0 and x % 3 > 0 and x % 5 > 0 and x % 7 > 0 61 62 def get_naive(x): 63 ans = 0 64 for i in range(x): 65 if good(i): 66 ans += 1 67 return ans 68 69 def get(r): 70 return (r // 210) * get_naive(210) + get_naive(r % 210) 71 72 t = int(input()) 73 for i in range(t): 74 l, r = map(int, input().split()) 75 print(get(r+1) - get(l)) 76 ``` 77 78 **Solution 2 (awoo)** 79 80 ``` 81 for _ in range(int(input())): 82 l, r = map(int, input().split()) 83 84 def f(x): 85 res = 0 86 ps = [2, 3, 5, 7] 87 for mask in range(16): 88 m = 1 89 sg = 1 90 for i in range(4): 91 if (mask >> i) & 1: 92 m *= ps[i] 93 sg = -sg 94 res += sg * (x // m) 95 return res 96 97 print(f(r) - f(l - 1)) 98 ``` 99 100 [2125D - Segments Covering](/contest/2125/problem/D "Educational Codeforces Round 181 (Rated for Div. 2)") 101 102 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 103 104 **Tutorial** 105 106 Tutorial is loading... 107 108 **Solution 1 (Neon)** 109 110 ``` 111 #include <bits/stdc++.h> 112 113 using namespace std; 114 115 using pt = pair<int, int>; 116 117 const int MOD = 998244353; 118 119 int add(int x, int y) { 120 x += y; 121 if (x >= MOD) x -= MOD; 122 if (x < 0) x += MOD; 123 return x; 124 } 125 126 int mul(int x, int y) { 127 return x * 1LL * y % MOD; 128 } 129 130 int binpow(int x, int y) { 131 int z = 1; 132 while (y) { 133 if (y & 1) z = mul(z, x); 134 x = mul(x, x); 135 y >>= 1; 136 } 137 return z; 138 } 139 140 int divide(int x, int y) { 141 return mul(x, binpow(y, MOD - 2)); 142 } 143 144 int main() { 145 ios::sync_with_stdio(false); cin.tie(0); 146 int n, m; 147 cin >> n >> m; 148 vector<vector<pt>> a(m + 1); 149 for (int i = 0; i < n; ++i) { 150 int l, r, p, q; 151 cin >> l >> r >> p >> q; 152 a[r].emplace_back(l - 1, divide(p, q)); 153 } 154 vector<int> pr(m + 1); 155 pr[0] = 1; 156 for (int i = 1; i <= m; ++i) { 157 int cur = 1; 158 for (auto [_, p] : a[i]) cur = mul(cur, add(1, -p)); 159 pr[i] = mul(pr[i - 1], cur); 160 } 161 vector<int> dp(m + 1); 162 dp[0] = 1; 163 for (int i = 1; i <= m; ++i) { 164 for (auto [l, p] : a[i]) { 165 int cur = divide(pr[i], pr[l]); 166 cur = divide(cur, add(1, -p)); 167 cur = mul(cur, p); 168 dp[i] = add(dp[i], mul(dp[l], cur)); 169 } 170 } 171 cout << dp[m] << endl; 172 } 173 ``` 174 175 **Solution 2 (Neon)** 176 177 ``` 178 #include <bits/stdc++.h> 179 180 using namespace std; 181 182 using pt = pair<int, int>; 183 184 const int MOD = 998244353; 185 186 int add(int x, int y) { 187 x += y; 188 if (x >= MOD) x -= MOD; 189 if (x < 0) x += MOD; 190 return x; 191 } 192 193 int mul(int x, int y) { 194 return x * 1LL * y % MOD; 195 } 196 197 int binpow(int x, int y) { 198 int z = 1; 199 while (y) { 200 if (y & 1) z = mul(z, x); 201 x = mul(x, x); 202 y >>= 1; 203 } 204 return z; 205 } 206 207 int divide(int x, int y) { 208 return mul(x, binpow(y, MOD - 2)); 209 } 210 211 int main() { 212 ios::sync_with_stdio(false); cin.tie(0); 213 int n, m; 214 cin >> n >> m; 215 vector<vector<pt>> a(m + 1); 216 vector<int> dp(m + 1); 217 dp[0] = 1; 218 for (int i = 0; i < n; ++i) { 219 int l, r, p, q; 220 cin >> l >> r >> p >> q; 221 int val = divide(p, q); 222 a[r].emplace_back(l - 1, val); 223 dp[0] = mul(dp[0], add(1, -val)); 224 } 225 for (int i = 1; i <= m; ++i) { 226 for (auto [l, p] : a[i]) { 227 int cur = dp[l]; 228 cur = divide(cur, add(1, -p)); 229 cur = mul(cur, p); 230 dp[i] = add(dp[i], cur); 231 } 232 } 233 cout << dp[m] << endl; 234 } 235 ``` 236 237 [2125E - Sets of Complementary Sums](/contest/2125/problem/E "Educational Codeforces Round 181 (Rated for Div. 2)") 238 239 Idea: [FelixArg](/profile/FelixArg "Master FelixArg") 240 241 **Tutorial** 242 243 Tutorial is loading... 244 245 **Solution (FelixArg)** 246 247 ``` 248 #include<bits/stdc++.h> 249 using namespace std; 250 251 #define int long long 252 253 const int MOD = 998'244'353; 254 255 void solve(){ 256 int n, x; 257 cin >> n >> x; 258 // need sum(mx + 1 - ai) <= mx + 1 259 // start with 1, 2, 3, ... n 260 // min sum + 1 is n + 1 261 262 if (n == 1){ 263 cout << x << '\n'; 264 return; 265 } 266 267 int s_cur = n * (n + 1) / 2; 268 int need = s_cur - (n + 1); 269 270 // leads to n is O(sqrt(s)) 271 if (n + need > x){ 272 cout << 0 << '\n'; 273 return; 274 } 275 276 // so we can do dp[sum] knapsack 277 278 vector<int> dp(x + 1); 279 dp[0] = 1; 280 281 // for -1 and 0 282 for (int j = 0; j < 2; j++){ 283 for (int i = 0; i < x; i++){ 284 dp[i + 1] = (dp[i + 1] + dp[i]) % MOD; 285 } 286 } 287 288 for (int i = 1; i <= n - 2; i++){ 289 for (int j = 0; j < x; j++){ 290 // increase sum by i -> mx increase by 1 + i 291 if (j + i + 1 <= x){ 292 dp[j + i + 1] = (dp[j + i + 1] + dp[j]) % MOD; 293 } 294 } 295 } 296 297 int ans = 0; 298 for (int i = 0; i <= x; i++){ 299 int cur = n + need + i; 300 if (cur > x){ 301 break; 302 } 303 ans = (ans + dp[i]) % MOD; 304 } 305 306 cout << ans << '\n'; 307 } 308 309 signed main() 310 { 311 #ifdef FELIX 312 auto _clock_start = chrono::high_resolution_clock::now(); 313 #endif 314 ios_base::sync_with_stdio(false); 315 cin.tie(0); 316 cout.tie(0); 317 318 int t = 1; 319 cin >> t; 320 while(t--){ 321 solve(); 322 } 323 324 #ifdef FELIX 325 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 326 chrono::high_resolution_clock::now() 327 - _clock_start).count() << "ms." << endl; 328 #endif 329 return 0; 330 } 331 ``` 332 333 [2125F - Timofey and Docker](/contest/2125/problem/F "Educational Codeforces Round 181 (Rated for Div. 2)") 334 335 Idea: [FelixArg](/profile/FelixArg "Master FelixArg") 336 337 **Tutorial** 338 339 Tutorial is loading... 340 341 **Solution (awoo)** 342 343 ``` 344 #include <bits/stdc++.h> 345 346 using namespace std; 347 348 #define forn(i, n) for(int i = 0; i < int(n); i++) 349 350 const int INF = 1e8; 351 const string al = "docker"; 352 353 int main(){ 354 cin.tie(0); 355 ios::sync_with_stdio(false); 356 int tc; 357 cin >> tc; 358 while (tc--){ 359 string s; 360 cin >> s; 361 int n = s.size(); 362 int mx = n / 6; 363 int m; 364 cin >> m; 365 vector<int> dx(mx + 2); 366 forn(i, m){ 367 int l, r; 368 cin >> l >> r; 369 r = min(r, mx); 370 if (l > r) continue; 371 ++dx[l]; 372 --dx[r + 1]; 373 } 374 forn(i, mx + 1) dx[i + 1] += dx[i]; 375 376 int cur = 0; 377 vector<int> dif(max(0, n - 5)); 378 forn(i, n - 5){ 379 forn(j, 6) 380 dif[i] += s[i + j] != al[j]; 381 cur += dif[i] == 0; 382 } 383 384 int mxcnt = *max_element(dx.begin(), dx.end()); 385 int k = -1; 386 int ans = INF; 387 forn(i, mx + 1){ 388 if (dx[i] != mxcnt) continue; 389 if (i <= cur){ 390 ans = min(ans, cur - i); 391 continue; 392 } 393 k = i; 394 break; 395 } 396 397 if (k == -1){ 398 cout << ans << '\n'; 399 continue; 400 } 401 402 auto calc = [&](int d){ 403 vector<pair<long long, int>> dp(n + 1, {(long long)1e18, -1}); 404 dp[0] = {0, 0}; 405 forn(i, n){ 406 dp[i + 1] = min(dp[i + 1], dp[i]); 407 if (i + 6 <= n) 408 dp[i + 6] = min(dp[i + 6], {dp[i].first + dif[i] + d, dp[i].second - 1}); 409 } 410 return dp[n]; 411 }; 412 413 int l = -INF, r = 0, sv = INF; 414 while (l <= r){ 415 int m = (l + r) / 2; 416 auto [val, cnt] = calc(m); 417 if (-cnt >= k){ 418 sv = val - k * 1ll * m; 419 l = m + 1; 420 } 421 else{ 422 r = m - 1; 423 } 424 } 425 ans = min(ans, sv); 426 427 cout << ans << '\n'; 428 } 429 } 430 ```