1955.md (11437B)
1 Source: https://codeforces.com/blog/entry/128243 2 3 [1955A - Yogurt Sale](/contest/1955/problem/A "Codeforces Round 938 (Div. 3)") 4 5 Idea: [mainyutin](/profile/mainyutin "Expert mainyutin"), prepared: [mainyutin](/profile/mainyutin "Expert mainyutin") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using ll = signed long long int; 17 18 using namespace std; 19 20 void solve() { 21 ll n, a, b; 22 cin >> n >> a >> b; 23 ll ans = n * a; 24 if (b < 2 * a) { 25 ans = (n / 2) * b + (n % 2) * a; 26 } 27 cout << ans << '\n'; 28 } 29 30 int main() { 31 int t; 32 cin >> t; 33 while (t--) { 34 solve(); 35 } 36 } 37 ``` 38 39 [1955B - Progressive Square](/contest/1955/problem/B "Codeforces Round 938 (Div. 3)") 40 41 Idea: [ssor96](/profile/ssor96 "Master ssor96"), [mainyutin](/profile/mainyutin "Expert mainyutin"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 42 43 **Tutorial** 44 45 Tutorial is loading... 46 47 **Solution** 48 49 ``` 50 #include <bits/stdc++.h> 51 52 using namespace std; 53 54 #define all(x) (x).begin(), (x).end() 55 56 using ll = signed long long int; 57 using pii = pair<int, int>; 58 using pll = pair<ll, ll>; 59 using vi = vector<int>; 60 using vl = vector<ll>; 61 62 void solve() { 63 int n; 64 ll c, d; 65 cin >> n >> c >> d; 66 vl a(n * n); 67 for (int i = 0; i < n * n; ++i) { 68 cin >> a[i]; 69 } 70 sort(all(a)); 71 vl b(n * n); 72 b[0] = a[0]; 73 for (int i = 1; i < n; ++i) { 74 b[i] = b[i - 1] + c; 75 } 76 for (int i = 1; i < n; ++i) { 77 for (int j = 0; j < n; ++j) { 78 b[i * n + j] = b[(i - 1) * n + j] + d; 79 } 80 } 81 sort(all(b)); 82 cout << (a == b ? "YEs" : "nO") << '\n'; 83 } 84 85 int main() { 86 int t; 87 cin >> t; 88 while (t--) { 89 solve(); 90 } 91 } 92 ``` 93 94 [1955C - Inhabitant of the Deep Sea](/contest/1955/problem/C "Codeforces Round 938 (Div. 3)") 95 96 Idea: [ssor96](/profile/ssor96 "Master ssor96"), [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [mainyutin](/profile/mainyutin "Expert mainyutin") 97 98 **Tutorial** 99 100 Tutorial is loading... 101 102 **Solution** 103 104 ``` 105 #include <bits/stdc++.h> 106 107 using namespace std; 108 109 #define all(x) (x).begin(), (x).end() 110 111 using ll = signed long long int; 112 113 void solve() { 114 int n; 115 ll k; 116 cin >> n >> k; 117 deque<ll> dq(n); 118 for (int i = 0; i < n; ++i) { 119 cin >> dq[i]; 120 } 121 while (dq.size() > 1 && k) { 122 ll mn = min(dq.front(), dq.back()); 123 if (k < 2 * mn) { 124 dq.front() -= k / 2 + k % 2; 125 dq.back() -= k / 2; 126 k = 0; 127 } else { 128 dq.front() -= mn; 129 dq.back() -= mn; 130 k -= 2 * mn; 131 } 132 if (dq.front() == 0) { 133 dq.pop_front(); 134 } 135 if (dq.back() == 0) { 136 dq.pop_back(); 137 } 138 } 139 int ans = n - dq.size(); 140 cout << ans + (dq.size() && dq.front() <= k) << '\n'; 141 } 142 143 int main() { 144 int t; 145 cin >> t; 146 while (t--) { 147 solve(); 148 } 149 } 150 ``` 151 152 [1955D - Inaccurate Subsequence Search](/contest/1955/problem/D "Codeforces Round 938 (Div. 3)") 153 154 Idea: [mainyutin](/profile/mainyutin "Expert mainyutin"), [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [mainyutin](/profile/mainyutin "Expert mainyutin") 155 156 **Tutorial** 157 158 Tutorial is loading... 159 160 **Solution** 161 162 ``` 163 #include <bits/stdc++.h> 164 165 using ll = signed long long int; 166 167 #define all(x) (x).begin(), (x).end() 168 169 using pii = std::pair<int, int>; 170 using pll = std::pair<ll, ll>; 171 172 using namespace std; 173 174 void solve() { 175 int n, m; 176 size_t k; 177 cin >> n >> m >> k; 178 vector<int> a(n); 179 for (int i = 0; i < n; ++i) { 180 cin >> a[i]; 181 } 182 multiset<int> todo, done, extra; 183 for (int j = 0; j < m; ++j) { 184 int b; 185 cin >> b; 186 todo.insert(b); 187 } 188 for (int j = 0; j < m; ++j) { 189 if (todo.find(a[j]) != todo.end()) { 190 todo.erase(todo.find(a[j])); 191 done.insert(a[j]); 192 } else { 193 extra.insert(a[j]); 194 } 195 } 196 int ans = (done.size() >= k); 197 for (int r = m; r < n; ++r) { 198 int old = a[r - m]; 199 if (extra.find(old) != extra.end()) { 200 extra.erase(extra.find(old)); 201 } else if (done.find(old) != done.end()) { 202 done.erase(done.find(old)); 203 todo.insert(old); 204 } 205 if (todo.find(a[r]) != todo.end()) { 206 todo.erase(todo.find(a[r])); 207 done.insert(a[r]); 208 } else { 209 extra.insert(a[r]); 210 } 211 ans += (done.size() >= k); 212 } 213 cout << ans << '\n'; 214 } 215 216 int main() { 217 int t; 218 cin >> t; 219 while (t--) { 220 solve(); 221 } 222 } 223 ``` 224 225 [1955E - Long Inversions](/contest/1955/problem/E "Codeforces Round 938 (Div. 3)") 226 227 Idea: [ssor96](/profile/ssor96 "Master ssor96"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 228 229 **Tutorial** 230 231 Tutorial is loading... 232 233 **Solution** 234 235 ``` 236 #include <bits/stdc++.h> 237 238 using ll = signed long long int; 239 240 #define all(x) (x).begin(), (x).end() 241 242 using pii = std::array<int, 2>; 243 using pll = std::array<ll, 2>; 244 using vi = std::vector<int>; 245 using vl = std::vector<ll>; 246 247 using namespace std; 248 249 void solve() { 250 int n; 251 string s; 252 cin >> n >> s; 253 for (int k = n; k > 0; --k) { 254 vector<char> t(n), end(n + 1); 255 for (int i = 0; i < n; ++i) { 256 t[i] = s[i] - '0'; 257 } 258 int cnt = 0; 259 for (int i = 0; i < n; ++i) { 260 cnt -= end[i]; 261 t[i] ^= (cnt & 1); 262 if (t[i] == 0) { 263 if (i + k <= n) { 264 ++end[i + k]; 265 ++cnt; 266 t[i] = 1; 267 } else { 268 break; 269 } 270 } 271 } 272 if (*min_element(all(t)) == 1) { 273 cout << k << '\n'; 274 return; 275 } 276 } 277 assert(false); 278 } 279 280 int main() { 281 int t; 282 cin >> t; 283 while (t--) { 284 solve(); 285 } 286 } 287 ``` 288 289 [1955F - Unfair Game](/contest/1955/problem/F "Codeforces Round 938 (Div. 3)") 290 291 Idea: [mainyutin](/profile/mainyutin "Expert mainyutin"), prepared: [mainyutin](/profile/mainyutin "Expert mainyutin") 292 293 **Tutorial** 294 295 Tutorial is loading... 296 297 **Solution** 298 299 ``` 300 #include <bits/stdc++.h> 301 302 using namespace std; 303 304 const int N = 201; 305 306 int dp[N][N][N]; 307 308 void precalc() { 309 dp[0][0][0] = 0; 310 for (int i = 0; i < N; ++i) { 311 for (int j = 0; j < N; ++j) { 312 for (int k = 0; k < N; ++k) { 313 int prev = 0; 314 if (i) prev = max(prev, dp[i - 1][j][k]); 315 if (j) prev = max(prev, dp[i][j - 1][k]); 316 if (k) prev = max(prev, dp[i][j][k - 1]); 317 dp[i][j][k] = prev; 318 int xr = ((i & 1) * 1) ^ ((j & 1) * 2) ^ ((k & 1) * 3); 319 if (xr == 0 && (i || j || k)) { 320 ++dp[i][j][k]; 321 } 322 } 323 } 324 } 325 } 326 327 void solve() { 328 vector<int> cnt(4); 329 for (int i = 0; i < 4; ++i) { 330 cin >> cnt[i]; 331 } 332 cout << dp[cnt[0]][cnt[1]][cnt[2]] + cnt[3] / 2 << '\n'; 333 } 334 335 int main() { 336 precalc(); 337 int t; 338 cin >> t; 339 while (t--) { 340 solve(); 341 } 342 } 343 ``` 344 345 [1955G - GCD on a grid](/contest/1955/problem/G "Codeforces Round 938 (Div. 3)") 346 347 Idea: [ZergTricky](/profile/ZergTricky "Master ZergTricky"), prepared: [mainyutin](/profile/mainyutin "Expert mainyutin") 348 349 **Tutorial** 350 351 Tutorial is loading... 352 353 **Solution** 354 355 ``` 356 #include <bits/stdc++.h> 357 358 using ll = signed long long int; 359 360 #define all(x) (x).begin(), (x).end() 361 362 using pii = std::pair<int, int>; 363 using pll = std::pair<ll, ll>; 364 365 using namespace std; 366 367 void solve() { 368 int n, m; 369 cin >> n >> m; 370 vector<vector<int> > a(n, vector<int>(m)); 371 for (int i = 0; i < n; ++i) { 372 for (int j = 0; j < m; ++j) { 373 cin >> a[i][j]; 374 } 375 } 376 int ans = 1, g = gcd(a[0][0], a[n - 1][m - 1]); 377 vector<vector<char> > dp(n, vector<char>(m)); 378 for (int x = 1; x * x <= g; ++x) { 379 if (g % x > 0) { 380 continue; 381 } 382 vector<int> cand = {x, g / x}; 383 for (int el : cand) { 384 for (int i = 0; i < n; ++i) { 385 dp[i].assign(m, 0); 386 } 387 dp[0][0] = 1; 388 for (int i = 0; i < n; ++i) { 389 for (int j = 0; j < m; ++j) { 390 if (a[i][j] % el > 0) { 391 continue; 392 } 393 if (!dp[i][j] && i) { 394 dp[i][j] = (dp[i - 1][j] == 1 ? 1 : 0); 395 } 396 if (!dp[i][j] && j) { 397 dp[i][j] = (dp[i][j - 1] == 1 ? 1 : 0); 398 } 399 } 400 } 401 if (dp[n - 1][m - 1]) { 402 ans = max(ans, el); 403 } 404 } 405 } 406 cout << ans << '\n'; 407 } 408 409 int main() { 410 int t; 411 cin >> t; 412 while (t--) { 413 solve(); 414 } 415 } 416 ``` 417 418 [1955H - The Most Reckless Defense](/contest/1955/problem/H "Codeforces Round 938 (Div. 3)") 419 420 Idea: [VManoshin](/profile/VManoshin "Expert VManoshin"), prepared: [mainyutin](/profile/mainyutin "Expert mainyutin") 421 422 **Tutorial** 423 424 Tutorial is loading... 425 426 **Solution** 427 428 ``` 429 #include <bits/stdc++.h> 430 431 using ll = signed long long int; 432 433 #define all(x) (x).begin(), (x).end() 434 435 using pii = std::pair<int, int>; 436 using pll = std::pair<ll, ll>; 437 438 using namespace std; 439 440 const int R = 12, INF = 2e9; 441 442 bool check(int x, int n) { return (0 <= x && x < n); } 443 444 void solve() { 445 int n, m, k; 446 cin >> n >> m >> k; 447 vector<string> gr(n); 448 for (int i = 0; i < n; ++i) { 449 cin >> gr[i]; 450 } 451 vector<pii> cord(k); 452 vector<int> p(k); 453 for (int i = 0; i < k; ++i) { 454 cin >> cord[i].first >> cord[i].second >> p[i]; 455 --cord[i].first; 456 --cord[i].second; 457 } 458 vector<vector<int> > cover(k, vector<int>(R + 1)); 459 for (int i = 0; i < k; ++i) { 460 int x = cord[i].first; 461 int y = cord[i].second; 462 for (int r = 1; r <= R; ++r) { 463 for (int dx = -r; dx <= r; ++dx) { 464 for (int dy = -r; dy <= r; ++dy) { 465 int nx = x + dx; 466 int ny = y + dy; 467 if (!check(nx, n) || !check(ny, m)) { 468 continue; 469 } 470 if ((x - nx) * (x - nx) + (y - ny) * (y - ny) <= r * r) { 471 cover[i][r] += (gr[nx][ny] == '#'); 472 } 473 } 474 } 475 } 476 } 477 vector<vector<int> > dp(k + 1, vector<int>(1 << R, -INF)); 478 dp[0][0] = 0; 479 for (int i = 1; i <= k; ++i) { 480 for (int mask = 0; mask < (1 << R); ++mask) { 481 dp[i][mask] = dp[i - 1][mask]; 482 for (int r = 1; r <= R; ++r) { 483 int j = r - 1; 484 if (!(mask & (1 << j))) { 485 continue; 486 } 487 dp[i][mask] = max(dp[i][mask], dp[i - 1][mask ^ (1 << j)] + 488 p[i - 1] * cover[i - 1][r]); 489 } 490 } 491 } 492 int ans = 0; 493 for (int mask = 0; mask < (1 << R); ++mask) { 494 int hp = 0, mlt = 3; 495 for (int j = 0; j < R; ++j) { 496 if (mask & (1 << j)) { 497 hp += mlt; 498 } 499 mlt *= 3; 500 } 501 for (int i = 0; i <= k; ++i) { 502 ans = max(ans, dp[i][mask] - hp); 503 } 504 } 505 cout << ans << '\n'; 506 } 507 508 int main() { 509 int t; 510 cin >> t; 511 while (t--) { 512 solve(); 513 } 514 } 515 ```