1009.md (9759B)
1 Source: https://codeforces.com/blog/entry/60630 2 3 [1009A - Game Shopping](/contest/1009/problem/A "Educational Codeforces Round 47 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (Vovuh)** 10 11 ``` 12 n, m = map(int, input().split()) 13 a = list(map(int, input().split())) 14 b = list(map(int, input().split())) 15 pos = 0 16 for i in a: 17 pos += (pos < len(b) and b[pos] >= i) 18 print(pos) 19 ``` 20 21 [1009B - Minimum Ternary String](/contest/1009/problem/B "Educational Codeforces Round 47 (Rated for Div. 2)") 22 23 **Tutorial** 24 25 Tutorial is loading... 26 27 **Solution (Vovuh)** 28 29 ``` 30 #include <bits/stdc++.h> 31 32 using namespace std; 33 34 int main() { 35 #ifdef _DEBUG 36 freopen("input.txt", "r", stdin); 37 // freopen("output.txt", "w", stdout); 38 #endif 39 40 string s; 41 cin >> s; 42 43 string ans; 44 45 int cnt = 0; 46 for (auto c : s) { 47 if (c == '1') ++cnt; 48 else ans += c; 49 } 50 51 int n = ans.size(); 52 int pos = -1; 53 while (pos + 1 < n && ans[pos + 1] == '0') ++pos; 54 ans.insert(pos + 1, string(cnt, '1')); 55 56 cout << ans << endl; 57 58 return 0; 59 } 60 ``` 61 62 [1009C - Annoying Present](/contest/1009/problem/C "Educational Codeforces Round 47 (Rated for Div. 2)") 63 64 **Tutorial** 65 66 Tutorial is loading... 67 68 **Solution (PikMike)** 69 70 ``` 71 #include <bits/stdc++.h> 72 73 #define forn(i, n) for (int i = 0; i < int(n); i++) 74 75 using namespace std; 76 77 typedef long long li; 78 79 int main() { 80 int n, m; 81 scanf("%d%d", &n, &m); 82 83 li neg = ((n - 1) / 2) * li((n - 1) / 2 + 1); 84 if (n % 2 == 0) neg += n / 2; 85 li pos = n * li(n - 1) / 2; 86 87 li ans = 0; 88 forn(i, m){ 89 int x, d; 90 scanf("%d%d", &x, &d); 91 ans += x * li(n); 92 if (d < 0) 93 ans += neg * d; 94 else 95 ans += pos * d; 96 } 97 98 printf("%.15f\n", double(ans) / n); 99 return 0; 100 } 101 ``` 102 103 [1009D - Relatively Prime Graph](/contest/1009/problem/D "Educational Codeforces Round 47 (Rated for Div. 2)") 104 105 **Tutorial** 106 107 Tutorial is loading... 108 109 **Solution (PikMike)** 110 111 ``` 112 #include <bits/stdc++.h> 113 114 #define forn(i, n) for (int i = 0; i < int(n); i++) 115 116 using namespace std; 117 118 const int N = 100000; 119 120 pair<int, int> ans[N]; 121 122 int main() { 123 int n, m; 124 scanf("%d%d", &n, &m); 125 126 if (m < n - 1) { 127 puts("Impossible"); 128 return 0; 129 } 130 131 int cur = 0; 132 133 forn(i, n) for (int j = i + 1; j < n; ++j){ 134 if (cur == m) 135 break; 136 if (__gcd(i + 1, j + 1) == 1) 137 ans[cur++] = make_pair(j, i); 138 } 139 140 if (cur != m){ 141 puts("Impossible"); 142 return 0; 143 } 144 145 puts("Possible"); 146 forn(i, m) 147 printf("%d %d\n", ans[i].first + 1, ans[i].second + 1); 148 149 return 0; 150 } 151 ``` 152 153 [1009E - Intercity Travelling](/contest/1009/problem/E "Educational Codeforces Round 47 (Rated for Div. 2)") 154 155 **Tutorial** 156 157 Tutorial is loading... 158 159 **Solution (BledDest)** 160 161 ``` 162 #include<bits/stdc++.h> 163 164 using namespace std; 165 166 const int MOD = 998244353; 167 168 int add(int x, int y) 169 { 170 x += y; 171 while(x >= MOD) 172 x -= MOD; 173 while(x < 0) 174 x += MOD; 175 return x; 176 } 177 178 int mul(int x, int y) 179 { 180 return (x * 1ll * y) % MOD; 181 } 182 183 int main() 184 { 185 int n; 186 scanf("%d", &n); 187 vector<int> a(n); 188 for(int i = 0; i < n; i++) 189 scanf("%d", &a[i]); 190 191 int ans = 0; 192 vector<int> pw2(1, 1); 193 while(pw2.size() < n) 194 pw2.push_back(mul(pw2.back(), 2)); 195 int cur = mul(pw2[n - 1], a[0]); 196 for(int i = 0; i < n; i++) 197 { 198 ans = add(ans, cur); 199 if(i < n - 1) 200 { 201 cur = add(cur, -mul(pw2[n - 2 - i], a[i])); 202 cur = add(cur, mul(pw2[n - 2 - i], a[i + 1])); 203 } 204 } 205 printf("%d\n", ans); 206 } 207 ``` 208 209 [1009F - Dominant Indices](/contest/1009/problem/F "Educational Codeforces Round 47 (Rated for Div. 2)") 210 211 **Tutorial** 212 213 Tutorial is loading... 214 215 **Solution (BledDest)** 216 217 ``` 218 #define _CRT_SECURE_NO_WARNINGS 219 220 #include <vector> 221 #include <cstdio> 222 #include <iostream> 223 #include <algorithm> 224 225 // RJ? No, thanks 226 227 using namespace std; 228 229 const int N = 1000043; 230 231 struct state 232 { 233 vector<int>* a; 234 int cur_max; 235 int sz() 236 { 237 return a->size(); 238 } 239 void add(int i, int val) 240 { 241 (*a)[i] += val; 242 if(make_pair((*a)[i], i) > make_pair((*a)[cur_max], cur_max)) 243 cur_max = i; 244 } 245 }; 246 247 state pull(state z) 248 { 249 if(z.sz() == 0) 250 { 251 state c; 252 c.a = new vector<int>(1, 1); 253 c.cur_max = 0; 254 return c; 255 } 256 else 257 { 258 state c; 259 c.a = z.a; 260 c.cur_max = z.cur_max; 261 c.a->push_back(0); 262 c.add(c.sz() - 1, 1); 263 return c; 264 } 265 } 266 267 state merge(state a, state b) 268 { 269 if(a.sz() < b.sz()) 270 swap(a, b); 271 state c; 272 c.a = a.a; 273 c.cur_max = a.cur_max; 274 int as = c.sz(); 275 int bs = b.sz(); 276 for(int i = 0; i < bs; i++) 277 a.add(as - i - 1, (*(b.a))[bs - i - 1]); 278 return a; 279 } 280 281 state s[N]; 282 int ans[N]; 283 vector<int> g[N]; 284 285 void dfs(int x, int p = -1) 286 { 287 s[x].a = new vector<int>(0); 288 s[x].cur_max = 0; 289 for(auto y : g[x]) 290 if(y != p) 291 { 292 dfs(y, x); 293 s[x] = merge(s[x], s[y]); 294 } 295 s[x] = pull(s[x]); 296 ans[x] = s[x].sz() - s[x].cur_max - 1; 297 } 298 299 int main() 300 { 301 int n; 302 scanf("%d", &n); 303 for(int i = 0; i < n - 1; i++) 304 { 305 int x, y; 306 scanf("%d %d", &x, &y); 307 --x; 308 --y; 309 g[x].push_back(y); 310 g[y].push_back(x); 311 } 312 dfs(0); 313 for(int i = 0; i < n; i++) 314 printf("%d\n", ans[i]); 315 return 0; 316 } 317 ``` 318 319 [1009G - Allowed Letters](/contest/1009/problem/G "Educational Codeforces Round 47 (Rated for Div. 2)") 320 321 **Tutorial** 322 323 Tutorial is loading... 324 325 **Solution (Bleddest)** 326 327 ``` 328 #include<bits/stdc++.h> 329 330 using namespace std; 331 332 #define sz(a) ((int)(a).size()) 333 334 struct edge 335 { 336 int y; 337 int c; 338 int f; 339 edge() {}; 340 edge(int y, int c, int f) : y(y), c(c), f(f) {}; 341 }; 342 343 const int N = 100; 344 345 vector<edge> e; 346 vector<int> g[N]; 347 int edge_num[N][N]; 348 int char_vertex[6]; 349 int mask_vertex[N]; 350 int used[N]; 351 int cc = 0; 352 int s, t; 353 354 void add_edge(int x, int y, int c) 355 { 356 edge_num[x][y] = sz(e); 357 g[x].push_back(sz(e)); 358 e.push_back(edge(y, c, 0)); 359 edge_num[y][x] = sz(e); 360 g[y].push_back(sz(e)); 361 e.push_back(edge(x, 0, 0)); 362 } 363 364 int rem(int num) 365 { 366 return e[num].c - e[num].f; 367 } 368 369 int dfs(int x, int mx) 370 { 371 if(x == t) return mx; 372 if(used[x] == cc) return 0; 373 used[x] = cc; 374 for(auto num : g[x]) 375 { 376 if(rem(num)) 377 { 378 int pushed = dfs(e[num].y, min(mx, rem(num))); 379 if(pushed) 380 { 381 e[num].f += pushed; 382 e[num ^ 1].f -= pushed; 383 return pushed; 384 } 385 } 386 } 387 return 0; 388 } 389 390 bool check(int ch, int mask) 391 { 392 if((mask & (1 << ch)) == 0) 393 return false; 394 int cv = char_vertex[ch]; 395 int mv = mask_vertex[mask]; 396 int e1 = edge_num[s][cv]; 397 int e2 = edge_num[mv][t]; 398 if(e[e1].f == 0 || e[e2].f == 0) 399 return false; 400 e[e1].f--; 401 e[e1 ^ 1].f++; 402 vector<int> affected_edges; 403 affected_edges.push_back(e1); 404 for(auto x : g[cv]) 405 { 406 if((x & 1) == 0 && e[x].f > 0) 407 { 408 affected_edges.push_back(x); 409 e[x].f--; 410 e[x ^ 1].f++; 411 int y = e[x].y; 412 for(auto x2 : g[y]) 413 { 414 if((x2 & 1) == 0) 415 { 416 affected_edges.push_back(x2); 417 e[x2].f--; 418 e[x2 ^ 1].f++; 419 break; 420 } 421 } 422 break; 423 } 424 } 425 if(e[e2].f < e[e2].c) 426 { 427 e[e1].c--; 428 e[e2].c--; 429 return true; 430 } 431 affected_edges.push_back(e2); 432 e[e2].f--; 433 e[e2 ^ 1].f++; 434 for(auto x : g[mv]) 435 { 436 if((x & 1) == 1 && e[x].f < 0) 437 { 438 affected_edges.push_back(x ^ 1); 439 e[x].f++; 440 e[x ^ 1].f--; 441 int y = e[x].y; 442 for(auto x2 : g[y]) 443 { 444 if((x2 & 1) == 1) 445 { 446 affected_edges.push_back(x2 ^ 1); 447 e[x2].f++; 448 e[x2 ^ 1].f--; 449 break; 450 } 451 } 452 break; 453 } 454 } 455 cc++; 456 e[e1].c--; 457 e[e2].c--; 458 if(dfs(s, 1)) 459 return true; 460 else 461 { 462 e[e1].c++; 463 e[e2].c++; 464 for(auto x : affected_edges) 465 { 466 e[x].f++; 467 e[x ^ 1].f--; 468 } 469 return false; 470 } 471 } 472 473 char buf[100043]; 474 string allowed[100043]; 475 int allowed_mask[100043]; 476 477 int main() 478 { 479 s = 70; 480 t = 71; 481 scanf("%s", buf); 482 string z = buf; 483 int n = sz(z); 484 int m; 485 scanf("%d", &m); 486 for(int i = 0; i < n; i++) 487 { 488 allowed[i] = "abcdef"; 489 allowed_mask[i] = 63; 490 } 491 for(int i = 0; i < m; i++) 492 { 493 int idx; 494 scanf("%d", &idx); 495 --idx; 496 scanf("%s", buf); 497 allowed[idx] = buf; 498 allowed_mask[idx] = 0; 499 for(auto x : allowed[idx]) 500 { 501 allowed_mask[idx] |= (1 << (x - 'a')); 502 } 503 } 504 for(int i = 0; i < 6; i++) 505 char_vertex[i] = i; 506 for(int i = 0; i < (1 << 6); i++) 507 mask_vertex[i] = i + 6; 508 for(int i = 0; i < (1 << 6); i++) 509 for(int j = 0; j < 6; j++) 510 if(i & (1 << j)) 511 add_edge(char_vertex[j], mask_vertex[i], 100000); 512 for(int i = 0; i < 6; i++) 513 { 514 int cnt = 0; 515 for(int j = 0; j < n; j++) 516 if(z[j] == 'a' + i) 517 cnt++; 518 add_edge(s, char_vertex[i], cnt); 519 } 520 for(int i = 0; i < (1 << 6); i++) 521 { 522 int cnt = 0; 523 for(int j = 0; j < n; j++) 524 if(allowed_mask[j] == i) 525 cnt++; 526 add_edge(mask_vertex[i], t, cnt); 527 } 528 int flow = 0; 529 while(true) 530 { 531 cc++; 532 int p = dfs(s, 100000); 533 if(p) 534 flow += p; 535 else 536 break; 537 } 538 if(flow != n) 539 { 540 puts("Impossible"); 541 return 0; 542 } 543 for(int i = 0; i < n; i++) 544 for(int j = 0; j < 6; j++) 545 { 546 if(check(j, allowed_mask[i])) 547 { 548 printf("%c", j + 'a'); 549 break; 550 } 551 } 552 puts(""); 553 } 554 ```