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