1538.md (9242B)
1 Source: https://codeforces.com/blog/entry/91637 2 3 [1538A - Stone Game](/contest/1538/problem/A "Codeforces Round 725 (Div. 3)") 4 5 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 #include "random" 16 17 using namespace std; 18 19 using ll = long long; 20 using ld = long double; 21 using pii = pair<int, int>; 22 using cd = complex<ld>; 23 24 void solve() { 25 int n; 26 cin >> n; 27 vector<int> v(n); 28 for (int &e : v) { 29 cin >> e; 30 } 31 int maxPos = max_element(v.begin(), v.end()) - v.begin(); 32 int minPos = min_element(v.begin(), v.end()) - v.begin(); 33 cout << min({ 34 max(maxPos, minPos) + 1, 35 (n - 1) - min(maxPos, minPos) + 1, 36 (n - 1) - maxPos + minPos + 2, 37 (n - 1) - minPos + maxPos + 2 38 }) << "\n"; 39 } 40 41 int main() { 42 ios_base::sync_with_stdio(false); 43 cin.tie(nullptr); 44 int t; 45 cin >> t; 46 while (t--) { 47 solve(); 48 } 49 } 50 ``` 51 52 [1538B - Friends and Candies](/contest/1538/problem/B "Codeforces Round 725 (Div. 3)") 53 54 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 55 56 **Tutorial** 57 58 Tutorial is loading... 59 60 **Solution** 61 62 ``` 63 #include <bits/stdc++.h> 64 65 using namespace std; 66 67 using ll = long long; 68 using ld = long double; 69 using pii = pair<int, int>; 70 using cd = complex<ld>; 71 72 void solve() { 73 int n; 74 cin >> n; 75 vector<int> a(n); 76 int s = 0; 77 for (int i = 0; i < n; i++) { 78 cin >> a[i]; 79 s += a[i]; 80 } 81 if (s % n != 0) { 82 cout << "-1" << endl; 83 return; 84 } 85 s /= n; 86 int res = 0; 87 for (int i = 0; i < n; i++) { 88 if (s < a[i]) { 89 res++; 90 } 91 } 92 cout << res << endl; 93 } 94 95 int main() { 96 int t; 97 cin >> t; 98 while (t--) { 99 solve(); 100 } 101 return 0; 102 } 103 ``` 104 105 [1538C - Number of Pairs](/contest/1538/problem/C "Codeforces Round 725 (Div. 3)") 106 107 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 108 109 **Tutorial** 110 111 Tutorial is loading... 112 113 **Solution** 114 115 ``` 116 #include <bits/stdc++.h> 117 #include "random" 118 119 using namespace std; 120 121 using ll = long long; 122 using ld = long double; 123 using pii = pair<int, int>; 124 using cd = complex<ld>; 125 126 void solve() { 127 int n, l, r; 128 cin >> n >> l >> r; 129 vector<int> v(n); 130 for (int &e : v) { 131 cin >> e; 132 } 133 sort(v.begin(), v.end()); 134 ll ans = 0; 135 for (int i = 0; i < n; i++) { 136 ans += upper_bound(v.begin(), v.end(), r - v[i]) - v.begin(); 137 ans -= lower_bound(v.begin(), v.end(), l - v[i]) - v.begin(); 138 if (l <= 2 * v[i] && 2 * v[i] <= r) { 139 ans--; 140 } 141 } 142 cout << ans / 2 << "\n"; 143 } 144 145 int main() { 146 ios_base::sync_with_stdio(false); 147 cin.tie(nullptr); 148 int t; 149 cin >> t; 150 while (t--) { 151 solve(); 152 } 153 } 154 ``` 155 156 [1538D - Another Problem About Dividing Numbers](/contest/1538/problem/D "Codeforces Round 725 (Div. 3)") 157 158 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 159 160 **Tutorial** 161 162 Tutorial is loading... 163 164 **Solution** 165 166 ``` 167 #include <bits/stdc++.h> 168 169 using namespace std; 170 171 using ll = long long; 172 using ld = long double; 173 using pii = pair<int, int>; 174 using cd = complex<ld>; 175 176 const int N = 50'000; 177 178 bool isPrime[N]; 179 vector<int> primes; 180 181 void precalc() { 182 fill(isPrime + 2, isPrime + N, true); 183 for (int i = 2; i * i < N; i++) { 184 for (int j = i * i; j < N; j += i) { 185 isPrime[j] = false; 186 } 187 } 188 for (int i = 2; i < N; i++) { 189 if (isPrime[i]) { 190 primes.push_back(i); 191 } 192 } 193 } 194 195 int calcPrime(int n) { 196 int res = 0; 197 for (int i : primes) { 198 if (i * i > n) { 199 break; 200 } 201 while (n % i == 0) { 202 n /= i; 203 res++; 204 } 205 } 206 if (n > 1) { 207 res++; 208 } 209 return res; 210 } 211 212 map<int, int> decompose(int n) { 213 map<int, int> a; 214 for (int i : primes) { 215 if (i * i > n) { 216 break; 217 } 218 int p = 0; 219 while (n % i == 0) { 220 n /= i; 221 p++; 222 } 223 if (p > 0) { 224 a[i] = p; 225 } 226 } 227 if (n > 1) { 228 a[n] = 1; 229 } 230 return a; 231 } 232 233 bool check(const map<int, int> &divs, 234 map<int, int>::const_iterator it, 235 map<int, int> &divsA, 236 map<int, int> &divsB, 237 int low, 238 int high, 239 int k) { 240 if (it == divs.end()) { 241 return __builtin_popcount(low) <= k && k <= high; 242 } 243 for (int p = 0; p <= it->second; p++) { 244 int pa = divsA[it->first]; 245 int pb = divsB[it->first]; 246 int nextLow = low; 247 if (p != pa) { 248 nextLow |= 1; 249 } 250 if (p != pb) { 251 nextLow |= 2; 252 } 253 if (check(divs, next(it), divsA, divsB, nextLow, high + pa + pb - 2 * p, k)) { 254 return true; 255 } 256 } 257 return false; 258 } 259 260 void solve() { 261 int a, b, k; 262 cin >> a >> b >> k; 263 int g = __gcd(a, b); 264 int low = 0; 265 int high = 0; 266 { 267 int t; 268 int ta = 1; 269 while ((t = __gcd(a, g)) != 1) { 270 a /= t; 271 ta *= t; 272 } 273 high += calcPrime(a); 274 if (a != 1) { 275 low |= 1; 276 } 277 a = ta; 278 } 279 { 280 int t; 281 int tb = 1; 282 while ((t = __gcd(b, g)) != 1) { 283 b /= t; 284 tb *= t; 285 } 286 high += calcPrime(b); 287 if (b != 1) { 288 low |= 2; 289 } 290 b = tb; 291 } 292 auto divs = decompose(g); 293 auto divsA = decompose(a); 294 auto divsB = decompose(b); 295 cout << (check(divs, divs.begin(), divsA, divsB, low, high, k) ? "YES" : "NO") << endl; 296 } 297 298 int main() { 299 precalc(); 300 301 int t; 302 cin >> t; 303 while (t--) { 304 solve(); 305 } 306 307 return 0; 308 } 309 ``` 310 311 [1538E - Funny Substrings](/contest/1538/problem/E "Codeforces Round 725 (Div. 3)") 312 313 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 314 315 **Tutorial** 316 317 Tutorial is loading... 318 319 **Solution** 320 321 ``` 322 #include <bits/stdc++.h> 323 #include "random" 324 325 using namespace std; 326 327 using ll = long long; 328 using ld = long double; 329 using pii = pair<int, int>; 330 using cd = complex<ld>; 331 332 vector<string> split(const string& s, char p) { 333 vector<string> res(1); 334 for (char c : s) { 335 if (c == p) { 336 res.emplace_back(); 337 } else { 338 res.back() += c; 339 } 340 } 341 return res; 342 } 343 344 struct Word { 345 ll len; 346 ll cnt; 347 string s; 348 }; 349 350 string getFirst(string s) { 351 if (s.size() < 3) { 352 return s; 353 } 354 return s.substr(0, 3); 355 } 356 357 string getLast(string s) { 358 if (s.size() < 3) { 359 return s; 360 } 361 return s.substr(s.size() - 3, 3); 362 } 363 364 int count(const string& s, const string& p) { 365 int cnt = 0; 366 for (int i = 0; i + p.size() <= s.size(); i++) { 367 if (s.substr(i, p.size()) == p) { 368 cnt++; 369 } 370 } 371 return cnt; 372 } 373 374 Word merge(const Word& a, const Word& b) { 375 Word c; 376 c.len = a.len + b.len; 377 c.s = a.s + b.s; 378 c.cnt = a.cnt + b.cnt + count(getLast(a.s) + getFirst(b.s), "haha"); 379 if (c.s.size() >= 7) { 380 c.s = getFirst(c.s) + "@" + getLast(c.s); 381 } 382 return c; 383 } 384 385 void solve() { 386 int n; 387 cin >> n; 388 map<string, Word> vars; 389 ll ans = 0; 390 for (int i = 0; i < n; i++) { 391 string var; 392 cin >> var; 393 string opr; 394 cin >> opr; 395 if (opr == "=") { 396 string a, plus, b; 397 cin >> a >> plus >> b; 398 vars[var] = merge(vars[a], vars[b]); 399 } else { 400 string str; 401 cin >> str; 402 Word word; 403 word.len = str.length(); 404 word.cnt = count(str, "haha"); 405 word.s = str; 406 vars[var] = word; 407 } 408 ans = vars[var].cnt; 409 } 410 cout << ans << "\n"; 411 } 412 413 int main() { 414 ios_base::sync_with_stdio(false); 415 cin.tie(nullptr); 416 int t; 417 cin >> t; 418 while (t--) { 419 solve(); 420 } 421 } 422 ``` 423 424 [1538F - Interesting Function](/contest/1538/problem/F "Codeforces Round 725 (Div. 3)") 425 426 Author: [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz"), [Stepavly](/profile/Stepavly "Candidate Master Stepavly") 427 428 **Tutorial** 429 430 Tutorial is loading... 431 432 **Solution** 433 434 ``` 435 #include <iostream> 436 437 using namespace std; 438 439 void solve () { 440 int L, R; 441 cin >> L >> R; 442 443 int ans = 0; 444 while (L != 0 || R != 0) { 445 ans += R - L; 446 L /= 10; 447 R /= 10; 448 } 449 cout << ans << '\n'; 450 } 451 452 int main () { 453 ios::sync_with_stdio(false); 454 cin.tie(0); 455 456 int testc; 457 cin >> testc; 458 459 for (int i = 0; i < testc; i++) { 460 solve(); 461 } 462 } 463 ``` 464 465 [1538G - Gift Set](/contest/1538/problem/G "Codeforces Round 725 (Div. 3)") 466 467 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 468 469 **Tutorial** 470 471 Tutorial is loading... 472 473 **Solution** 474 475 ``` 476 #include <bits/stdc++.h> 477 #include "random" 478 479 using namespace std; 480 481 using ll = long long; 482 using ld = long double; 483 using pii = pair<int, int>; 484 using cd = complex<ld>; 485 486 void solve() { 487 ll x, y, a, b; 488 cin >> x >> y >> a >> b; 489 ll l = 0, r = 1e9 + 100; 490 if (a == b) { 491 cout << min(x, y) / a << "\n"; 492 return; 493 } 494 if (a < b) { 495 swap(a, b); 496 } 497 while (r - l > 1) { 498 ll m = (l + r) / 2; 499 ll right = floorl((x - m * b) * 1.0l / (a - b)); 500 ll left = ceill((y - m * a) * 1.0l / (b - a)); 501 if (max(left, 0ll) <= min(right, m)) { 502 l = m; 503 } else { 504 r = m; 505 } 506 } 507 cout << l << "\n"; 508 } 509 510 int main() { 511 ios_base::sync_with_stdio(false); 512 cin.tie(nullptr); 513 int t; 514 cin >> t; 515 while (t--) { 516 solve(); 517 } 518 } 519 ```