1822.md (10023B)
1 Source: https://codeforces.com/blog/entry/115409 2 3 [1822A - TubeTube Feed](/contest/1822/problem/A "Codeforces Round 867 (Div. 3)") 4 5 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 def solve(): 15 n, t = map(int, input().split()) 16 a = [int(x) for x in input().split()] 17 b = [int(x) for x in input().split()] 18 bst = -2 19 for i in range(n): 20 if i + a[i] <= t and (bst == -2 or b[bst] < b[i]): 21 bst = i 22 print(bst + 1) 23 24 25 t = int(input()) 26 for _ in range(t): 27 solve() 28 ``` 29 30 **Rate the problem** 31 32 * Didn't solve 33 * Good task 34 * Average task 35 * Bad task 36 37 [1822B - Karina and Array](/contest/1822/problem/B "Codeforces Round 867 (Div. 3)") 38 39 Idea: [playerr17](/profile/playerr17 "Expert playerr17"), prepared: [playerr17](/profile/playerr17 "Expert playerr17") 40 41 **Tutorial** 42 43 Tutorial is loading... 44 45 **Solution** 46 47 ``` 48 t = int(input()) 49 50 for testCase in range(t): 51 n = int(input()) 52 a = list(map(int, input().split(' '))) 53 a.sort() 54 print(max(a[0] * a[1], a[-1] * a[-2])) 55 ``` 56 57 **Rate the problem** 58 59 * Didn't solve 60 * Good task 61 * Average task 62 * Bad task 63 64 [1822C - Bun Lover](/contest/1822/problem/C "Codeforces Round 867 (Div. 3)") 65 66 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka"), prepared: [diskoteka](/profile/diskoteka "Candidate Master diskoteka") 67 68 **Tutorial** 69 70 Tutorial is loading... 71 72 **Solution** 73 74 ``` 75 #include <bits/stdc++.h> 76 77 using namespace std; 78 79 #define int long long 80 81 int32_t main() { 82 int q; 83 cin >> q; 84 while (q--) { 85 int n; 86 cin >> n; 87 cout << ((n + 1) * n) + n + 2 << "\n"; 88 } 89 return 0; 90 } 91 ``` 92 93 **Rate the problem** 94 95 * Didn't solve 96 * Good task 97 * Average task 98 * Bad task 99 100 [1822D - Super-Permutation](/contest/1822/problem/D "Codeforces Round 867 (Div. 3)") 101 102 Idea: [isosto](/profile/isosto "Candidate Master isosto"), [pavlekn](/profile/pavlekn "Master pavlekn"), prepared: [diskoteka](/profile/diskoteka "Candidate Master diskoteka") 103 104 **Tutorial** 105 106 Tutorial is loading... 107 108 **Solution** 109 110 ``` 111 #include <bits/stdc++.h> 112 113 using namespace std; 114 115 int main() { 116 int q; 117 cin >> q; 118 while (q--) { 119 int n; 120 cin >> n; 121 if (n == 1) { 122 cout << "1\n"; 123 continue; 124 } 125 if (n % 2) { 126 cout << "-1\n"; 127 } else { 128 for (int i = 0; i < n; ++i) { 129 if (i % 2) { 130 cout << i << " "; 131 } else { 132 cout << n - i << " "; 133 } 134 } 135 cout << "\n"; 136 } 137 } 138 return 0; 139 } 140 ``` 141 142 **Rate the problem** 143 144 * Didn't solve 145 * Good task 146 * Average task 147 * Bad task 148 149 [1822E - Making Anti-Palindromes](/contest/1822/problem/E "Codeforces Round 867 (Div. 3)") 150 151 Idea: [pavlekn](/profile/pavlekn "Master pavlekn"), prepared: [pavlekn](/profile/pavlekn "Master pavlekn") 152 153 **Tutorial** 154 155 Tutorial is loading... 156 157 **Solution** 158 159 ``` 160 #include <bits/stdc++.h> 161 162 using namespace std; 163 164 void solve(int n, string & s) { 165 if (n % 2 == 1) { 166 cout << -1 << endl; 167 return; 168 } 169 vector<int> cnt(26); 170 for (int i = 0; i < n; ++i) { 171 ++cnt[s[i] - 'a']; 172 } 173 for (int i = 0; i < 26; ++i) { 174 if (cnt[i] * 2 > n) { 175 cout << -1 << endl; 176 return; 177 } 178 } 179 int pairs = 0; 180 vector<int> cnt_pairs(26); 181 for (int i = 0; i * 2 < n; ++i) { 182 if (s[i] == s[n - i - 1]) { 183 ++pairs; 184 ++cnt_pairs[s[i] - 'a']; 185 } 186 } 187 for (int i = 0; i < 26; ++i) { 188 if (cnt_pairs[i] * 2 > pairs) { 189 cout << cnt_pairs[i] << endl; 190 return; 191 } 192 } 193 cout << (pairs + 1) / 2 << endl; 194 } 195 196 int32_t main() { 197 int t; 198 cin >> t; 199 for (int _ = 0; _ < t; ++_) { 200 int n; 201 cin >> n; 202 string s; 203 cin >> s; 204 solve(n, s); 205 } 206 } 207 ``` 208 209 **Rate the problem** 210 211 * Didn't solve 212 * Good task 213 * Average task 214 * Bad task 215 216 [1822F - Gardening Friends](/contest/1822/problem/F "Codeforces Round 867 (Div. 3)") 217 218 Idea: [playerr17](/profile/playerr17 "Expert playerr17"), prepared: [playerr17](/profile/playerr17 "Expert playerr17") 219 220 **Tutorial** 221 222 Tutorial is loading... 223 224 **Solution** 225 226 ``` 227 #include<bits/stdc++.h> 228 229 using namespace std; 230 231 struct Value { 232 int64_t value = 0; 233 int vertex = 0; 234 }; 235 236 vector<vector<int>> nei; 237 vector<vector<int>> depth_vertex; 238 vector<int> depth; 239 vector<int> parent; 240 241 void dfs(int v, int p = -1, int cnt = 0) { 242 depth_vertex[cnt].push_back(v); 243 depth[v] = cnt; 244 parent[v] = p; 245 for (int u : nei[v]) { 246 if (u == p) continue; 247 dfs(u, v, cnt + 1); 248 } 249 } 250 251 void solve() { 252 int n, root = 1; 253 int64_t k_wei, cost; 254 cin >> n >> k_wei >> cost; 255 256 nei.clear(); 257 nei.resize(n + 1); 258 depth_vertex.clear(); 259 depth_vertex.resize(n + 1); 260 depth.clear(); 261 depth.resize(n + 1); 262 parent.clear(); 263 parent.resize(n + 1); 264 265 for (int _ = 0; _ < n - 1; ++_) { 266 int u, v; 267 cin >> u >> v; 268 nei[u].push_back(v); 269 nei[v].push_back(u); 270 } 271 272 dfs(root); 273 274 vector<pair<Value, Value>> down(n + 1); 275 276 for (int tin = n; tin >= 0; --tin) { 277 for (int v : depth_vertex[tin]) { 278 for (int u : nei[v]) { 279 if (u == parent[v]) continue; 280 if (down[u].first.value + 1 > down[v].first.value) { 281 down[v].first.value = down[u].first.value + 1; 282 down[v].first.vertex = u; 283 } 284 } 285 for (int u : nei[v]) { 286 if (u == parent[v] || u == down[v].first.vertex) continue; 287 if (down[u].first.value + 1 > down[v].second.value) { 288 down[v].second.value = down[u].first.value + 1; 289 } 290 } 291 } 292 } 293 294 vector<int64_t> up(n + 1, 0); 295 296 for (int tin = 1; tin <= n; ++tin) { 297 for (int v : depth_vertex[tin]) { 298 int p = parent[v]; 299 up[v] = up[p] + 1; 300 if (down[p].first.vertex == v) { 301 up[v] = max(up[v], down[p].second.value + 1); 302 } else { 303 up[v] = max(up[v], down[p].first.value + 1); 304 } 305 } 306 } 307 308 int64_t ans = -1'000'000'000'000'000'002; 309 310 for (int v = 1; v <= n; ++v) { 311 ans = max(ans, k_wei * max(up[v], down[v].first.value) - cost * int64_t(depth[v])); 312 } 313 314 cout << ans << endl; 315 316 } 317 318 int main() 319 { 320 int t; 321 cin >> t; 322 for (int _ = 1; _ <= t; ++_) { 323 solve(); 324 } 325 return 0; 326 } 327 ``` 328 329 **Rate the problem** 330 331 * Didn't solve 332 * Good task 333 * Average task 334 * Bad task 335 336 [1822G1 - Magic Triples (Easy Version)](/contest/1822/problem/G1 "Codeforces Round 867 (Div. 3)") 337 338 Idea: [pavlekn](/profile/pavlekn "Master pavlekn"), prepared: [pavlekn](/profile/pavlekn "Master pavlekn") 339 340 **Tutorial** 341 342 Tutorial is loading... 343 344 **Solution** 345 346 ``` 347 #include <bits/stdc++.h> 348 349 using namespace std; 350 351 #define int long long 352 353 const int MAX_VAL = 1e6; 354 355 int cnt[MAX_VAL + 1]; 356 357 int32_t main() { 358 int t; 359 cin >> t; 360 for (int _ = 0; _ < t; ++_) { 361 int n; 362 cin >> n; 363 vector<int> a(n); 364 for (int i = 0; i < n; ++i) { 365 cin >> a[i]; 366 ++cnt[a[i]]; 367 } 368 int ans = 0; 369 for (int i = 0; i < n; ++i) { 370 ans += (cnt[a[i]] - 1) * (cnt[a[i]] - 2); 371 for (int b = 2; a[i] * b * b <= MAX_VAL; ++b) { 372 ans += cnt[a[i] * b] * cnt[a[i] * b * b]; 373 } 374 } 375 cout << ans << "\n"; 376 for (int i = 0; i < n; ++i) { 377 --cnt[a[i]]; 378 } 379 } 380 return 0; 381 } 382 ``` 383 384 **Rate the problem** 385 386 * Didn't solve 387 * Good task 388 * Average task 389 * Bad task 390 391 [1822G2 - Magic Triples (Hard Version)](/contest/1822/problem/G2 "Codeforces Round 867 (Div. 3)") 392 393 Idea: [pavlekn](/profile/pavlekn "Master pavlekn"), prepared: [pavlekn](/profile/pavlekn "Master pavlekn") 394 395 **Tutorial** 396 397 Tutorial is loading... 398 399 **Solution** 400 401 ``` 402 #include <bits/stdc++.h> 403 404 using namespace std; 405 406 typedef long long ll; 407 408 const int K = 1e6; 409 const int MAX_VAL = 1e9; 410 411 int32_t main() { 412 int t; 413 scanf("%d", &t); 414 for (int _ = 0; _ < t; ++_) { 415 int n; 416 scanf("%d", &n); 417 vector<int> a(n); 418 map<int, int> cnt; 419 for (int i = 0; i < n; ++i) { 420 scanf("%d", &a[i]); 421 ++cnt[a[i]]; 422 } 423 ll ans = 0; 424 for (int i = 0; i < n; ++i) { 425 ans += (ll)(cnt[a[i]] - 1) * (cnt[a[i]] - 2); 426 } 427 for (auto el : cnt) { 428 int num = el.first; 429 int val = el.second; 430 if (num > K) { 431 for (int b = 2; b * num <= MAX_VAL; ++b) { 432 if (num % b == 0 && cnt.find(num / b) != cnt.end() && cnt.find(num * b) != cnt.end()) { 433 ans += (ll)(cnt[num / b]) * (cnt[num * b]) * val; 434 } 435 } 436 } else { 437 for (int b = 2; b * b <= num; ++b) { 438 if (num % b == 0) { 439 if ((ll)num * b <= (ll)MAX_VAL && cnt.find(num / b) != cnt.end() && cnt.find(num * b) != cnt.end()) { 440 ans += (ll)(cnt[num / b]) * (cnt[num * b]) * val; 441 } 442 if (b * b != num) { 443 if ((ll)num * num / b <= (ll)MAX_VAL && cnt.find(b) != cnt.end() && cnt.find(num / b * num) != cnt.end()) { 444 ans += (ll)(cnt[b]) * (cnt[num / b * num]) * val; 445 } 446 } 447 } 448 } 449 if (num > 1 && (ll)num * num <= (ll)MAX_VAL && cnt.find(1) != cnt.end() && cnt.find(num * num) != cnt.end()) { 450 ans += (ll)(cnt[1]) * (cnt[num * num]) * val; 451 } 452 } 453 } 454 printf("%lld\n", ans); 455 } 456 return 0; 457 } 458 ``` 459 460 **Rate the problem** 461 462 * Didn't solve 463 * Good task 464 * Average task 465 * Bad task