2114.md (9132B)
1 Source: https://codeforces.com/blog/entry/143268 2 3 [2114A - Square Year](/contest/2114/problem/A "Codeforces Round 1027 (Div. 3)") 4 5 Idea: [myav](/profile/myav "Pupil myav") 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 void solve() { 19 int n; 20 cin >> n; 21 int sq = ceil(sqrt(n)); 22 if (sq * sq == n) { 23 cout << 0 << ' ' << sq << "\n"; 24 } else { 25 cout << "-1\n"; 26 } 27 } 28 29 int main() { 30 int t; 31 cin >> t; 32 while (t--) solve(); 33 } 34 ``` 35 36 **Rate the problem** 37 38 * Didn't solve 39 * Good task 40 * Average task 41 * Bad task 42 43 [2114B - Not Quite a Palindromic String](/contest/2114/problem/B "Codeforces Round 1027 (Div. 3)") 44 45 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya") 46 47 **Tutorial** 48 49 Tutorial is loading... 50 51 **Solution** 52 53 ``` 54 #include <bits/stdc++.h> 55 56 #define int long long 57 #define pb emplace_back 58 #define mp make_pair 59 #define x first 60 #define y second 61 #define all(a) a.begin(), a.end() 62 #define rall(a) a.rbegin(), a.rend() 63 64 typedef long double ld; 65 typedef long long ll; 66 67 using namespace std; 68 69 mt19937 rnd(time(nullptr)); 70 71 const int inf = 1e9; 72 const int M = 1e9 + 7; 73 const ld pi = atan2(0, -1); 74 const ld eps = 1e-6; 75 76 void solve(int tc){ 77 int n, k; 78 cin >> n >> k; 79 string s; 80 cin >> s; 81 vector<int> cnt(2); 82 for(char c: s){ 83 cnt[c - '0']++; 84 } 85 int mn = max(cnt[0], cnt[1]) - n / 2; 86 int mx = cnt[0] / 2 + cnt[1] / 2; 87 if(k >= mn && (k - mn) % 2 == 0 && k <= mx) cout << "YES"; 88 else cout << "NO"; 89 } 90 91 bool multi = true; 92 93 signed main() { 94 int t = 1; 95 if (multi)cin >> t; 96 for (int i = 1; i <= t; ++i) { 97 solve(i); 98 cout << "\n"; 99 } 100 return 0; 101 } 102 ``` 103 104 **Rate the problem** 105 106 * Didn't solve 107 * Good task 108 * Average task 109 * Bad task 110 111 [2114C - Need More Arrays](/contest/2114/problem/C "Codeforces Round 1027 (Div. 3)") 112 113 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya") 114 115 **Tutorial** 116 117 Tutorial is loading... 118 119 **Solution** 120 121 ``` 122 #include <bits/stdc++.h> 123 124 using namespace std; 125 126 void solve(int tc){ 127 int n; 128 cin >> n; 129 int last = -1, ans = 0; 130 for(int i = 0; i < n; ++i){ 131 int a; 132 cin >> a; 133 if(a - last > 1){ 134 ans++; 135 last = a; 136 } 137 } 138 cout << ans; 139 } 140 141 bool multi = true; 142 143 signed main() { 144 int t = 1; 145 if (multi)cin >> t; 146 for (int i = 1; i <= t; ++i) { 147 solve(i); 148 cout << "\n"; 149 } 150 return 0; 151 } 152 ``` 153 154 **Rate the problem** 155 156 * Didn't solve 157 * Good task 158 * Average task 159 * Bad task 160 161 [2114D - Come a Little Closer](/contest/2114/problem/D "Codeforces Round 1027 (Div. 3)") 162 163 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya") 164 165 **Tutorial** 166 167 Tutorial is loading... 168 169 **Solution** 170 171 ``` 172 #include <bits/stdc++.h> 173 174 #define int long long 175 #define pb emplace_back 176 #define mp make_pair 177 #define x first 178 #define y second 179 #define all(a) a.begin(), a.end() 180 #define rall(a) a.rbegin(), a.rend() 181 182 typedef long double ld; 183 typedef long long ll; 184 185 using namespace std; 186 187 mt19937 rnd(time(nullptr)); 188 189 const int inf = 1e9; 190 const int M = 1e9 + 7; 191 const ld pi = atan2(0, -1); 192 const ld eps = 1e-6; 193 194 struct min_max{ 195 int mx1, mx2, mn1, mn2; 196 197 void fix_mx(){ 198 if(mx1 < mx2){ 199 swap(mx1, mx2); 200 } 201 } 202 void fix_mn(){ 203 if(mn1 > mn2){ 204 swap(mn1, mn2); 205 } 206 } 207 208 min_max(int a, int b){ 209 mx1 = mn1 = a; 210 mx2 = mn2 = b; 211 fix_mx(); 212 fix_mn(); 213 } 214 215 void add(int x){ 216 mx2 = max(mx2, x); 217 mn2 = min(mn2, x); 218 fix_mx(); 219 fix_mn(); 220 } 221 222 int get_seg(int x){ 223 pair<int, int> res = {mn1, mx1}; 224 if(x == mn1) res.x = mn2; 225 if(x == mx1) res.y = mx2; 226 return res.y - res.x + 1; 227 } 228 }; 229 230 void solve(int tc){ 231 int n; 232 cin >> n; 233 vector<pair<int, int>> coord(n); 234 for(auto &e: coord){ 235 cin >> e.x >> e.y; 236 } 237 if(n <= 2){ 238 cout << n; 239 return; 240 } 241 242 min_max xc(coord[0].x, coord[1].x), yc(coord[0].y, coord[1].y); 243 for(int i = 2; i < n; ++i){ 244 xc.add(coord[i].x); 245 yc.add(coord[i].y); 246 } 247 248 int ans = xc.get_seg(-1) * yc.get_seg(-1); 249 for(int i = 0; i < n; ++i){ 250 int x = xc.get_seg(coord[i].x); 251 int y = yc.get_seg(coord[i].y); 252 if(x * y == n - 1){ 253 ans = min(ans, min((x + 1) * y, x * (y + 1))); 254 } 255 else{ 256 ans = min(ans, x * y); 257 } 258 } 259 cout << ans; 260 } 261 262 bool multi = true; 263 264 signed main() { 265 int t = 1; 266 if (multi)cin >> t; 267 for (int i = 1; i <= t; ++i) { 268 solve(i); 269 cout << "\n"; 270 } 271 return 0; 272 } 273 ``` 274 275 **Rate the problem** 276 277 * Didn't solve 278 * Good task 279 * Average task 280 * Bad task 281 282 [2114E - Kirei Attacks the Estate](/contest/2114/problem/E "Codeforces Round 1027 (Div. 3)") 283 284 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40") 285 286 **Tutorial** 287 288 Tutorial is loading... 289 290 **Solution** 291 292 ``` 293 from math import inf 294 from sys import setrecursionlimit 295 296 def solve(v, p, mini, maxi): 297 global res 298 res[v] = max(arr[v], mini * -1 + arr[v]) 299 mini = min(arr[v], maxi * -1 + arr[v]) 300 for u in gr[v]: 301 if u == p: 302 continue 303 solve(u, v, mini, res[v]) 304 305 setrecursionlimit(400_000) 306 t = int(input()) 307 for _ in range(t): 308 n = int(input()) 309 arr = list(map(int, input().split())) 310 gr = [[] for _ in range(n)] 311 for j in range(n - 1): 312 v, u = map(int, input().split()) 313 gr[v - 1].append(u - 1) 314 gr[u - 1].append(v - 1) 315 res = [0] * n 316 solve(0, -1, 0, 0) 317 print(*res) 318 ``` 319 320 **Rate the problem** 321 322 * Didn't solve 323 * Good task 324 * Average task 325 * Bad task 326 327 [2114F - Small Operations](/contest/2114/problem/F "Codeforces Round 1027 (Div. 3)") 328 329 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya") 330 331 **Tutorial** 332 333 Tutorial is loading... 334 335 **Solution** 336 337 ``` 338 #include <bits/stdc++.h> 339 340 #define int long long 341 #define pb emplace_back 342 #define mp make_pair 343 #define x first 344 #define y second 345 #define all(a) a.begin(), a.end() 346 #define rall(a) a.rbegin(), a.rend() 347 348 typedef long double ld; 349 typedef long long ll; 350 351 using namespace std; 352 353 mt19937 rnd(time(nullptr)); 354 355 const int inf = 1e9; 356 const int M = 1e9 + 7; 357 const ld pi = atan2(0, -1); 358 const ld eps = 1e-6; 359 360 int gcd(int a, int b) { 361 return b == 0 ? a : gcd(b, a % b); 362 } 363 364 int get_ans(int x, int k){ 365 if(x == 1) return 0; 366 vector<int> divs; 367 for(int i = 1; i * i <= x; i++){ 368 if(x % i == 0){ 369 divs.push_back(i); 370 divs.push_back(x / i); 371 } 372 } 373 sort(all(divs)); 374 int n = divs.size(); 375 vector<int> dp(n, 100); 376 dp[0] = 0; 377 for(int i = 1; i < n; i++){ 378 for(int j = i - 1; j >= 0; j--){ 379 if(divs[i] / divs[j] > k){ 380 break; 381 } 382 if(divs[i] % divs[j] == 0) { 383 dp[i] = min(dp[i], dp[j] + 1); 384 } 385 } 386 } 387 return dp[n - 1] == 100 ? -1 : dp[n - 1]; 388 } 389 390 void solve(int tc){ 391 int x, y, k; 392 cin >> x >> y >> k; 393 int g = gcd(x, y); 394 x /= g; 395 y /= g; 396 int ax = get_ans(x, k); 397 int ay = get_ans(y, k); 398 if(ax == -1 || ay == -1) cout << -1; 399 else cout << ax + ay; 400 } 401 402 bool multi = true; 403 404 signed main() { 405 int t = 1; 406 if (multi) cin >> t; 407 for (int i = 1; i <= t; ++i) { 408 solve(i); 409 cout << "\n"; 410 } 411 return 0; 412 } 413 ``` 414 415 **Rate the problem** 416 417 * Didn't solve 418 * Good task 419 * Average task 420 * Bad task 421 422 [2114G - Build an Array](/contest/2114/problem/G "Codeforces Round 1027 (Div. 3)") 423 424 Idea: [myav](/profile/myav "Pupil myav") 425 426 **Tutorial** 427 428 Tutorial is loading... 429 430 **Solution** 431 432 ``` 433 #include <bits/stdc++.h> 434 435 #define int long long 436 #define pb emplace_back 437 #define mp make_pair 438 #define x first 439 #define y second 440 #define all(a) a.begin(), a.end() 441 #define rall(a) a.rbegin(), a.rend() 442 443 typedef long double ld; 444 typedef long long ll; 445 446 using namespace std; 447 448 mt19937 rnd(time(nullptr)); 449 450 const int inf = 1e9; 451 const int M = 1e9 + 7; 452 const ld pi = atan2(0, -1); 453 const ld eps = 1e-6; 454 455 int max_op(int a, int b) { 456 int min_part = a; 457 while (min_part % 2 == 0 && min_part / 2 != b) { 458 min_part /= 2; 459 } 460 if (min_part % 2 == 1) { 461 return a / min_part; 462 } 463 int true_min = min_part; 464 while (true_min % 2 == 0) { 465 true_min /= 2; 466 } 467 return 1 + (a - min_part) / true_min; 468 } 469 470 void solve(int tc){ 471 int n, k; 472 cin >> n >> k; 473 vector<int> a(n); 474 for (int &e: a) cin >> e; 475 vector<int> pre(n, 0); 476 for (int j = 1; j < n; ++j) { 477 pre[j] = pre[j - 1] + max_op(a[j - 1], a[j]); 478 } 479 vector<int> suf(n, 0); 480 for (int j = n - 2; j >= 0; --j) { 481 suf[j] = suf[j + 1] + max_op(a[j + 1], a[j]); 482 } 483 for (int i = 0; i < n; i++) { 484 int res = max_op(a[i], 0) + pre[i] + suf[i]; 485 if (res >= k) { 486 cout << "YES"; 487 return; 488 } 489 } 490 cout << "NO"; 491 } 492 493 bool multi = true; 494 495 signed main() { 496 497 int t = 1; 498 if (multi) cin >> t; 499 for (int i = 1; i <= t; ++i) { 500 solve(i); 501 cout << "\n"; 502 } 503 return 0; 504 } 505 ``` 506 507 **Rate the problem** 508 509 * Didn't solve 510 * Good task 511 * Average task 512 * Bad task