2253.md (10900B)
1 Source: https://codeforces.com/blog/entry/155813 2 3 [2253A - The Best Card](/contest/2253/problem/A "Educational Codeforces Round 193 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 n = int(input()) 17 good = True 18 for j in range(2, n + 1): 19 if (n + 1) % j == 0: 20 good = False 21 if good: 22 print('YES') 23 else: 24 print('NO') 25 ``` 26 27 [2253B - Hypercarp and the Control Panel](/contest/2253/problem/B "Educational Codeforces Round 193 (Rated for Div. 2)") 28 29 Idea: [FelixArg](/profile/FelixArg "Master FelixArg") 30 31 **Tutorial** 32 33 Tutorial is loading... 34 35 **Solution (FelixArg)** 36 37 ``` 38 #include <bits/stdc++.h> 39 40 using namespace std; 41 #define int long long 42 43 void solve(){ 44 int n; 45 cin >> n; 46 vector<int> a(n); 47 for (int i = 0; i < n; i++){ 48 cin >> a[i]; 49 } 50 vector<pair<int, int>> b; 51 for (int i = 0; i < n; i++){ 52 if (b.empty() || b.back().first != a[i]){ 53 b.emplace_back(a[i], 1); 54 } 55 else{ 56 b.back().second++; 57 } 58 } 59 int m = b.size(); 60 for (int i = 0; i < m - 1; i++){ 61 if (b[i].second > 1 && b[i + 1].second > 1){ 62 cout << m + 2 << '\n'; 63 return; 64 } 65 } 66 for (int i = 0; i < m; i++){ 67 if (i < m - 1 && b[i].second > 1 && (i + 2 >= m || b[i + 2].first != b[i].first)){ 68 cout << m + 1 << '\n'; 69 return; 70 } 71 if (i > 0 && b[i].second > 1 && (i - 2 < 0 || b[i - 2].first != b[i].first)){ 72 cout << m + 1 << '\n'; 73 return; 74 } 75 } 76 cout << m << '\n'; 77 } 78 79 signed main() 80 { 81 #ifdef FELIX 82 auto _clock_start = chrono::high_resolution_clock::now(); 83 #endif 84 ios_base::sync_with_stdio(false); 85 cin.tie(0); 86 cout.tie(0); 87 88 int tests = 1; 89 cin >> tests; 90 while(tests--){ 91 solve(); 92 } 93 94 #ifdef FELIX 95 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 96 chrono::high_resolution_clock::now() 97 - _clock_start).count() << "ms." << endl; 98 #endif 99 return 0; 100 } 101 ``` 102 103 [2253C - Sum of Distinct Values in a Matrix](/contest/2253/problem/C "Educational Codeforces Round 193 (Rated for Div. 2)") 104 105 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 106 107 **Tutorial** 108 109 Tutorial is loading... 110 111 **Solution (BledDest)** 112 113 ``` 114 def get_k_last(l, k): 115 if k < len(l): 116 return l[len(l)-k:] 117 else: 118 return l 119 120 t = int(input()) 121 for _ in range(t): 122 n, m, x, y = map(int, input().split()) 123 a = list(map(int, input().split())) 124 b = list(map(int, input().split())) 125 126 c = [] 127 d = [] 128 e = [] 129 i = 0 130 j = 0 131 while i < x and j < y: 132 if a[i] == b[j]: 133 c.append(a[i]) 134 i += 1 135 j += 1 136 elif a[i] < b[j]: 137 d.append(a[i]) 138 i += 1 139 else: 140 e.append(b[j]) 141 j += 1 142 d.extend(a[i:]) 143 e.extend(b[j:]) 144 145 res = sorted(get_k_last(d, n) + get_k_last(e, m) + c) 146 res = get_k_last(res, n + m - 1) 147 print(sum(res)) 148 ``` 149 150 [2253D - Hypercarp and Interdimensional Jumps](/contest/2253/problem/D "Educational Codeforces Round 193 (Rated for Div. 2)") 151 152 Idea: [FelixArg](/profile/FelixArg "Master FelixArg") 153 154 **Tutorial** 155 156 Tutorial is loading... 157 158 **Solution (FelixArg)** 159 160 ``` 161 #include <bits/stdc++.h> 162 163 using namespace std; 164 #define int long long 165 166 void solve(){ 167 int x, y; 168 cin >> x >> y; 169 170 int su = x + y; 171 int k = 0; 172 while((k + 1) * (k + 2) / 2 <= su){ 173 k++; 174 } 175 176 int p1x = k * (k + 1) / 2 - y; 177 int p1y = y; 178 179 int p2x = x; 180 int p2y = k * (k + 1) / 2 - x; 181 182 vector<pair<int, int>> cand; 183 if ((p1x + p2x) < 0){ 184 cand.emplace_back((p1x + p2x) / 2, k * (k + 1) / 2 - (p1x + p2x) / 2); 185 cand.emplace_back((p1x + p2x - 1) / 2, k * (k + 1) / 2 - (p1x + p2x - 1) / 2); 186 } 187 else{ 188 cand.emplace_back((p1x + p2x) / 2, k * (k + 1) / 2 - (p1x + p2x) / 2); 189 cand.emplace_back((p1x + p2x + 1) / 2, k * (k + 1) / 2 - (p1x + p2x + 1) / 2); 190 } 191 192 auto best = cand[0]; 193 for (auto [p, q] : cand){ 194 if (p < 0){ 195 p = 0; 196 } 197 if (q < 0){ 198 q = 0; 199 } 200 if ((p - x) * (p - x) + (q - y) * (q - y) < 201 (best.first - x) * (best.first - x) + (best.second - y) * (best.second - y)){ 202 best = {p, q}; 203 } 204 } 205 206 string ans(k, 'Y'); 207 for (int i = 0; i < k; i++){ 208 if (best.first >= k - i){ 209 ans[i] = 'X'; 210 best.first -= (k - i); 211 } 212 } 213 214 cout << ans << '\n'; 215 } 216 217 signed main() 218 { 219 #ifdef FELIX 220 auto _clock_start = chrono::high_resolution_clock::now(); 221 #endif 222 ios_base::sync_with_stdio(false); 223 cin.tie(0); 224 cout.tie(0); 225 226 int tests = 1; 227 cin >> tests; 228 while(tests--){ 229 solve(); 230 } 231 232 #ifdef FELIX 233 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 234 chrono::high_resolution_clock::now() 235 - _clock_start).count() << "ms." << endl; 236 #endif 237 return 0; 238 } 239 ``` 240 241 [2253E - Diameter Intersections](/contest/2253/problem/E "Educational Codeforces Round 193 (Rated for Div. 2)") 242 243 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 244 245 **Tutorial** 246 247 Tutorial is loading... 248 249 **Solution (BledDest)** 250 251 ``` 252 #include<bits/stdc++.h> 253 254 using namespace std; 255 256 const int N = 1000043; 257 258 vector<int> g[N]; 259 int n; 260 261 vector<int> get_dist(int x) 262 { 263 vector<int> d(n, -1); 264 d[x] = 0; 265 queue<int> q; 266 q.push(x); 267 while(!q.empty()) 268 { 269 int k = q.front(); 270 q.pop(); 271 for(auto y : g[k]) 272 if(d[y] == -1) 273 { 274 d[y] = d[k] + 1; 275 q.push(y); 276 } 277 } 278 return d; 279 } 280 281 void remove_edge(int x, int y) 282 { 283 int idx = -1; 284 for(int i = 0; i < g[x].size(); i++) 285 if(g[x][i] == y) 286 idx = i; 287 g[x].erase(g[x].begin() + idx, g[x].begin() + idx + 1); 288 } 289 290 vector<int> process(int v) 291 { 292 vector<int> d(n, -1), p(n, -1); 293 queue<int> q; 294 q.push(v); 295 d[v] = 0; 296 vector<int> visited; 297 while(!q.empty()) 298 { 299 int k = q.front(); 300 q.pop(); 301 visited.push_back(k); 302 for(auto y : g[k]) 303 if(d[y] == -1) 304 { 305 d[y] = d[k] + 1; 306 q.push(y); 307 p[y] = k; 308 } 309 } 310 int max_dist = *max_element(d.begin(), d.end()); 311 vector<bool> has_end(n, false); 312 has_end[v] = true; 313 for(auto x : visited) 314 if(d[x] == max_dist) 315 { 316 int cur = x; 317 while(!has_end[cur]) 318 { 319 has_end[cur] = true; 320 cur = p[cur]; 321 } 322 } 323 324 vector<int> res; 325 for(auto x : visited) 326 { 327 if(!has_end[x]) continue; 328 int good_children = 0; 329 for(auto y : g[x]) 330 if(p[x] != y && has_end[y]) good_children++; 331 if(good_children != 1) res.push_back(d[x]); 332 } 333 sort(res.begin(), res.end()); 334 res.erase(unique(res.begin(), res.end()), res.end()); 335 return res; 336 } 337 338 void solve() 339 { 340 cin >> n; 341 for(int i = 0; i < n; i++) 342 g[i].clear(); 343 for(int i = 0; i < n - 1; i++) 344 { 345 int x, y; 346 cin >> x >> y; 347 --x; 348 --y; 349 g[x].push_back(y); 350 g[y].push_back(x); 351 } 352 353 auto dist0 = get_dist(0); 354 int e1 = max_element(dist0.begin(), dist0.end()) - dist0.begin(); 355 auto dist1 = get_dist(e1); 356 int e2 = max_element(dist1.begin(), dist1.end()) - dist1.begin(); 357 auto dist2 = get_dist(e2); 358 int d = dist1[e2]; 359 360 int x = -1, y = -1; 361 for(int i = 0; i < n; i++) 362 if(dist1[i] + dist2[i] == d) 363 { 364 if(dist1[i] == dist2[i] - 1) 365 x = i; 366 else if(dist1[i] == dist2[i] + 1) 367 y = i; 368 } 369 370 remove_edge(x, y); 371 remove_edge(y, x); 372 auto ans1 = process(x); 373 auto ans2 = process(y); 374 375 vector<bool> res(n + 1); 376 for(auto x : ans1) 377 for(auto y : ans2) 378 res[x + y + 1] = true; 379 int cnt = 0; 380 for(auto x : res) 381 if(x) cnt++; 382 cout << cnt; 383 for(int i = 0; i <= n; i++) 384 if(res[i]) 385 cout << " " << i; 386 cout << endl; 387 } 388 389 int main() 390 { 391 ios_base::sync_with_stdio(0); 392 cin.tie(0); 393 int t; 394 cin >> t; 395 for(int i = 0; i < t; i++) 396 solve(); 397 } 398 ``` 399 400 [2253F - 4-beauty](/contest/2253/problem/F "Educational Codeforces Round 193 (Rated for Div. 2)") 401 402 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 403 404 **Tutorial** 405 406 Tutorial is loading... 407 408 **Solution (BledDest)** 409 410 ``` 411 #include<bits/stdc++.h> 412 413 using namespace std; 414 415 const int N = int(5e5) + 43; 416 const long long INF64 = (long long)(1e18); 417 418 int n; 419 int cost[N]; 420 421 void upd(long long& x, long long y) 422 { 423 if(x > y) x = y; 424 } 425 426 bool check_bit(int x, int y) 427 { 428 return bool((x >> y) & 1); 429 } 430 431 long long calc_dp(const vector<vector<int>>& c) 432 { 433 int n = c.size(); 434 int m = c[0].size(); 435 int full = (1 << m) - 1; 436 vector<vector<vector<long long>>> dp(2, vector<vector<long long>>(m, vector<long long>(1 << m, INF64))); 437 dp[0][0][0] = 0; 438 for(int i = 0; i < n; i++) 439 { 440 int i1 = i & 1; 441 int i2 = i1 ^ 1; 442 for(int j = 0; j < m; j++) 443 for(int f = 0; f < (1 << m); f++) 444 dp[i2][j][f] = INF64; 445 for(int j = 0; j < m; j++) 446 for(int f = 0; f < (1 << m); f++) 447 { 448 if(dp[i1][j][f] == INF64) continue; 449 int ni = i1; 450 int nj = j + 1; 451 if(nj == m) 452 { 453 ni = i2; 454 nj = 0; 455 } 456 bool can = true; 457 if(i > 0 && j + 2 < m && check_bit(f, m - 1) && check_bit(f, m - 2) && check_bit(f, m - 3)) 458 can = false; 459 if(can) 460 { 461 int nf = ((f << 1) & full) | 1; 462 upd(dp[ni][nj][nf], dp[i1][j][f]); 463 } 464 int nf = (f << 1) & full; 465 upd(dp[ni][nj][nf], dp[i1][j][f] + c[i][j]); 466 } 467 } 468 return *min_element(dp[n & 1][0].begin(), dp[n & 1][0].end()); 469 } 470 471 long long calc_comp(int x) 472 { 473 int d2 = 0, d3 = 0; 474 int p2 = 1, p3 = 1; 475 while(x * (p2 * 2) <= n) 476 { 477 p2 *= 2; 478 d2++; 479 } 480 while(x * (p3 * 3) <= n) 481 { 482 p3 *= 3; 483 d3++; 484 } 485 d2++; 486 d3++; 487 vector<int> pow2(d2, 1), pow3(d3, 1); 488 for(int i = 1; i < d2; i++) 489 pow2[i] = pow2[i - 1] * 2; 490 for(int i = 1; i < d3; i++) 491 pow3[i] = pow3[i - 1] * 3; 492 vector<vector<int>> cur(d3, vector<int>(d2, 0)); 493 for(int i = 0; i < d2; i++) 494 for(int j = 0; j < d3; j++) 495 if(x * 1ll * pow2[i] * 1ll * pow3[j] <= n) 496 cur[j][i] = cost[x * pow2[i] * pow3[j]]; 497 return calc_dp(cur); 498 } 499 500 void solve() 501 { 502 cin >> n; 503 for(int i = 1; i <= n; i++) 504 cin >> cost[i]; 505 long long ans = 0; 506 for(int i = 1; i <= n; i++) 507 if(i % 2 != 0 && i % 3 != 0) 508 ans += calc_comp(i); 509 cout << ans << endl; 510 } 511 512 int main() 513 { 514 ios_base::sync_with_stdio(0); 515 int t = 1; 516 for(int i = 0; i < t; i++) 517 solve(); 518 } 519 ```