2204.md (9951B)
1 Source: https://codeforces.com/blog/entry/152150 2 3 [2204A - Passing the Ball](/contest/2204/problem/A "Educational Codeforces Round 188 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 #include<bits/stdc++.h> 15 16 using namespace std; 17 18 int main() 19 { 20 int t; 21 cin >> t; 22 for(int i = 0; i < t; i++) 23 { 24 int n; 25 cin >> n; 26 string s; 27 cin >> s; 28 cout << s.find("RL") + 2 << endl; 29 } 30 return 0; 31 } 32 ``` 33 34 [2204B - Right Maximum](/contest/2204/problem/B "Educational Codeforces Round 188 (Rated for Div. 2)") 35 36 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm") 37 38 **Tutorial** 39 40 Tutorial is loading... 41 42 **Solution (BledDest)** 43 44 ``` 45 #include<bits/stdc++.h> 46 47 using namespace std; 48 49 void solve() 50 { 51 int n; 52 cin >> n; 53 vector<int> a(n); 54 for(int i = 0; i < n; i++) cin >> a[i]; 55 int mx = 0; 56 int ans = 0; 57 for(int i = 0; i < n; i++) 58 { 59 if(a[i] >= mx) ans++; 60 mx = max(mx, a[i]); 61 } 62 cout << ans << "\n"; 63 } 64 65 int main() 66 { 67 ios_base::sync_with_stdio(0); 68 cin.tie(0); 69 int t; 70 cin >> t; 71 for(int i = 0; i < t; i++) 72 solve(); 73 return 0; 74 } 75 ``` 76 77 [2204C - Spring](/contest/2204/problem/C "Educational Codeforces Round 188 (Rated for Div. 2)") 78 79 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 80 81 **Tutorial** 82 83 Tutorial is loading... 84 85 **Solution (BledDest)** 86 87 ``` 88 #include<bits/stdc++.h> 89 90 using namespace std; 91 92 long long getOne(long long a, long long m) 93 { 94 return m / a; 95 } 96 97 long long getTwo(long long a, long long b, long long m) 98 { 99 return m / lcm(a, b); 100 } 101 102 long long getThree(long long a, long long b, long long c, long long m) 103 { 104 return m / lcm(lcm(a, b), c); 105 } 106 107 long long get(long long a, long long b, long long c, long long m) 108 { 109 long long c1 = getOne(a, m); 110 long long c2 = getTwo(a, b, m) + getTwo(a, c, m); 111 long long c3 = getThree(a, b, c, m); 112 return (c1 - c2 + c3) * 6 + (c2 - 2 * c3) * 3 + c3 * 2; 113 } 114 115 void solve() 116 { 117 long long a, b, c, m; 118 cin >> a >> b >> c >> m; 119 cout << get(a, b, c, m) << " " << get(b, a, c, m) << " " << get(c, a, b, m) << endl; 120 } 121 122 int main() 123 { 124 ios_base::sync_with_stdio(0); 125 cin.tie(0); 126 int t; 127 cin >> t; 128 for(int i = 0; i < t; i++) 129 solve(); 130 return 0; 131 } 132 ``` 133 134 [2204D - Alternating Path](/contest/2204/problem/D "Educational Codeforces Round 188 (Rated for Div. 2)") 135 136 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 137 138 **Tutorial** 139 140 Tutorial is loading... 141 142 **Solution (awoo)** 143 144 ``` 145 #include <bits/stdc++.h> 146 147 #define forn(i, n) for (int i = 0; i < int(n); i++) 148 149 using namespace std; 150 151 152 int main() { 153 cin.tie(0); 154 ios::sync_with_stdio(false); 155 int t; 156 cin >> t; 157 while (t--){ 158 int n, m; 159 cin >> n >> m; 160 vector<vector<int>> g(n); 161 forn(i, m){ 162 int v, u; 163 cin >> v >> u; 164 --v, --u; 165 g[v].push_back(u); 166 g[u].push_back(v); 167 } 168 vector<int> clr(n, -1); 169 int ans = 0; 170 forn(i, n) if (clr[i] == -1){ 171 queue<int> q; 172 q.push(i); 173 clr[i] = 0; 174 vector<int> cnt(2); 175 bool ok = true; 176 while (!q.empty()){ 177 int v = q.front(); 178 q.pop(); 179 ++cnt[clr[v]]; 180 for (int u : g[v]){ 181 if (clr[u] == clr[v]) 182 ok = false; 183 else if (clr[u] == -1){ 184 clr[u] = clr[v] ^ 1; 185 q.push(u); 186 } 187 } 188 } 189 if (ok) ans += max(cnt[0], cnt[1]); 190 } 191 cout << ans << '\n'; 192 } 193 return 0; 194 } 195 ``` 196 197 [2204E - Sum of Digits (and Again)](/contest/2204/problem/E "Educational Codeforces Round 188 (Rated for Div. 2)") 198 199 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 200 201 **Tutorial** 202 203 Tutorial is loading... 204 205 **Solution (BledDest)** 206 207 ``` 208 #include<bits/stdc++.h> 209 210 using namespace std; 211 212 int f(int x) 213 { 214 int res = 0; 215 while(x != 0) 216 { 217 res += x % 10; 218 x /= 10; 219 } 220 return res; 221 } 222 223 void solve() 224 { 225 string s; 226 cin >> s; 227 int n = s.size(); 228 if(n == 1) 229 { 230 cout << s << "\n"; 231 return; 232 } 233 vector<int> cnt(10); 234 int sum_digits = 0; 235 for(auto x : s) 236 { 237 cnt[x - '0']++; 238 sum_digits += x - '0'; 239 } 240 for(int x = 1; x <= n * 9; x++) 241 { 242 int nx = x; 243 string sx = to_string(nx); 244 while(nx > 9) 245 { 246 nx = f(nx); 247 sx += to_string(nx); 248 } 249 //cout << x << " " << sx << endl; 250 vector<int> need_cnt(10); 251 int sum_digits_x = 0; 252 for(auto y : sx) 253 { 254 need_cnt[y - '0']++; 255 sum_digits_x += y - '0'; 256 } 257 bool can = true; 258 for(int i = 0; i <= 9; i++) 259 if(need_cnt[i] > cnt[i]) can = false; 260 if(sum_digits - sum_digits_x != x) 261 can = false; 262 if(can) 263 { 264 string res = ""; 265 for(int i = 9; i >= 0; i--) 266 { 267 for(int j = 0; j < cnt[i] - need_cnt[i]; j++) 268 res.push_back(char('0' + i)); 269 } 270 res += sx; 271 cout << res << endl; 272 return; 273 } 274 } 275 } 276 277 int main() 278 { 279 ios_base::sync_with_stdio(0); 280 cin.tie(0); 281 int t; 282 cin >> t; 283 for(int i = 0; i < t; i++) 284 solve(); 285 return 0; 286 } 287 ``` 288 289 [2204F - Sum of Fractions](/contest/2204/problem/F "Educational Codeforces Round 188 (Rated for Div. 2)") 290 291 Idea: [adedalic](/profile/adedalic "International Master adedalic") 292 293 **Tutorial** 294 295 Tutorial is loading... 296 297 **Solution (adedalic)** 298 299 ``` 300 #include<bits/stdc++.h> 301 302 using namespace std; 303 304 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 305 #define sz(a) int((a).size()) 306 307 #define x first 308 #define y second 309 310 typedef long long li; 311 typedef long double ld; 312 typedef pair<int, int> pt; 313 314 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 315 return out << "(" << p.x << ", " << p.y << ")"; 316 } 317 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 318 fore(i, 0, sz(v)) { 319 if(i) out << " "; 320 out << v[i]; 321 } 322 return out; 323 } 324 325 const int INF = int(1e9); 326 const li INF64 = li(1e18); 327 const ld EPS = 1e-9; 328 329 const int MOD = 998'244'353; 330 331 int add(int a, int b) { 332 a += b; 333 while (a >= MOD) 334 a -= MOD; 335 while (a < 0) 336 a += MOD; 337 return a; 338 } 339 int mul(int a, int b) { 340 return a * 1ll * b % MOD; 341 } 342 int binPow(int a, int k) { 343 int ans = 1; 344 while (k > 0) { 345 if (k & 1) 346 ans = mul(ans, a); 347 a = mul(a, a); 348 k >>= 1; 349 } 350 return ans; 351 } 352 353 int n, m; 354 vector<int> a, k; 355 356 inline bool read() { 357 if(!(cin >> n >> m)) 358 return false; 359 a.resize(n); 360 fore (i, 0, n) 361 cin >> a[i]; 362 k.resize(m); 363 fore (i, 0, m) 364 cin >> k[i]; 365 return true; 366 } 367 368 inline void solve() { 369 vector<int> lf(n, -1), rg(n, n); 370 vector<int> st; 371 fore (i, 0, n) { 372 while (!st.empty() && a[st.back()] > a[i]) 373 st.pop_back(); 374 if (!st.empty()) 375 lf[i] = st.back(); 376 st.push_back(i); 377 } 378 st.clear(); 379 for (int i = n - 1; i >= 0; i--) { 380 while (!st.empty() && a[st.back()] >= a[i]) 381 st.pop_back(); 382 if (!st.empty()) 383 rg[i] = st.back(); 384 st.push_back(i); 385 } 386 387 int commonSum = 0; 388 vector<int> la(m + 1), lk(m + 1), ra(m + 1), rk(m + 1); 389 390 //[l, r) 391 auto addSeg = [](vector<int> &pS, int l, int r, int val) { 392 pS[l] = add(pS[l], val); 393 pS[r] = add(pS[r], -val); 394 }; 395 396 fore (i, 0, n) { 397 int cnt = mul(i - lf[i], rg[i] - i); 398 int rem = add(mul(i + 1, n - i), -cnt); 399 int ia = binPow(a[i], MOD - 2); 400 commonSum = add(commonSum, mul(rem, ia)); 401 402 int p = lower_bound(k.begin(), k.end(), a[i]) - k.begin(); 403 addSeg(la, 0, p, mul(cnt, ia)); 404 addSeg(lk, 0, p, mul(cnt, ia)); 405 addSeg(ra, p, m, cnt); 406 addSeg(rk, p, m, mul(cnt, add(2, -a[i]))); 407 } 408 fore (i, 0, m) { 409 la[i + 1] = add(la[i + 1], la[i]); 410 lk[i + 1] = add(lk[i + 1], lk[i]); 411 ra[i + 1] = add(ra[i + 1], ra[i]); 412 rk[i + 1] = add(rk[i + 1], rk[i]); 413 } 414 415 fore (i, 0, m) { 416 int ans = commonSum; 417 ans = add(ans, mul(add(la[i], ra[i]), k[i])); 418 ans = add(ans, add(lk[i], rk[i])); 419 cout << ans << '\n'; 420 } 421 } 422 423 int main() { 424 #ifdef _DEBUG 425 freopen("input.txt", "r", stdin); 426 int tt = clock(); 427 #endif 428 ios_base::sync_with_stdio(false); 429 cin.tie(0), cout.tie(0); 430 cout << fixed << setprecision(15); 431 432 if(read()) { 433 solve(); 434 435 #ifdef _DEBUG 436 cerr << "TIME = " << clock() - tt << endl; 437 tt = clock(); 438 #endif 439 } 440 return 0; 441 } 442 ``` 443 444 [2204G - Grid Path](/contest/2204/problem/G "Educational Codeforces Round 188 (Rated for Div. 2)") 445 446 Idea: [Roms](/profile/Roms "Master Roms") 447 448 **Tutorial** 449 450 Tutorial is loading... 451 452 **Solution (Neon)** 453 454 ``` 455 #include <bits/stdc++.h> 456 457 using namespace std; 458 459 #define forn(i, n) for (int i = 0; i < int(n); ++i) 460 461 const int K = 301; 462 463 using mat = vector<vector<int>>; 464 465 int n, m, mod, k; 466 467 int add(int x, int y) { 468 x += y; 469 if (x >= mod) x -= mod; 470 return x; 471 } 472 473 int mul(int x, int y) { 474 return x * 1LL * y % mod; 475 } 476 477 unsigned long long aux[K][K]; 478 479 mat mul(mat a, mat b) { 480 mat b2(k, vector<int>(k)); 481 forn(x, k) forn(y, k) b2[x][y] = b[y][x]; 482 mat c(k, vector<int>(k)); 483 forn(x, k) forn(y, k) { 484 aux[x][y] = 0; 485 forn(z, k) { 486 aux[x][y] += a[x][z] * 1ll * b2[y][z]; 487 if((z & 15) == 15) 488 aux[x][y] %= mod; 489 } 490 c[x][y] = aux[x][y] % mod; 491 } 492 return c; 493 } 494 495 mat binpow(mat a, int b) { 496 mat c(k, vector<int>(k)); 497 forn(i, k) c[i][i] = 1; 498 while (b) { 499 if (b & 1) c = mul(c, a); 500 a = mul(a, a); 501 b >>= 1; 502 } 503 return c; 504 } 505 506 int main() { 507 cin >> n >> m >> mod; 508 k = 2 * m + 1; 509 mat a(k, vector<int>(k)); 510 a[k - 1][k - 1] = 1; 511 forn(i, m) forn(f, 2) { 512 for (int l = f ? 0 : i; l <= i; ++l) { 513 for (int r = i; r < m; ++r) { 514 a[i * 2 + f][k - 1] = add(a[i * 2 + f][k - 1], 1); 515 for (int j = l; j <= r; ++j) { 516 a[i * 2 + f][j * 2 + (j == l)] = add(a[i * 2 + f][j * 2 + (j == l)], 1); 517 } 518 } 519 } 520 } 521 auto res = binpow(a, n); 522 cout << res[1][k - 1] << endl; 523 } 524 ```