1743.md (9034B)
1 Source: https://codeforces.com/blog/entry/108153 2 3 [1743A - Password](/contest/1743/problem/A "Educational Codeforces Round 137 (Rated for Div. 2)") 4 5 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution 1 (awoo)** 12 13 ``` 14 for _ in range(int(input())): 15 n = int(input()) 16 a = set(map(int, input().split())) 17 ans = 0 18 for i in range(10000): 19 num = str(i) 20 num = (4 - len(num)) * '0' + num 21 used = set(num) 22 if len(used) != 2: 23 continue 24 d1 = int(used.pop()) 25 d2 = int(used.pop()) 26 if (not d1 in a) and (not d2 in a) and num.count(num[0]) == 2: 27 ans += 1 28 print(ans) 29 ``` 30 31 **Solution 2 (fcspartakm)** 32 33 ``` 34 #include <bits/stdc++.h> 35 36 using namespace std; 37 38 int n; 39 40 inline void read() { 41 cin >> n; 42 int x; 43 for (int i = 0; i < n; ++i) 44 cin >> x; 45 } 46 47 inline int fac(int n) { 48 int res = 1; 49 for (int i = 2; i <= n; i++) { 50 res *= i; 51 } 52 return res; 53 } 54 55 inline int c(int n, int k) { 56 return fac(n) / fac(k) / fac(n - k); 57 } 58 59 inline void solve() { 60 cout << c(10 - n, 2) * c(4, 2) << endl; 61 } 62 63 int main () { 64 int t; 65 cin >> t; 66 while (t--){ 67 read(); 68 solve(); 69 } 70 } 71 ``` 72 73 [1743B - Permutation Value](/contest/1743/problem/B "Educational Codeforces Round 137 (Rated for Div. 2)") 74 75 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 76 77 **Tutorial** 78 79 Tutorial is loading... 80 81 **Solution (BledDest)** 82 83 ``` 84 #include <bits/stdc++.h> 85 86 using namespace std; 87 88 void solve() 89 { 90 int n; 91 cin >> n; 92 cout << 1; 93 for(int i = n; i >= 2; i--) 94 cout << " " << i; 95 cout << endl; 96 } 97 98 int main() 99 { 100 int t; 101 cin >> t; 102 for(int i = 0; i < t; i++) 103 solve(); 104 } 105 ``` 106 107 [1743C - Save the Magazines](/contest/1743/problem/C "Educational Codeforces Round 137 (Rated for Div. 2)") 108 109 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm") 110 111 **Tutorial** 112 113 Tutorial is loading... 114 115 **Solution (awoo)** 116 117 ``` 118 for _ in range(int(input())): 119 n = int(input()) 120 s = '0' + input() 121 a = [0] + list(map(int, input().split())) 122 ans = 0 123 i = 0 124 while i <= n: 125 mn = a[i] 126 sm = a[i] 127 j = i + 1 128 while j <= n and s[j] == '1': 129 mn = min(mn, a[j]) 130 sm += a[j] 131 j += 1 132 ans += sm - mn 133 i = j 134 print(ans) 135 ``` 136 137 [1743D - Problem with Random Tests](/contest/1743/problem/D "Educational Codeforces Round 137 (Rated for Div. 2)") 138 139 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 140 141 **Tutorial** 142 143 Tutorial is loading... 144 145 **Solution (BledDest)** 146 147 ``` 148 #include<bits/stdc++.h> 149 150 using namespace std; 151 152 char buf[1000043]; 153 154 string normalize(const string& v) 155 { 156 int cnt = 0; 157 while(cnt < v.size() && v[cnt] == '0') cnt++; 158 if(cnt == v.size()) return "0"; 159 return v.substr(cnt, int(v.size()) - cnt); 160 } 161 162 string operator |(const string& a, const string& b) 163 { 164 int sz = max(a.size(), b.size()); 165 string ans(sz, '0'); 166 for(int i = 0; i < a.size(); i++) 167 if(a[i] == '1') ans[i + sz - int(a.size())] = '1'; 168 for(int i = 0; i < b.size(); i++) 169 if(b[i] == '1') ans[i + sz - int(b.size())] = '1'; 170 return normalize(ans); 171 } 172 173 bool better(const string& a, const string& b) 174 { 175 if(a.size() != b.size()) return a.size() > b.size(); 176 return a > b; 177 } 178 179 int main() 180 { 181 int n; 182 scanf("%d", &n); 183 string s; 184 scanf("%s", buf); 185 s = buf; 186 string ans = s | s; 187 int pos1 = s.find("1"); 188 if(pos1 != string::npos) 189 { 190 int pos2 = s.find("0", pos1); 191 if(pos2 != string::npos) 192 { 193 int cur = pos1; 194 int not_needed = 0; 195 while(true) 196 { 197 if(cur == n || (s[cur] == '1' && cur > pos2)) break; 198 string nw = s | s.substr(pos1, n - pos1 - not_needed); 199 if(better(nw, ans)) ans = nw; 200 cur++; 201 not_needed++; 202 } 203 } 204 } 205 puts(ans.c_str()); 206 } 207 ``` 208 209 [1743E - FTL](/contest/1743/problem/E "Educational Codeforces Round 137 (Rated for Div. 2)") 210 211 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 212 213 **Tutorial** 214 215 Tutorial is loading... 216 217 **Solution (awoo)** 218 219 ``` 220 #include <bits/stdc++.h> 221 222 #define forn(i, n) for (int i = 0; i < int(n); i++) 223 224 using namespace std; 225 226 const long long INF64 = 1e18; 227 228 int main() { 229 vector<int> ps(2); 230 vector<long long> ts(2); 231 int h, s; 232 forn(i, 2) scanf("%d%lld", &ps[i], &ts[i]); 233 scanf("%d%d", &h, &s); 234 long long ans = INF64; 235 vector<long long> dp(h + 1, INF64); 236 dp[0] = 0; 237 forn(i, h) for (int j = 1; j <= h - i; ++j) forn(k, 2){ 238 int ni = min((long long)h, i + j * (ps[k] - s) + j * ts[k] / ts[k ^ 1] * (ps[k ^ 1] - s)); 239 if (ni == h) 240 ans = min(ans, dp[i] + j * ts[k]); 241 if (j * ts[k] >= ts[k ^ 1]){ 242 ni = min((long long)h, i + (j - 1) * (ps[k] - s) + (j * ts[k] / ts[k ^ 1] - 1) * (ps[k ^ 1] - s) + (ps[0] + ps[1] - s)); 243 dp[ni] = min(dp[ni], dp[i] + j * ts[k]); 244 } 245 } 246 ans = min(ans, dp[h]); 247 printf("%lld\n", ans); 248 } 249 ``` 250 251 [1743F - Intersection and Union](/contest/1743/problem/F "Educational Codeforces Round 137 (Rated for Div. 2)") 252 253 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 254 255 **Tutorial** 256 257 Tutorial is loading... 258 259 **Solution (BledDest)** 260 261 ``` 262 #include<bits/stdc++.h> 263 264 using namespace std; 265 266 const int N = 300043; 267 268 typedef array<int, 2> vec; 269 typedef array<vec, 2> mat; 270 271 const int MOD = 998244353; 272 273 mat operator*(const mat& a, const mat& b) 274 { 275 mat c; 276 for(int i = 0; i < 2; i++) 277 for(int j = 0; j < 2; j++) 278 c[i][j] = 0; 279 for(int i = 0; i < 2; i++) 280 for(int j = 0; j < 2; j++) 281 for(int k = 0; k < 2; k++) 282 c[i][k] = (a[i][j] * 1ll * b[j][k] + c[i][k]) % MOD; 283 return c; 284 } 285 286 mat ZERO = {vec({3, 0}), vec({1, 2})}; 287 mat ONE = {vec({1, 2}), vec({1, 2})}; 288 289 mat t[4 * N]; 290 291 void recalc(int v) 292 { 293 t[v] = t[v * 2 + 1] * t[v * 2 + 2]; 294 } 295 296 void build(int v, int l, int r) 297 { 298 if(l == r - 1) 299 { 300 t[v] = ZERO; 301 } 302 else 303 { 304 int m = (l + r) / 2; 305 build(v * 2 + 1, l, m); 306 build(v * 2 + 2, m, r); 307 recalc(v); 308 } 309 } 310 311 void upd(int v, int l, int r, int pos, int val) 312 { 313 if(l == r - 1) 314 { 315 if(val == 0) t[v] = ZERO; 316 else t[v] = ONE; 317 } 318 else 319 { 320 int m = (l + r) / 2; 321 if(pos < m) upd(v * 2 + 1, l, m, pos, val); 322 else upd(v * 2 + 2, m, r, pos, val); 323 recalc(v); 324 } 325 } 326 327 int main() 328 { 329 ios_base::sync_with_stdio(0); 330 cin.tie(0); 331 int n; 332 cin >> n; 333 vector<vector<pair<int, int>>> v(N); 334 for(int i = 0; i < n; i++) 335 { 336 int l, r; 337 cin >> l >> r; 338 v[l].push_back(make_pair(1, i)); 339 v[r + 1].push_back(make_pair(0, i)); 340 } 341 build(0, 0, n - 1); 342 int cur = 0; 343 int ans = 0; 344 for(int i = 0; i <= 300000; i++) 345 { 346 for(auto x : v[i]) 347 { 348 if(x.second == 0) cur = x.first; 349 else upd(0, 0, n - 1, x.second - 1, x.first); 350 } 351 ans = (ans + t[0][cur][1]) % MOD; 352 } 353 cout << ans << endl; 354 } 355 ``` 356 357 [1743G - Antifibonacci Cut](/contest/1743/problem/G "Educational Codeforces Round 137 (Rated for Div. 2)") 358 359 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 360 361 **Tutorial** 362 363 Tutorial is loading... 364 365 **Solution (BledDest)** 366 367 ``` 368 #include<bits/stdc++.h> 369 370 using namespace std; 371 372 const int MOD = 998244353; 373 374 int add(int x, int y) 375 { 376 x += y; 377 while(x >= MOD) x -= MOD; 378 while(x < 0) x += MOD; 379 return x; 380 } 381 382 int sub(int x, int y) 383 { 384 return add(x, MOD - y); 385 } 386 387 int expected(int mask) 388 { 389 if(mask & 2) return 0; 390 return 1; 391 } 392 393 int last_bit(int x) 394 { 395 if(x == 0) return -1; 396 return x - (x & (x - 1)); 397 } 398 399 bool go(int& a, int x) 400 { 401 if(expected(a) != x) 402 { 403 a = 1 << x; 404 return false; 405 } 406 a ^= (1 << x); 407 while(true) 408 { 409 int b = last_bit(a); 410 int c = last_bit(a - b); 411 if(c == 2 * b) a += b; 412 else break; 413 } 414 return true; 415 } 416 417 bool is_fib(int a) 418 { 419 return a == last_bit(a); 420 } 421 422 vector<pair<int, int>> go(const vector<pair<int, int>>& a, int x) 423 { 424 vector<pair<int, int>> nw; 425 for(auto b : a) 426 { 427 int cost = b.first; 428 int seqn = b.second; 429 if(go(seqn, x)) nw.push_back(make_pair(cost, seqn)); 430 } 431 return nw; 432 } 433 434 int main() 435 { 436 ios_base::sync_with_stdio(0); 437 cin.tie(0); 438 int last = 1, sum = 1; 439 vector<pair<int, int>> w; 440 int n; 441 cin >> n; 442 for(int i = 0; i < n; i++) 443 { 444 string s; 445 cin >> s; 446 for(auto x : s) 447 { 448 int c = x - '0'; 449 int ndp = sub(sum, last); 450 w = go(w, c); 451 for(int j = 0; j < w.size(); j++) 452 { 453 if(is_fib(w[j].second)) 454 ndp = sub(ndp, w[j].first); 455 } 456 if(c == 1) w.push_back(make_pair(last, 2)); 457 sum = add(sum, ndp); 458 last = ndp; 459 assert(w.size() <= 60); 460 } 461 cout << last << endl; 462 } 463 } 464 ```