1194.md (10320B)
1 Source: https://codeforces.com/blog/entry/68405 2 3 [1194A - Remove a Progression](/contest/1194/problem/A "Educational Codeforces Round 68 (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 fun main(args: Array<String>) { 15 val T = readLine()!!.toInt() 16 for (t in 1..T) { 17 val (n, x) = readLine()!!.split(' ').map { it.toLong() } 18 println(x * 2) 19 } 20 } 21 ``` 22 23 [1194B - Yet Another Crosses Problem](/contest/1194/problem/B "Educational Codeforces Round 68 (Rated for Div. 2)") 24 25 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 26 27 **Tutorial** 28 29 Tutorial is loading... 30 31 **Solution (PikMike)** 32 33 ``` 34 #include <bits/stdc++.h> 35 36 #define forn(i, n) for (int i = 0; i < int(n); i++) 37 38 using namespace std; 39 40 int main() { 41 int q; 42 cin >> q; 43 forn(_, q){ 44 int n, m; 45 cin >> n >> m; 46 vector<string> s(n); 47 forn(i, n) 48 cin >> s[i]; 49 vector<int> cntn(n), cntm(m); 50 forn(i, n) forn(j, m){ 51 cntn[i] += (s[i][j] == '.'); 52 cntm[j] += (s[i][j] == '.'); 53 } 54 int ans = n + m; 55 forn(i, n) forn(j, m){ 56 ans = min(ans, cntn[i] + cntm[j] - (s[i][j] == '.')); 57 } 58 cout << ans << "\n"; 59 } 60 return 0; 61 } 62 ``` 63 64 [1194C - From S To T](/contest/1194/problem/C "Educational Codeforces Round 68 (Rated for Div. 2)") 65 66 Idea: [Roms](/profile/Roms "Master Roms") 67 68 **Tutorial** 69 70 Tutorial is loading... 71 72 **Solution (Roms)** 73 74 ``` 75 #include <bits/stdc++.h> 76 77 using namespace std; 78 79 int q; 80 string s, t, p; 81 int cnt[30]; 82 83 int main() { 84 cin >> q; 85 for(int iq = 0; iq < q; ++iq){ 86 cin >> s >> t >> p; 87 memset(cnt, 0, sizeof cnt); 88 for(auto x : p) 89 ++cnt[x - 'a']; 90 91 bool ok = true; 92 int is = 0, it = 0; 93 while(is < s.size()){ 94 if(it == t.size()){ 95 ok = false; 96 break; 97 } 98 99 if(s[is] == t[it]){ 100 ++is, ++it; 101 continue; 102 } 103 104 --cnt[t[it] - 'a']; 105 ++it; 106 } 107 while(it < t.size()){ 108 --cnt[t[it] - 'a']; 109 ++it; 110 } 111 112 if(*min_element(cnt, cnt + 30) < 0) 113 ok = false; 114 115 if(ok) cout << "YES\n"; 116 else cout << "NO\n"; 117 } 118 return 0; 119 } 120 121 } 122 ``` 123 124 [1194D - 1-2-K Game](/contest/1194/problem/D "Educational Codeforces Round 68 (Rated for Div. 2)") 125 126 Idea: [adedalic](/profile/adedalic "International Master adedalic") 127 128 **Tutorial** 129 130 Tutorial is loading... 131 132 **Solution (adedalic)** 133 134 ``` 135 #include <bits/stdc++.h> 136 using namespace std; 137 138 int n, k; 139 140 inline bool read() { 141 if(!(cin >> n >> k)) 142 return false; 143 return true; 144 } 145 146 void solve() { 147 bool win = true; 148 if(k % 3 == 0) { 149 int np = n % (k + 1); 150 if(np % 3 == 0 && np != k) 151 win = false; 152 } else { 153 int np = n % 3; 154 if(np == 0) 155 win = false; 156 } 157 158 puts(win ? "Alice" : "Bob"); 159 } 160 161 int main(){ 162 int T; cin >> T; 163 while(T--) { 164 read(); 165 solve(); 166 } 167 return 0; 168 } 169 ``` 170 171 [1194E - Count The Rectangles](/contest/1194/problem/E "Educational Codeforces Round 68 (Rated for Div. 2)") 172 173 Idea: [adedalic](/profile/adedalic "International Master adedalic") 174 175 **Tutorial** 176 177 Tutorial is loading... 178 179 **Solution (Roms)** 180 181 ``` 182 #include <bits/stdc++.h> 183 184 using namespace std; 185 186 #define mp make_pair 187 188 const int N = 10009; 189 const int INF = 1000000009; 190 191 int n; 192 vector <pair<int, int> > vs[N], hs[N]; 193 int f[N]; 194 vector <int> d[N]; 195 196 void upd(int pos, int x){ 197 for(; pos < N; pos |= pos + 1) 198 f[pos] += x; 199 } 200 201 int get(int pos){ 202 int res = 0; 203 for(; pos >= 0; pos = (pos & (pos + 1)) - 1) 204 res += f[pos]; 205 return res; 206 } 207 208 int get(int l, int r){ 209 return get(r) - get(l - 1); 210 } 211 212 const int D = 5000; 213 214 int main() { 215 cin >> n; 216 for(int i = 0; i < n; ++i){ 217 int x1, y1, x2, y2; 218 cin >> x1 >> y1 >> x2 >> y2; 219 x1 += D, y1 += D, x2 += D, y2 += D; 220 if(y1 == y2) 221 hs[y1].push_back( mp(min(x1, x2), max(x1, x2)) ); 222 else 223 vs[x1].push_back( mp(min(y1, y2), max(y1, y2)) ); 224 } 225 226 long long res = 0; 227 for(int y = 0; y < N; ++y) for(auto s : hs[y]){ 228 for(int i = 0; i < N; ++i) d[i].clear(); 229 memset(f, 0, sizeof f); 230 231 int l = s.first, r = s.second; 232 for(int x = l; x <= r; ++x) for(auto s2 : vs[x]) 233 if(s2.first <= y && s2.second > y) { 234 d[s2.second].push_back(x); 235 upd(x, 1); 236 } 237 238 for(int y2 = y + 1; y2 < N; ++y2){ 239 for(auto s2 : hs[y2]){ 240 int cur = get(s2.first, s2.second); 241 res += cur * (cur - 1) / 2; 242 } 243 for(auto x : d[y2]) upd(x, -1); 244 } 245 } 246 247 cout << res << endl; 248 return 0; 249 } 250 ``` 251 252 [1194F - Crossword Expert](/contest/1194/problem/F "Educational Codeforces Round 68 (Rated for Div. 2)") 253 254 Idea: [adedalic](/profile/adedalic "International Master adedalic") 255 256 **Tutorial** 257 258 Tutorial is loading... 259 260 **Solution (adedalic)** 261 262 ``` 263 #include<bits/stdc++.h> 264 265 using namespace std; 266 267 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 268 #define sz(a) int((a).size()) 269 270 #define x first 271 #define y second 272 273 typedef long long li; 274 typedef pair<int, int> pt; 275 276 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 277 return out << "(" << p.x << ", " << p.y << ")"; 278 } 279 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 280 fore(i, 0, sz(v)) { 281 if(i) out << " "; 282 out << v[i]; 283 } 284 return out; 285 } 286 287 const int MOD = int(1e9) + 7; 288 289 inline int norm(int a) { 290 if(a >= MOD) a -= MOD; 291 if(a < 0) a += MOD; 292 return a; 293 } 294 inline int mul(int a, int b) { 295 return int(a * 1ll * b % MOD); 296 } 297 inline int binPow(int a, int k) { 298 int ans = 1; 299 while(k > 0) { 300 if(k & 1) ans = mul(ans, a); 301 a = mul(a, a); 302 k >>= 1; 303 } 304 return ans; 305 } 306 inline int inv(int a) { 307 return binPow(a, MOD - 2); 308 } 309 310 int n; 311 li T; 312 vector<li> t; 313 314 inline bool read() { 315 if(!(cin >> n >> T)) 316 return false; 317 t.resize(n); 318 fore(i, 0, n) 319 cin >> t[i]; 320 return true; 321 } 322 323 vector<int> f, inf; 324 325 int C(int n, li k) { 326 if(k > n || k < 0) 327 return 0; 328 return mul(f[n], mul(inf[k], inf[n - k])); 329 } 330 331 inline void solve() { 332 f.resize(n + 5); 333 inf.resize(n + 5); 334 f[0] = inf[0] = 1; 335 fore(i, 1, sz(f)) { 336 f[i] = mul(i, f[i - 1]); 337 inf[i] = mul(inf[i - 1], inv(i)); 338 } 339 340 int sumC = 1; 341 li bd = T; 342 int pw2 = 1, i2 = (MOD + 1) / 2; 343 344 vector<int> p(n + 1, 0); 345 fore(i, 0, n) { 346 pw2 = mul(pw2, i2); 347 348 sumC = norm(mul(2, sumC) - C(i, bd)); 349 li need = t[i]; 350 if(bd > i + 1) { 351 li sub = min(bd - i - 1, need); 352 bd -= sub, need -= sub; 353 } 354 li rem = min(bd + 1, need); 355 fore(k, 0, rem) 356 sumC = norm(sumC - C(i + 1, bd - k)); 357 bd -= rem; 358 359 p[i] = mul(sumC, pw2); 360 } 361 362 int ans = int(accumulate(p.begin(), p.end(), 0ll) % MOD); 363 cout << ans << endl; 364 // cerr << mul(ans, binPow(2, n)) << endl; 365 } 366 367 int main() { 368 #ifdef _DEBUG 369 freopen("input.txt", "r", stdin); 370 int tt = clock(); 371 #endif 372 cout << fixed << setprecision(15); 373 374 if(read()) { 375 solve(); 376 377 #ifdef _DEBUG 378 cerr << "TIME = " << clock() - tt << endl; 379 tt = clock(); 380 #endif 381 } 382 return 0; 383 } 384 ``` 385 386 [1194G - Another Meme Problem](/contest/1194/problem/G "Educational Codeforces Round 68 (Rated for Div. 2)") 387 388 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 389 390 **Tutorial** 391 392 Tutorial is loading... 393 394 **Solution (BledDest)** 395 396 ``` 397 #include<bits/stdc++.h> 398 399 using namespace std; 400 401 const int N = 105; 402 403 int a[N]; 404 int n; 405 int numPos[10], denPos[10]; 406 int num, den; 407 const int MOD = 998244353; 408 409 struct halfState 410 { 411 int carry; 412 int mask; 413 bool comp; 414 415 halfState() {}; 416 halfState(int carry, int mask, bool comp) : carry(carry), mask(mask), comp(comp) {}; 417 }; 418 419 bool operator <(const halfState& x, const halfState& y) 420 { 421 if(x.carry != y.carry) return x.carry < y.carry; 422 if(x.mask != y.mask) return x.mask < y.mask; 423 return x.comp < y.comp; 424 } 425 426 bool operator ==(const halfState& x, const halfState& y) 427 { 428 return x.carry == y.carry && x.mask == y.mask && x.comp == y.comp; 429 } 430 431 bool operator !=(const halfState& x, const halfState& y) 432 { 433 return x.carry != y.carry || x.mask != y.mask || x.comp != y.comp; 434 } 435 436 halfState go(const halfState& s, int pos, int digit, bool isNum) 437 { 438 int newDigit = digit * (isNum ? num : den) + s.carry; 439 int newCarry = newDigit / 10; 440 newDigit %= 10; 441 int newMask = s.mask; 442 int maskPos = (isNum ? numPos[newDigit] : denPos[newDigit]); 443 if(maskPos != -1) newMask |= (1 << maskPos); 444 bool newComp = (newDigit < a[pos]) || (newDigit == a[pos] && s.comp); 445 return halfState(newCarry, newMask, newComp); 446 } 447 448 struct state 449 { 450 halfState numState; 451 halfState denState; 452 453 state() {}; 454 state(halfState numState, halfState denState) : numState(numState), denState(denState) {}; 455 456 void norm() 457 { 458 if(numState.mask & denState.mask) 459 numState.mask = denState.mask = 1; 460 }; 461 462 bool valid() 463 { 464 return bool(numState.mask & denState.mask) && numState.comp && denState.comp && (numState.carry == 0) && (denState.carry == 0); 465 }; 466 }; 467 468 bool operator <(const state& x, const state& y) 469 { 470 if(x.numState != y.numState) return x.numState < y.numState; 471 return x.denState < y.denState; 472 } 473 474 state go(const state& s, int pos, int digit) 475 { 476 halfState newNum = go(s.numState, pos, digit, true); 477 halfState denNum = go(s.denState, pos, digit, false); 478 state res(newNum, denNum); 479 res.norm(); 480 return res; 481 } 482 483 int add(int x, int y) 484 { 485 return (x + y) % MOD; 486 } 487 488 int ans = 0; 489 490 void calcFixed(int x, int y) 491 { 492 num = x; 493 den = y; 494 for(int i = 0; i <= 9; i++) 495 numPos[i] = denPos[i] = -1; 496 int cnt = 0; 497 for(int i = 1; i <= 9; i++) 498 for(int j = 1; j <= 9; j++) 499 if(i * y == j * x) 500 { 501 numPos[i] = denPos[j] = cnt++; 502 } 503 vector<map<state, int> > dp(102); 504 dp[0][state(halfState(0, 0, true), halfState(0, 0, true))] = 1; 505 for(int i = 0; i <= 100; i++) 506 for(auto x : dp[i]) 507 { 508 state curState = x.first; 509 int curCount = x.second; 510 for(int j = 0; j <= 9; j++) 511 { 512 state newState = go(curState, i, j); 513 dp[i + 1][newState] = add(dp[i + 1][newState], curCount); 514 } 515 } 516 for(auto x : dp[101]) 517 { 518 state curState = x.first; 519 int curCount = x.second; 520 if(curState.valid()) 521 ans = add(ans, curCount); 522 } 523 } 524 525 int main() 526 { 527 string s; 528 cin >> s; 529 int len = s.size(); 530 reverse(s.begin(), s.end()); 531 for(int i = 0; i < len; i++) 532 { 533 a[i] = s[i] - '0'; 534 } 535 for(int i = 1; i <= 9; i++) 536 for(int j = 1; j <= 9; j++) 537 if(__gcd(i, j) == 1) 538 calcFixed(i, j); 539 cout << ans << endl; 540 } 541 ```