1156.md (8593B)
1 Source: https://codeforces.com/blog/entry/66827 2 3 [1156A - Inscribed Figures](/contest/1156/problem/A "Educational Codeforces Round 64 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (PikMike)** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 #define forn(i, n) for(int i = 0; i < int(n); i++) 15 16 using namespace std; 17 18 int main(){ 19 int n; 20 scanf("%d", &n); 21 int sum = 0; 22 int lst = 1; 23 vector<int> figs; 24 forn(i, n){ 25 int x; 26 scanf("%d", &x); 27 if (lst != 1 && x != 1){ 28 puts("Infinite"); 29 return 0; 30 } 31 if (x != 1){ 32 figs.push_back(x); 33 sum += x + 1; 34 if (i != 0 && i != n - 1) 35 sum += x + 1; 36 } 37 lst = x; 38 } 39 forn(i, int(figs.size()) - 1) if (figs[i] == 3 && figs[i + 1] == 2) 40 --sum; 41 printf("Finite\n%d\n", sum); 42 } 43 ``` 44 45 [1156B - Ugly Pairs](/contest/1156/problem/B "Educational Codeforces Round 64 (Rated for Div. 2)") 46 47 **Tutorial** 48 49 Tutorial is loading... 50 51 **Solution (PikMike)** 52 53 ``` 54 #include <bits/stdc++.h> 55 56 #define forn(i, n) for (int i = 0; i < int(n); i++) 57 58 using namespace std; 59 60 bool check(string s){ 61 bool ok = true; 62 forn(i, int(s.size()) - 1) 63 ok &= (abs(s[i] - s[i + 1]) != 1); 64 return ok; 65 } 66 67 int main() { 68 int T; 69 scanf("%d", &T); 70 static char buf[120]; 71 forn(_, T){ 72 scanf("%s", buf); 73 string s = buf; 74 string odd = "", even = ""; 75 forn(i, s.size()){ 76 if (s[i] % 2 == 0) 77 odd += s[i]; 78 else 79 even += s[i]; 80 } 81 sort(odd.begin(), odd.end()); 82 sort(even.begin(), even.end()); 83 if (check(odd + even)) 84 printf("%s\n", (odd + even).c_str()); 85 else if (check(even + odd)) 86 printf("%s\n", (even + odd).c_str()); 87 else 88 puts("No answer"); 89 } 90 return 0; 91 } 92 ``` 93 94 [1156C - Match Points](/contest/1156/problem/C "Educational Codeforces Round 64 (Rated for Div. 2)") 95 96 **Tutorial** 97 98 Tutorial is loading... 99 100 **Solution (BledDest)** 101 102 ``` 103 #include<bits/stdc++.h> 104 105 using namespace std; 106 107 const int N = 200043; 108 109 int n, z; 110 int a[N]; 111 112 int main() 113 { 114 scanf("%d", &n); 115 scanf("%d", &z); 116 for(int i = 0; i < n; i++) 117 scanf("%d", &a[i]); 118 sort(a, a + n); 119 int l = 0; 120 int r = n / 2 + 1; 121 while(r - l > 1) 122 { 123 int m = (l + r) / 2; 124 bool good = true; 125 for(int i = 0; i < m; i++) 126 good &= (a[n - m + i] - a[i] >= z); 127 if(good) 128 l = m; 129 else 130 r = m; 131 } 132 cout << l << endl; 133 } 134 ``` 135 136 [1156D - 0-1-Tree](/contest/1156/problem/D "Educational Codeforces Round 64 (Rated for Div. 2)") 137 138 **Tutorial** 139 140 Tutorial is loading... 141 142 **Solution (BledDest)** 143 144 ``` 145 #include<bits/stdc++.h> 146 147 using namespace std; 148 149 const int N = 200043; 150 151 int p[2][N]; 152 int siz[2][N]; 153 154 int get(int x, int c) 155 { 156 if(p[c][x] == x) 157 return x; 158 return p[c][x] = get(p[c][x], c); 159 } 160 161 void merge(int x, int y, int c) 162 { 163 x = get(x, c); 164 y = get(y, c); 165 if(siz[c][x] < siz[c][y]) 166 swap(x, y); 167 p[c][y] = x; 168 siz[c][x] += siz[c][y]; 169 } 170 171 int main() 172 { 173 int n; 174 scanf("%d", &n); 175 for(int i = 0; i < n; i++) 176 { 177 p[0][i] = p[1][i] = i; 178 siz[0][i] = siz[1][i] = 1; 179 } 180 for(int i = 0; i < n - 1; i++) 181 { 182 int x, y, c; 183 scanf("%d %d %d", &x, &y, &c); 184 --x; 185 --y; 186 merge(x, y, c); 187 } 188 long long ans = 0; 189 for(int i = 0; i < n; i++) 190 { 191 if(p[0][i] == i) 192 ans += siz[0][i] * 1ll * (siz[0][i] - 1); 193 if(p[1][i] == i) 194 ans += siz[1][i] * 1ll * (siz[1][i] - 1); 195 ans += (siz[0][get(i, 0)] - 1) * 1ll * (siz[1][get(i, 1)] - 1); 196 } 197 cout << ans << endl; 198 } 199 ``` 200 201 [1156E - Special Segments of Permutation](/contest/1156/problem/E "Educational Codeforces Round 64 (Rated for Div. 2)") 202 203 **Tutorial** 204 205 Tutorial is loading... 206 207 **Solution (BledDest)** 208 209 ``` 210 #include<bits/stdc++.h> 211 212 using namespace std; 213 214 const int N = 200043; 215 216 int lf[N]; 217 int rg[N]; 218 int n; 219 int ans = 0; 220 int p[N]; 221 int q[N]; 222 223 void update(int l, int r, int l2, int r2, int sum) 224 { 225 for(int i = l; i <= r; i++) 226 { 227 int o = sum - p[i]; 228 if(o >= 1 && o <= n && l2 <= q[o] && q[o] <= r2) 229 ans++; 230 } 231 } 232 233 int main() 234 { 235 scanf("%d", &n); 236 for(int i = 0; i < n; i++) 237 { 238 scanf("%d", &p[i]); 239 q[p[i]] = i; 240 } 241 stack<pair<int, int> > s; 242 s.push(make_pair(n + 1, -1)); 243 for(int i = 0; i < n; i++) 244 { 245 while(s.top().first < p[i]) 246 s.pop(); 247 lf[i] = s.top().second; 248 s.push(make_pair(p[i], i)); 249 } 250 while(!s.empty()) 251 s.pop(); 252 s.push(make_pair(n + 1, n)); 253 for(int i = n - 1; i >= 0; i--) 254 { 255 while(s.top().first < p[i]) 256 s.pop(); 257 rg[i] = s.top().second; 258 s.push(make_pair(p[i], i)); 259 } 260 for(int i = 0; i < n; i++) 261 { 262 // cerr << i << " " << lf[i] << " " << rg[i] << endl; 263 int lenl = i - lf[i] - 1; 264 int lenr = rg[i] - i - 1; 265 if(lenl == 0 || lenr == 0) 266 continue; 267 if(lenl < lenr) 268 update(lf[i] + 1, i - 1, i + 1, rg[i] - 1, p[i]); 269 else 270 update(i + 1, rg[i] - 1, lf[i] + 1, i - 1, p[i]); 271 } 272 cout << ans << endl; 273 } 274 ``` 275 276 [1156F - Card Bag](/contest/1156/problem/F "Educational Codeforces Round 64 (Rated for Div. 2)") 277 278 **Tutorial** 279 280 Tutorial is loading... 281 282 **Solution (Roms)** 283 284 ``` 285 #include<bits/stdc++.h> 286 287 using namespace std; 288 289 const int MOD = 998244353; 290 const int N = 5005; 291 292 void upd(int &a, int b){ 293 a += b; 294 a %= MOD; 295 } 296 297 int mul(int a, int b){ 298 return (a * 1LL * b) % MOD; 299 } 300 301 int bp(int a, int n){ 302 int res = 1; 303 for(; n > 0; n >>= 1){ 304 if(n & 1) res = mul(res, a); 305 a = mul(a, a); 306 } 307 return res; 308 } 309 310 int getInv(int a){ 311 int ia = bp(a, MOD - 2); 312 assert(mul(a, ia) == 1); 313 return ia; 314 } 315 316 int n; 317 int cnt[N]; 318 int suf[N]; 319 int dp[N][N]; 320 int sum[N][N]; 321 int inv[N]; 322 323 int main(){ 324 for(int i = 1; i < N; ++i) 325 inv[i] = getInv(i); 326 327 cin >> n; 328 for(int i = 0; i < n; ++i){ 329 int x; 330 cin >> x; 331 ++cnt[x]; 332 } 333 cnt[0] = 1; 334 for(int i = N - 2; i >= 0; --i) 335 suf[i] = suf[i + 1] + cnt[i]; 336 337 for(int x = n; x >= 0; --x) 338 for(int y = n; y >= 0; --y){ 339 if(cnt[x] == 0){ 340 upd(sum[x][y], sum[x + 1][y]); 341 continue; 342 } 343 int s = n - y; 344 if(s <= 0){ 345 upd(sum[x][y], sum[x + 1][y]); 346 continue; 347 } 348 349 upd(dp[x][y], mul(cnt[x] - 1, inv[s])); 350 upd(dp[x][y], mul(sum[x + 1][y + 1], inv[s])); 351 352 upd(sum[x][y], sum[x + 1][y]); 353 upd(sum[x][y], mul(cnt[x], dp[x][y])); 354 } 355 356 cout << dp[0][0] << endl; 357 return 0; 358 } 359 ``` 360 361 [1156G - Optimizer](/contest/1156/problem/G "Educational Codeforces Round 64 (Rated for Div. 2)") 362 363 **Tutorial** 364 365 Tutorial is loading... 366 367 **Solution (e-maxx)** 368 369 [Solution](https://codeforces.com/contest/1156/submission/53641770) described in a tutorial. 370 371 Jury's solution: 372 373 ``` 374 #include <algorithm> 375 #include <iostream> 376 #include <map> 377 #include <string> 378 #include <vector> 379 380 using namespace std; 381 382 struct expr { 383 string t; // variable name or operation 384 expr * l, * r; // only if operation 385 long long hash; 386 387 expr (string var) 388 : t(var), l(0), r(0), hash(0) 389 { } 390 expr (char op, expr * l, expr * r) 391 : t(1,op), l(l), r(r), hash(0) 392 { } 393 394 long long calc_hash() { 395 if (!hash) 396 if (!l) { 397 long long pw = 257; 398 for (size_t i=0; i<t.length(); ++i, pw*=97) 399 hash += t[i] * pw; 400 } 401 else 402 hash += l->calc_hash() * t[0] + r->calc_hash() * 31; 403 return hash; 404 } 405 }; 406 407 map<string,expr*> var; 408 409 void inc_var_name (string & cur) { 410 for (size_t i=cur.length()-1; ; --i) 411 if (cur[i] < 'z') { 412 ++cur[i]; 413 break; 414 } 415 else 416 cur[i] = 'a'; 417 } 418 419 string generate_var() { 420 static string cur = "aaaa"; 421 while (var.count(cur)) 422 inc_var_name (cur); 423 string res = cur; 424 inc_var_name (cur); 425 return res; 426 } 427 428 vector<string> ans; 429 map<long long,string> calced; 430 431 string restore (expr * e, string name = "") { 432 if (!e->l) return e->t; 433 long long h = e->calc_hash(); 434 if (calced.count(h)) return calced[h]; 435 string l = restore (e->l), r = restore (e->r); 436 string my = name.empty() ? generate_var() : name; 437 calced[h] = my; 438 ans.push_back (my + "=" + l + e->t + r); 439 return my; 440 } 441 442 int main() { 443 int n; 444 scanf ("%d\n", &n); 445 for (int i=0; i<n; ++i) { 446 static char buf[100]; 447 gets (buf); 448 string s = buf; 449 450 size_t pos1 = s.find ('='), pos2 = s.find_first_of ("&^$#"); 451 string lname = s.substr (0, pos1); 452 string r1name = s.substr (pos1 + 1, pos2 - pos1 - 1); 453 if (!var.count(r1name)) 454 var[r1name] = new expr (r1name); 455 if (pos2 != -1) { 456 string r2name = s.substr (pos2 + 1); 457 if (!var.count(r2name)) 458 var[r2name] = new expr (r2name); 459 var[lname] = new expr (s [ s.find_first_of ("&^$#") ], var[r1name], var[r2name]); 460 } 461 else 462 var[lname] = var[r1name]; 463 } 464 465 if (!var.count("res")) { 466 cout << 0; 467 return 0; 468 } 469 470 string name = restore (var["res"], "res"); 471 if (name != "res") 472 ans.push_back ("res=" + name); 473 474 cout << ans.size() << endl; 475 for (size_t i=0; i<ans.size(); ++i) 476 puts (ans[i].c_str()); 477 478 } 479 ```