1676.md (8724B)
1 Source: https://codeforces.com/blog/entry/102710 2 3 Thank you for participating! 4 5 [1676A - Счастливый?](/contest/1676/problem/A "Codeforces Round 790 (Div. 4)") 6 7 Idea: [mesanu](/profile/mesanu "Эксперт mesanu") and [SlavicG](/profile/SlavicG "Кандидат в мастера SlavicG") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution** 14 15 ``` 16 #include <bits/stdc++.h> 17 using namespace std; 18 19 void solve() { 20 string s; 21 cin >> s; 22 if(s[0]+s[1]+s[2] == s[3]+s[4]+s[5]) { 23 cout << "YES" << endl; 24 } 25 else { 26 cout << "NO" << endl; 27 } 28 } 29 30 int main() { 31 int t = 1; 32 cin >> t; 33 while (t--) { 34 solve(); 35 } 36 } 37 ``` 38 39 [1676B - Равенство конфет](/contest/1676/problem/B "Codeforces Round 790 (Div. 4)") 40 41 Idea: [Errichto](/profile/Errichto "Международный гроссмейстер Errichto") 42 43 **Tutorial** 44 45 Tutorial is loading... 46 47 **Solution** 48 49 ``` 50 #include "bits/stdc++.h" 51 using namespace std; 52 53 int main() { 54 int t; cin >> t; 55 while(t--) { 56 int n; cin >> n; 57 vector<int> a(n); 58 int mn = INT_MAX, ans = 0; 59 for(int i = 0; i < n; ++i) { 60 cin >> a[i]; 61 mn = min(mn, a[i]); 62 } 63 for(int i = 0; i < n; ++i) { 64 ans += a[i] - mn; 65 } 66 cout << ans << "\n"; 67 } 68 } 69 ``` 70 71 [1676C - Самые похожие слова](/contest/1676/problem/C "Codeforces Round 790 (Div. 4)") 72 73 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 74 75 **Tutorial** 76 77 Tutorial is loading... 78 79 **Solution** 80 81 ``` 82 #include "bits/stdc++.h" 83 using namespace std; 84 85 int cost(string& a, string& b) { 86 int val = 0; 87 for(int i = 0; i < a.size(); ++i) { 88 val += abs(a[i] - b[i]); 89 } 90 return val; 91 } 92 93 int main() { 94 int t; cin >> t; 95 while(t--) { 96 int n, m; cin >> n >> m; 97 vector<string> s(n); 98 for(int i = 0; i < n; ++i) { 99 cin >> s[i]; 100 } 101 int ans = INT_MAX; 102 for(int i = 0; i < n; ++i) { 103 for(int j = i + 1; j < n; ++j) { 104 ans = min(ans, cost(s[i], s[j])); 105 } 106 } 107 cout << ans << "\n"; 108 } 109 } 110 ``` 111 112 [1676D - X-сумма](/contest/1676/problem/D "Codeforces Round 790 (Div. 4)") 113 114 Idea: [mesanu](/profile/mesanu "Эксперт mesanu") 115 116 **Tutorial** 117 118 Tutorial is loading... 119 120 **Solution** 121 122 ``` 123 #include <bits/stdc++.h> 124 using namespace std; 125 126 void solve() 127 { 128 int n, m; 129 cin >> n >> m; 130 int a[n][m]; 131 for(int i = 0; i < n; i++) 132 { 133 for(int j = 0; j < m; j++) 134 { 135 cin >> a[i][j]; 136 } 137 } 138 int mx = 0; 139 for(int i = 0; i < n; i++) 140 { 141 for(int j = 0; j < m; j++) 142 { 143 int now = 0; 144 int ci = i, cj = j; 145 while(ci >= 0 && ci < n && cj >= 0 && cj < m) 146 { 147 now+=a[ci][cj]; 148 ci--; 149 cj--; 150 } 151 ci = i, cj = j; 152 while(ci >= 0 && ci < n && cj >= 0 && cj < m) 153 { 154 now+=a[ci][cj]; 155 ci++; 156 cj--; 157 } 158 ci = i, cj = j; 159 while(ci >= 0 && ci < n && cj >= 0 && cj < m) 160 { 161 now+=a[ci][cj]; 162 ci--; 163 cj++; 164 } 165 ci = i, cj = j; 166 while(ci >= 0 && ci < n && cj >= 0 && cj < m) 167 { 168 now+=a[ci][cj]; 169 ci++; 170 cj++; 171 } 172 now-=a[i][j]*3; 173 mx = max(mx, now); 174 } 175 } 176 cout << mx << endl; 177 } 178 179 int main() { 180 int t; 181 cin >> t; 182 while(t--) 183 { 184 solve(); 185 } 186 } 187 ``` 188 189 [1676E - Запросы на поедание конфет](/contest/1676/problem/E "Codeforces Round 790 (Div. 4)") 190 191 Idea: [mesanu](/profile/mesanu "Эксперт mesanu") 192 193 **Tutorial** 194 195 Tutorial is loading... 196 197 **Solution** 198 199 ``` 200 #include "bits/stdc++.h" 201 using namespace std; 202 203 int main() { 204 int t; cin >> t; 205 while(t--) { 206 int n, q; cin >> n >> q; 207 vector<long long> a(n), p(n); 208 for(int i = 0; i < n; ++i) { 209 cin >> a[i]; 210 } 211 sort(a.rbegin(), a.rend()); 212 for(int i = 0; i < n; ++i) { 213 p[i] = (i ? p[i - 1] : 0) + a[i]; 214 } 215 216 while(q--) { 217 long long x; cin >> x; 218 int l = 1, r = n, ans = -1; 219 while(l <= r) { 220 int mid = (l + r) / 2; 221 if(p[mid - 1] >= x) { 222 ans = mid; 223 r = mid - 1; 224 } else { 225 l = mid + 1; 226 } 227 } 228 cout << ans << "\n"; 229 } 230 } 231 } 232 ``` 233 234 [1676F - Самый длинный страйк](/contest/1676/problem/F "Codeforces Round 790 (Div. 4)") 235 236 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 237 238 **Tutorial** 239 240 Tutorial is loading... 241 242 **Solution** 243 244 ``` 245 #include <bits/stdc++.h> 246 using namespace std; 247 248 void solve() 249 { 250 int n, k; 251 cin >> n >> k; 252 int a[n]; 253 map<int, int> mp; 254 for(int i = 0; i < n; i++) 255 { 256 cin >> a[i]; 257 mp[a[i]]++; 258 } 259 vector<int> c; 260 for(auto x : mp) 261 { 262 if(x.second >= k) 263 { 264 c.push_back(x.first); 265 } 266 } 267 if(c.size() == 0) 268 { 269 cout << -1 << endl; 270 return; 271 } 272 sort(c.begin(), c.end()); 273 int mx = 0; 274 int lans = c[0], rans = c[0]; 275 int l = c[0]; 276 for(int i = 1; i < c.size(); i++) 277 { 278 if(c[i]-1 == c[i-1]) 279 { 280 if(c[i]-l > mx) 281 { 282 lans = l; 283 rans = c[i]; 284 mx = c[i]-l; 285 } 286 } 287 else 288 { 289 l = c[i]; 290 } 291 } 292 cout << lans << " " << rans << endl; 293 } 294 295 int main(int argc, char * argv[]) 296 { 297 int t; 298 cin >> t; 299 while(t--) 300 { 301 solve(); 302 } 303 } 304 ``` 305 306 [1676G - Чёрно-белые сбалансированные поддеревья](/contest/1676/problem/G "Codeforces Round 790 (Div. 4)") 307 308 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 309 310 **Tutorial** 311 312 Tutorial is loading... 313 314 **Solution** 315 316 ``` 317 #include <bits/stdc++.h> 318 319 using namespace std; 320 321 const int MAX = 200007; 322 const int MOD = 1000000007; 323 324 void solve() { 325 int n; 326 cin >> n; 327 vector<int> child[n + 7]; 328 for (int i = 2; i <= n; i++) { 329 int x; 330 cin >> x; 331 child[x].push_back(i); 332 } 333 string s; 334 cin >> s; 335 int res = 0; 336 function<int(int)> dp = [&] (int x) { 337 int bal = (s[x - 1] == 'B') ? -1 : 1; 338 if (child[x].empty()) {return bal;} 339 for (int i : child[x]) { 340 bal += dp(i); 341 } 342 if (bal == 0) {res++;} 343 return bal; 344 }; 345 dp(1); 346 cout << res << '\n'; 347 } 348 349 int main() { 350 ios::sync_with_stdio(false); 351 cin.tie(nullptr); 352 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 353 // solve(); 354 } 355 ``` 356 357 [1676H1 - Максимизация пересечений (простая версия)](/contest/1676/problem/H1 "Codeforces Round 790 (Div. 4)") 358 359 Idea: [flamestorm](/profile/flamestorm "Эксперт flamestorm") 360 361 **Tutorial** 362 363 Tutorial is loading... 364 365 **Solution** 366 367 ``` 368 #include <bits/stdc++.h> 369 370 using namespace std; 371 372 const int MAX = 200007; 373 const int MOD = 1000000007; 374 375 void solve() { 376 int n; 377 cin >> n; 378 int a[n]; 379 for (int i = 0; i < n; i++) { 380 cin >> a[i]; 381 } 382 int res = 0; 383 for (int i = 0; i < n; i++) { 384 for (int j = i + 1; j < n; j++) { 385 if (a[i] >= a[j]) {res++;} 386 } 387 } 388 cout << res << '\n'; 389 } 390 391 int main() { 392 ios::sync_with_stdio(false); 393 cin.tie(nullptr); 394 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 395 // solve(); 396 } 397 ``` 398 399 [1676H2 - Максимизация пересечений (сложная версия)](/contest/1676/problem/H2 "Codeforces Round 790 (Div. 4)") 400 401 Idea: [flamestorm](/profile/flamestorm "Эксперт flamestorm") 402 403 **Tutorial** 404 405 Tutorial is loading... 406 407 **Solution** 408 409 ``` 410 #include <bits/stdc++.h> 411 412 using namespace std; 413 414 const int MAX = 200007; 415 const int MOD = 1000000007; 416 417 long long merge(int a[], int temp[], int left, int mid, int right) { 418 int i, j, k; 419 long long count = 0; 420 i = left; 421 j = mid; 422 k = left; 423 while ((i <= mid - 1) && (j <= right)) { 424 if (a[i] <= a[j]){ 425 temp[k++] = a[i++]; 426 } else { 427 temp[k++] = a[j++]; 428 count += (mid - i); 429 } 430 } 431 while (i <= mid - 1) 432 temp[k++] = a[i++]; 433 while (j <= right) 434 temp[k++] = a[j++]; 435 for (i=left; i <= right; i++) 436 a[i] = temp[i]; 437 return count; 438 } 439 long long mergeSort(int a[], int temp[], int left, int right){ 440 int mid; 441 long long count = 0; 442 if (right > left) { 443 mid = (right + left)/2; 444 count = mergeSort(a, temp, left, mid); 445 count += mergeSort(a, temp, mid+1, right); 446 count += merge(a, temp, left, mid+1, right); 447 } 448 return count; 449 } 450 long long aInversion(int a[], int n) { 451 int temp[n]; 452 return mergeSort(a, temp, 0, n - 1); 453 } 454 455 void solve() { 456 int n; 457 cin >> n; 458 int a[n]; 459 for (int i = 0; i < n; i++) { 460 cin >> a[i]; 461 } 462 long long res = aInversion(a, n); 463 sort(a, a + n); 464 long long curr = 1; 465 for (int i = 1; i < n; i++) { 466 if (a[i] != a[i - 1]) {res += (curr * (curr - 1)) / 2; curr = 1;} 467 else {curr++;} 468 } 469 res += (curr * (curr - 1)) / 2; 470 cout << res << '\n'; 471 } 472 473 int main() { 474 ios::sync_with_stdio(false); 475 cin.tie(nullptr); 476 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 477 // solve(); 478 } 479 ```