1525.md (8036B)
1 Source: https://codeforces.com/blog/entry/90793 2 3 [1525A - Potion-making](/contest/1525/problem/A "Educational Codeforces Round 109 (Rated for Div. 2)") 4 5 Idea: [adedalic](/profile/adedalic "International Master adedalic") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (adedalic)** 12 13 ``` 14 #include<bits/stdc++.h> 15 using namespace std; 16 17 int main() { 18 int t; cin >> t; 19 while (t--) { 20 int k; cin >> k; 21 cout << 100 / gcd(100, k) << endl; 22 } 23 return 0; 24 } 25 ``` 26 27 [1525B - Permutation Sort](/contest/1525/problem/B "Educational Codeforces Round 109 (Rated for Div. 2)") 28 29 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 30 31 **Tutorial** 32 33 Tutorial is loading... 34 35 **Solution (Neon)** 36 37 ``` 38 #include <bits/stdc++.h> 39 40 using namespace std; 41 42 int main() { 43 int t; 44 scanf("%d", &t); 45 while (t--) { 46 int n; 47 scanf("%d", &n); 48 vector<int> a(n); 49 for (int &x : a) scanf("%d", &x); 50 int ans = 2; 51 if (is_sorted(a.begin(), a.end())) 52 ans = 0; 53 else if (a[0] == 1 || a[n - 1] == n) 54 ans = 1; 55 else if (a[0] == n && a[n - 1] == 1) 56 ans = 3; 57 printf("%d\n", ans); 58 } 59 } 60 ``` 61 62 [1525C - Robot Collisions](/contest/1525/problem/C "Educational Codeforces Round 109 (Rated for Div. 2)") 63 64 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 65 66 **Tutorial** 67 68 Tutorial is loading... 69 70 **Solution (awoo)** 71 72 ``` 73 #include <bits/stdc++.h> 74 75 #define forn(i, n) for (int i = 0; i < int(n); i++) 76 77 using namespace std; 78 79 struct bot{ 80 int x, d; 81 }; 82 83 int main() { 84 int t; 85 cin >> t; 86 forn(_, t){ 87 int n, m; 88 scanf("%d%d", &n, &m); 89 vector<bot> a(n); 90 forn(i, n) scanf("%d", &a[i].x); 91 forn(i, n){ 92 char c; 93 scanf(" %c", &c); 94 a[i].d = c == 'L' ? -1 : 1; 95 } 96 vector<int> ord(n); 97 iota(ord.begin(), ord.end(), 0); 98 sort(ord.begin(), ord.end(), [&a](int x, int y){ 99 return a[x].x < a[y].x; 100 }); 101 vector<int> ans(n, -1); 102 vector<vector<int>> par(2); 103 for (int i : ord){ 104 int p = a[i].x % 2; 105 if (a[i].d == -1){ 106 if (par[p].empty()) 107 par[p].push_back(i); 108 else{ 109 int j = par[p].back(); 110 par[p].pop_back(); 111 ans[i] = ans[j] = (a[i].x - (a[j].d == 1 ? a[j].x : -a[j].x)) / 2; 112 } 113 } 114 else{ 115 par[p].push_back(i); 116 } 117 } 118 forn(p, 2){ 119 while (int(par[p].size()) > 1){ 120 int i = par[p].back(); 121 par[p].pop_back(); 122 int j = par[p].back(); 123 par[p].pop_back(); 124 ans[i] = ans[j] = (2 * m - a[i].x - (a[j].d == 1 ? a[j].x : -a[j].x)) / 2; 125 } 126 } 127 forn(i, n){ 128 printf("%d ", ans[i]); 129 } 130 puts(""); 131 } 132 return 0; 133 } 134 ``` 135 136 [1525D - Armchairs](/contest/1525/problem/D "Educational Codeforces Round 109 (Rated for Div. 2)") 137 138 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 139 140 **Tutorial** 141 142 Tutorial is loading... 143 144 **Solution (BledDest)** 145 146 ``` 147 #include <bits/stdc++.h> 148 149 using namespace std; 150 151 const int INF = int(1e9); 152 153 int main() 154 { 155 int n; 156 cin >> n; 157 vector<int> a(n); 158 for(int i = 0; i < n; i++) 159 cin >> a[i]; 160 vector<int> pos; 161 for(int i = 0; i < n; i++) 162 if(a[i] == 1) 163 pos.push_back(i); 164 int k = pos.size(); 165 vector<vector<int>> dp(n + 1, vector<int>(k + 1, INF)); 166 dp[0][0] = 0; 167 for(int i = 0; i < n; i++) 168 for(int j = 0; j <= k; j++) 169 { 170 if(dp[i][j] == INF) continue; 171 dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]); 172 if(j < k && a[i] == 0) 173 dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(pos[j] - i)); 174 } 175 cout << dp[n][k] << endl; 176 } 177 ``` 178 179 [1525E - Assimilation IV](/contest/1525/problem/E "Educational Codeforces Round 109 (Rated for Div. 2)") 180 181 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 182 183 **Tutorial** 184 185 Tutorial is loading... 186 187 **Solution (adedalic)** 188 189 ``` 190 #include<bits/stdc++.h> 191 192 using namespace std; 193 194 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 195 #define sz(a) int((a).size()) 196 197 #define x first 198 #define y second 199 200 typedef long long li; 201 typedef pair<int, int> pt; 202 203 const int MOD = 998244353; 204 205 int norm(int a) { 206 while (a >= MOD) 207 a -= MOD; 208 while (a < 0) 209 a += MOD; 210 return a; 211 } 212 int mul(int a, int b) { 213 return int(a * 1ll * b % MOD); 214 } 215 int binPow(int a, int k) { 216 int ans = 1; 217 while (k > 0) { 218 if (k & 1) 219 ans = mul(ans, a); 220 a = mul(a, a); 221 k >>= 1; 222 } 223 return ans; 224 } 225 int inv(int a) { 226 return binPow(a, MOD - 2); 227 } 228 229 vector< vector<int> > d; 230 int n, m; 231 232 inline bool read() { 233 if(!(cin >> n >> m)) 234 return false; 235 d.resize(n, vector<int>(m)); 236 fore (i, 0, n) fore (j, 0, m) 237 cin >> d[i][j]; 238 return true; 239 } 240 241 inline void solve() { 242 int invFact = 1; 243 fore (i, 1, n + 1) 244 invFact = mul(invFact, i); 245 invFact = inv(invFact); 246 247 int E = 0; 248 fore (j, 0, m) { 249 vector<int> cnt(n + 1, 0); 250 fore (i, 0, n) 251 cnt[n + 1 - d[i][j]]++; 252 253 vector<int> d(n + 1, 0); 254 d[0] = 1; 255 int rem = 0; 256 fore (i, 0, n) { 257 rem += cnt[i]; 258 d[i + 1] = norm(d[i + 1] + mul(d[i], rem)); 259 rem = max(0, rem - 1); 260 } 261 // cerr << d[n] << " - " << norm(1 - mul(d[n], invFact)) << endl; 262 E = norm(E + 1 - mul(d[n], invFact)); 263 } 264 cout << E << endl; 265 } 266 267 int main() { 268 #ifdef _DEBUG 269 freopen("input.txt", "r", stdin); 270 int tt = clock(); 271 #endif 272 ios_base::sync_with_stdio(false); 273 cin.tie(0), cout.tie(0); 274 cout << fixed << setprecision(15); 275 276 if(read()) { 277 solve(); 278 279 #ifdef _DEBUG 280 cerr << "TIME = " << clock() - tt << endl; 281 tt = clock(); 282 #endif 283 } 284 return 0; 285 } 286 ``` 287 288 [1525F - Goblins And Gnomes](/contest/1525/problem/F "Educational Codeforces Round 109 (Rated for Div. 2)") 289 290 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 291 292 **Tutorial** 293 294 Tutorial is loading... 295 296 **Solution (BledDest)** 297 298 ``` 299 #include <bits/stdc++.h> 300 301 using namespace std; 302 303 const int N = 543; 304 const long long INF = (long long)(1e18); 305 306 struct Matching 307 { 308 int n1, n2; 309 vector<set<int>> g; 310 vector<int> mt, used; 311 312 void init() 313 { 314 mt = vector<int>(n2, -1); 315 } 316 317 int kuhn(int x) 318 { 319 if(used[x] == 1) return 0; 320 used[x] = 1; 321 for(auto y : g[x]) 322 if(mt[y] == -1 || kuhn(mt[y]) == 1) 323 { 324 mt[y] = x; 325 return 1; 326 } 327 return 0; 328 } 329 330 int calc() 331 { 332 init(); 333 int sum = 0; 334 for(int i = 0; i < n1; i++) 335 { 336 used = vector<int>(n1, 0); 337 sum += kuhn(i); 338 } 339 return sum; 340 } 341 342 void remove_vertex(int v, bool right) 343 { 344 if(right) 345 { 346 for(int i = 0; i < n1; i++) 347 g[i].erase(v); 348 } 349 else 350 g[v].clear(); 351 } 352 353 void add_edge(int x, int y) 354 { 355 g[x].insert(y); 356 } 357 358 Matching() {}; 359 Matching(int n1, int n2) : n1(n1), n2(n2) 360 { 361 g.resize(n1); 362 }; 363 }; 364 365 int n, m, k; 366 long long dp[N][N]; 367 int p[N][N]; 368 vector<int> g[N]; 369 long long x[N], y[N]; 370 371 int main() 372 { 373 cin >> n >> m >> k; 374 for(int i = 0; i < m; i++) 375 { 376 int u, v; 377 cin >> u >> v; 378 --u; 379 --v; 380 g[u].push_back(v); 381 } 382 for(int i = 0; i < k; i++) 383 cin >> x[i] >> y[i]; 384 385 Matching mt(n, n); 386 for(int i = 0; i < n; i++) 387 for(auto j : g[i]) 388 mt.add_edge(i, j); 389 int cnt = mt.calc(); 390 int cur = cnt; 391 vector<int> seq; 392 while(cur > 0) 393 { 394 int idx = 0; 395 for(int i = 0; i < n; i++) 396 { 397 Matching mt2 = mt; 398 mt2.remove_vertex(i, false); 399 if(mt2.calc() < cur) 400 idx = i + 1; 401 mt2 = mt; 402 mt2.remove_vertex(i, true); 403 if(mt2.calc() < cur) 404 idx = -(i + 1); 405 } 406 assert(idx != 0); 407 seq.push_back(idx); 408 mt.remove_vertex(abs(idx) - 1, idx < 0); 409 cur--; 410 } 411 reverse(seq.begin(), seq.end()); 412 for(int i = 0; i <= k; i++) 413 for(int j = 0; j <= cnt; j++) 414 dp[i][j] = -INF; 415 dp[0][cnt] = 0; 416 for(int i = 0; i < k; i++) 417 for(int j = 0; j <= cnt; j++) 418 { 419 if(dp[i][j] == -INF) continue; 420 for(int z = 0; z <= j; z++) 421 { 422 if(i + 1 + z >= n) continue; 423 int t = j - z; 424 long long add = max(0ll, x[i] - t * y[i]); 425 if(dp[i + 1][z] < dp[i][j] + add) 426 { 427 dp[i + 1][z] = dp[i][j] + add; 428 p[i + 1][z] = j; 429 } 430 } 431 } 432 cur = max_element(dp[k], dp[k] + cnt + 1) - dp[k]; 433 vector<int> res; 434 for(int i = k; i > 0; i--) 435 { 436 res.push_back(0); 437 for(int j = p[i][cur] - 1; j >= cur; j--) 438 res.push_back(seq[j]); 439 cur = p[i][cur]; 440 } 441 reverse(res.begin(), res.end()); 442 cout << res.size() << endl; 443 for(auto x : res) cout << x << " "; 444 cout << endl; 445 } 446 ```