1593.md (8173B)
1 Source: https://codeforces.com/blog/entry/96034 2 3 [1593A - Elections](/contest/1593/problem/A "Codeforces Round 748 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int solveSingle(int best, int other1, int other2) 19 { 20 return max(0, max(other1, other2) + 1 - best); 21 } 22 23 int main() 24 { 25 int t; 26 cin >> t; 27 28 while (t--) 29 { 30 int a, b, c; 31 cin >> a >> b >> c; 32 33 cout << solveSingle(a, b, c) << ' ' << solveSingle(b, a, c) << ' ' << solveSingle(c, a, b) << '\n'; 34 } 35 36 return 0; 37 } 38 ``` 39 40 [1593B - Make it Divisible by 25](/contest/1593/problem/B "Codeforces Round 748 (Div. 3)") 41 42 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 43 44 **Tutorial** 45 46 Tutorial is loading... 47 48 **Solution** 49 50 ``` 51 #include <bits/stdc++.h> 52 53 using namespace std; 54 55 const string subseqs[] = { "00", "25", "50", "75" }; 56 57 const int INF = 100; 58 59 int solve(string& s, string& t) 60 { 61 int sptr = s.length() - 1; 62 63 int ans = 0; 64 while (sptr >= 0 && s[sptr] != t[1]) 65 { 66 sptr--; 67 ans++; 68 } 69 70 if (sptr < 0) return INF; 71 72 sptr--; 73 74 while (sptr >= 0 && s[sptr] != t[0]) 75 { 76 sptr--; 77 ans++; 78 } 79 80 return sptr < 0 ? INF : ans; 81 } 82 83 int main() 84 { 85 int t; 86 cin >> t; 87 88 while (t--) 89 { 90 string n; 91 cin >> n; 92 93 int ans = INF; 94 for (auto e : subseqs) 95 ans = min(ans, solve(n, e)); 96 97 cout << ans << '\n'; 98 } 99 100 return 0; 101 } 102 ``` 103 104 [1593C - Save More Mice](/contest/1593/problem/C "Codeforces Round 748 (Div. 3)") 105 106 Idea: ITMO student team 107 108 **Tutorial** 109 110 Tutorial is loading... 111 112 **Solution** 113 114 ``` 115 #include <bits/stdc++.h> 116 117 using namespace std; 118 119 int main() 120 { 121 int t; 122 cin >> t; 123 124 while (t--) 125 { 126 int n, k; 127 cin >> n >> k; 128 129 vector<int> x(k); 130 for (int i = 0; i < k; i++) cin >> x[i]; 131 sort(x.rbegin(), x.rend()); 132 133 int cnt = 0; 134 long long sum = 0; 135 136 while (cnt < x.size() && sum + n - x[cnt] < n) 137 { 138 sum += n - x[cnt++]; 139 } 140 141 cout << cnt << '\n'; 142 } 143 144 return 0; 145 } 146 ``` 147 148 [1593D1 - All are Same](/contest/1593/problem/D1 "Codeforces Round 748 (Div. 3)") 149 150 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 151 152 **Tutorial** 153 154 Tutorial is loading... 155 156 **Solution** 157 158 ``` 159 #include <bits/stdc++.h> 160 161 using namespace std; 162 163 int main() 164 { 165 int t; 166 cin >> t; 167 168 while (t--) 169 { 170 int n; 171 cin >> n; 172 173 vector<int> a(n); 174 for (int i = 0; i < n; i++) cin >> a[i]; 175 176 bool inf = true; 177 int minval = a[0]; 178 179 for (int i = 1; i < n; i++) 180 { 181 if (a[i] != a[0]) 182 { 183 inf = false; 184 break; 185 } 186 minval = min(minval, a[i]); 187 } 188 189 if (inf) 190 { 191 cout << "-1\n"; 192 continue; 193 } 194 195 sort(a.begin(), a.end()); 196 197 int ans = 0; 198 for (int i = 0; i < n; i++) 199 ans = gcd(ans, a[i] - minval); 200 cout << ans << '\n'; 201 } 202 203 return 0; 204 } 205 ``` 206 207 [1593D2 - Half of Same](/contest/1593/problem/D2 "Codeforces Round 748 (Div. 3)") 208 209 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 210 211 **Tutorial** 212 213 Tutorial is loading... 214 215 **Solution** 216 217 ``` 218 #include <bits/stdc++.h> 219 220 using namespace std; 221 222 #define forn(i, n) for (int i = 0; i < int(n); i++) 223 224 set<int> divs(int n) { 225 set<int> d; 226 for (int dd = 1; dd * dd <= n; dd++) 227 if (n % dd == 0) { 228 d.insert(n / dd); 229 d.insert(dd); 230 } 231 return d; 232 } 233 234 int main() { 235 int t; 236 cin >> t; 237 forn(tt, t) { 238 int n; 239 cin >> n; 240 vector<int> a(n); 241 forn(i, n) 242 cin >> a[i]; 243 int k = -1; 244 245 forn(i, n) { 246 int minv = a[i]; 247 int same = 0; 248 vector<int> d; 249 forn(j, n) { 250 if (a[j] == minv) 251 same++; 252 else if (a[j] > minv) 253 d.push_back(a[j] - minv); 254 } 255 if (same >= n / 2) { 256 k = INT_MAX; 257 continue; 258 } 259 map<int,int> div_counts; 260 for (int di: d) 261 for (int dd: divs(di)) 262 div_counts[dd]++; 263 for (auto p: div_counts) 264 if (p.second >= n / 2 - same) 265 k = max(k, p.first); 266 } 267 268 cout << (k == INT_MAX ? -1 : k) << endl; 269 } 270 } 271 ``` 272 273 [1593E - Gardener and Tree](/contest/1593/problem/E "Codeforces Round 748 (Div. 3)") 274 275 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 276 277 **Tutorial** 278 279 Tutorial is loading... 280 281 **Solution** 282 283 ``` 284 #include <bits/stdc++.h> 285 286 using namespace std; 287 288 int main() 289 { 290 int t; 291 cin >> t; 292 293 while (t--) 294 { 295 int n, k; 296 cin >> n >> k; 297 298 vector<vector<int>> g(n, vector<int>()); 299 vector<int> rem(n, 0); 300 vector<int> layer(n, 0); 301 302 for (int i = 1; i < n; i++) 303 { 304 int x, y; 305 cin >> x >> y; 306 x--; 307 y--; 308 g[x].push_back(y); 309 g[y].push_back(x); 310 rem[x]++; 311 rem[y]++; 312 } 313 314 queue<int> q; 315 for (int i = 0; i < n; i++) 316 if (rem[i] == 1) 317 { 318 q.push(i); 319 layer[i] = 1; 320 } 321 322 while (!q.empty()) 323 { 324 int u = q.front(); 325 q.pop(); 326 327 for (int v : g[u]) 328 { 329 if (rem[v] != 1) 330 { 331 rem[v]--; 332 if (rem[v] == 1) 333 { 334 layer[v] = layer[u] + 1; 335 q.push(v); 336 } 337 } 338 } 339 } 340 341 int ans = 0; 342 for (int i = 0; i < n; i++) 343 if (layer[i] > k) 344 ans++; 345 346 cout << ans << '\n'; 347 } 348 349 return 0; 350 } 351 ``` 352 353 [1593F - Red-Black Number](/contest/1593/problem/F "Codeforces Round 748 (Div. 3)") 354 355 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 356 357 **Tutorial** 358 359 Tutorial is loading... 360 361 **Solution** 362 363 ``` 364 #include <bits/stdc++.h> 365 366 using namespace std; 367 368 const int MAX_N = 64; 369 370 bool dp[MAX_N][MAX_N][MAX_N][MAX_N]; // (taken, red, mod A, mod B) -> may be 371 pair<bool, int> sert[MAX_N][MAX_N][MAX_N][MAX_N]; // the same -> (true (red) | false(black), prev red/black) 372 373 int main() 374 { 375 int t; 376 cin >> t; 377 378 while (t--) 379 { 380 int n, a, b; 381 string x; 382 cin >> n >> a >> b >> x; 383 384 for (int i = 0; i <= n; i++) 385 for (int j = 0; j <= n; j++) 386 for (int k = 0; k < a; k++) 387 for (int l = 0; l < b; l++) 388 dp[i][j][k][l] = false; 389 390 dp[0][0][0][0] = true; 391 392 for(int taken = 0; taken < n; taken++) 393 for(int red = 0; red <= taken; red++) 394 for(int remA = 0; remA < a; remA++) 395 for(int remB = 0; remB < b; remB++) 396 if (dp[taken][red][remA][remB]) 397 { 398 // red transition 399 dp[taken + 1][red + 1][(remA * 10 + (x[taken] - '0')) % a][remB] = true; 400 sert[taken + 1][red + 1][(remA * 10 + (x[taken] - '0')) % a][remB] = { true, remA }; 401 402 // black transition 403 dp[taken + 1][red][remA][(remB * 10 + (x[taken] - '0')) % b] = true; 404 sert[taken + 1][red][remA][(remB * 10 + (x[taken] - '0')) % b] = { false, remB }; 405 } 406 407 int bestRed = 0; 408 409 for (int red = 1; red < n; red++) 410 if (dp[n][red][0][0] && abs(red - (n - red)) < abs(bestRed - (n - bestRed))) 411 bestRed = red; 412 413 if (bestRed == 0) 414 { 415 cout << "-1\n"; 416 } 417 else 418 { 419 int taken = n; 420 int red = bestRed; 421 int remA = 0; 422 int remB = 0; 423 string ans = ""; 424 425 while (taken > 0) 426 { 427 auto way = sert[taken][red][remA][remB]; 428 if (way.first) 429 { 430 red--; 431 remA = way.second; 432 ans.push_back('R'); 433 } 434 else 435 { 436 remB = way.second; 437 ans.push_back('B'); 438 } 439 taken--; 440 } 441 442 reverse(ans.begin(), ans.end()); 443 cout << ans << '\n'; 444 } 445 } 446 447 return 0; 448 } 449 ``` 450 451 [1593G - Changing Brackets](/contest/1593/problem/G "Codeforces Round 748 (Div. 3)") 452 453 Idea: [nastya_ka](/profile/nastya_ka "Specialist nastya_ka") 454 455 **Tutorial** 456 457 Tutorial is loading... 458 459 **Solution** 460 461 ``` 462 #include <bits/stdc++.h> 463 464 using namespace std; 465 466 const int MAX_N = 1'000'000; 467 468 int psumOdd[MAX_N + 1]; 469 int psumEven[MAX_N + 1]; 470 471 void solve() 472 { 473 string s; 474 int q; 475 cin >> s >> q; 476 int n = s.length(); 477 478 psumOdd[0] = psumEven[0] = 0; 479 for (int i = 0; i < n; i++) 480 { 481 psumOdd[i + 1] = psumOdd[i]; 482 psumEven[i + 1] = psumEven[i]; 483 484 if (s[i] == '[' || s[i] == ']') 485 { 486 if (i & 1) 487 psumOdd[i + 1]++; 488 else 489 psumEven[i + 1]++; 490 } 491 } 492 493 while (q--) 494 { 495 int l, r; 496 cin >> l >> r; 497 l--; 498 int odd = psumOdd[r] - psumOdd[l]; 499 int even = psumEven[r] - psumEven[l]; 500 cout << abs(odd - even) << '\n'; 501 } 502 } 503 504 int main() 505 { 506 int t; 507 cin >> t; 508 while (t--) 509 solve(); 510 return 0; 511 } 512 ```