1409.md (8339B)
1 Source: https://codeforces.com/blog/entry/82284 2 3 I'm so thankful to all testers, especially to [Gassa](/profile/Gassa "Grandmaster Gassa") and [Rox](/profile/Rox "Candidate Master Rox") for their invaluable help! 4 5 [1409A - Yet Another Two Integers Problem](/contest/1409/problem/A "Codeforces Round 667 (Div. 3)") 6 7 Idea: [vovuh](/profile/vovuh "Master vovuh") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution** 14 15 ``` 16 #include <bits/stdc++.h> 17 18 using namespace std; 19 20 int main() { 21 #ifdef _DEBUG 22 freopen("input.txt", "r", stdin); 23 // freopen("output.txt", "w", stdout); 24 #endif 25 26 int t; 27 cin >> t; 28 while (t--) { 29 int a, b; 30 cin >> a >> b; 31 cout << (abs(a - b) + 9) / 10 << endl; 32 } 33 34 return 0; 35 } 36 ``` 37 38 [1409B - Minimum Product](/contest/1409/problem/B "Codeforces Round 667 (Div. 3)") 39 40 Idea: [vovuh](/profile/vovuh "Master vovuh") 41 42 **Tutorial** 43 44 Tutorial is loading... 45 46 **Solution** 47 48 ``` 49 #include <bits/stdc++.h> 50 51 using namespace std; 52 53 int main() { 54 #ifdef _DEBUG 55 freopen("input.txt", "r", stdin); 56 // freopen("output.txt", "w", stdout); 57 #endif 58 59 int t; 60 cin >> t; 61 while (t--) { 62 int a, b, x, y, n; 63 cin >> a >> b >> x >> y >> n; 64 long long ans = 1e18; 65 for (int i = 0; i < 2; ++i) { 66 int da = min(n, a - x); 67 int db = min(n - da, b - y); 68 ans = min(ans, (a - da) * 1ll * (b - db)); 69 swap(a, b); 70 swap(x, y); 71 } 72 cout << ans << endl; 73 } 74 75 return 0; 76 } 77 ``` 78 79 [1409C - Yet Another Array Restoration](/contest/1409/problem/C "Codeforces Round 667 (Div. 3)") 80 81 Idea: [vovuh](/profile/vovuh "Master vovuh") 82 83 **Tutorial** 84 85 Tutorial is loading... 86 87 **Solution (Gassa)** 88 89 ``` 90 // Author: Ivan Kazmenko ([email protected]) 91 module solution; 92 import std.algorithm; 93 import std.conv; 94 import std.range; 95 import std.stdio; 96 import std.string; 97 98 void main () 99 { 100 auto tests = readln.strip.to !(int); 101 foreach (test; 0..tests) 102 { 103 int n, x, y; 104 readf !(" %s %s %s") (n, x, y); 105 auto answer = int.max.repeat (n).array; 106 foreach (start; 1..51) 107 { 108 foreach (d; 1..51) 109 { 110 auto a = iota (start, start + d * n, d).array; 111 if (a.canFind (x) && a.canFind (y)) 112 { 113 if (answer.back > a.back) 114 { 115 answer = a; 116 } 117 } 118 } 119 } 120 writefln !("%(%s %)") (answer); 121 } 122 } 123 ``` 124 125 **Solution (vovuh)** 126 127 ``` 128 #include <bits/stdc++.h> 129 130 using namespace std; 131 132 int main() { 133 #ifdef _DEBUG 134 freopen("input.txt", "r", stdin); 135 // freopen("output.txt", "w", stdout); 136 #endif 137 138 int t; 139 cin >> t; 140 while (t--) { 141 int n, x, y; 142 cin >> n >> x >> y; 143 vector<int> ans; 144 for (int d = 1; d <= y - x; ++d) { 145 if ((y - x) % d != 0) continue; 146 vector<int> res; 147 bool foundx = false; 148 int cur = y; 149 int need = n; 150 while (cur >= 1 && need > 0) { 151 res.push_back(cur); 152 foundx |= cur == x; 153 --need; 154 cur -= d; 155 } 156 cur = y; 157 while (need > 0) { 158 cur += d; 159 res.push_back(cur); 160 --need; 161 } 162 sort(res.begin(), res.end()); 163 if (need == 0 && foundx) { 164 if (ans.empty() || ans.back() > res.back()) { 165 ans = res; 166 } 167 } 168 } 169 assert(!ans.empty()); 170 for (auto it : ans) cout << it << " "; 171 cout << endl; 172 173 } 174 175 return 0; 176 } 177 ``` 178 179 **Solution (Rox)** 180 181 ``` 182 #include <bits/stdc++.h> 183 184 using namespace std; 185 186 int main() { 187 int tcs; 188 cin >> tcs; 189 190 while (tcs--) { 191 int n, x, y; 192 cin >> n >> x >> y; 193 int diff = y - x; 194 for (int delta = 1; delta <= diff; ++delta) { 195 if (diff % delta) continue; 196 if (diff / delta + 1 > n) continue; 197 int k = min((y - 1) / delta, n - 1); 198 int a0 = y - k * delta; 199 for (int i = 0; i < n; ++i) { 200 cout << (a0 + i * delta) << ' '; 201 } 202 cout << endl; 203 break; 204 } 205 } 206 } 207 ``` 208 209 [1409D - Decrease the Sum of Digits](/contest/1409/problem/D "Codeforces Round 667 (Div. 3)") 210 211 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 212 213 **Tutorial** 214 215 Tutorial is loading... 216 217 **Solution** 218 219 ``` 220 #include <bits/stdc++.h> 221 222 using namespace std; 223 224 int sum(long long n) { 225 int res = 0; 226 while (n > 0) { 227 res += n % 10; 228 n /= 10; 229 } 230 return res; 231 } 232 233 int main() { 234 #ifdef _DEBUG 235 freopen("input.txt", "r", stdin); 236 // freopen("output.txt", "w", stdout); 237 #endif 238 239 int t; 240 cin >> t; 241 while (t--) { 242 long long n; 243 int s; 244 cin >> n >> s; 245 long long ans = 0; 246 if (sum(n) <= s) { 247 cout << 0 << endl; 248 continue; 249 } 250 long long pw = 1; 251 for (int i = 0; i < 18; ++i) { 252 int digit = (n / pw) % 10; 253 long long add = pw * ((10 - digit) % 10); 254 n += add; 255 ans += add; 256 if (sum(n) <= s) { 257 break; 258 } 259 pw *= 10; 260 } 261 cout << ans << endl; 262 } 263 264 return 0; 265 } 266 ``` 267 268 [1409E - Two Platforms](/contest/1409/problem/E "Codeforces Round 667 (Div. 3)") 269 270 Idea: [vovuh](/profile/vovuh "Master vovuh") 271 272 **Tutorial** 273 274 Tutorial is loading... 275 276 **Solution** 277 278 ``` 279 #include <bits/stdc++.h> 280 281 using namespace std; 282 283 int main() { 284 #ifdef _DEBUG 285 freopen("input.txt", "r", stdin); 286 // freopen("output.txt", "w", stdout); 287 #endif 288 289 int t; 290 cin >> t; 291 while (t--) { 292 int n, k; 293 cin >> n >> k; 294 vector<int> x(n), y(n); 295 for (auto &it : x) cin >> it; 296 for (auto &it : y) cin >> it; 297 sort(x.begin(), x.end()); 298 int j = n - 1; 299 vector<int> l(n), r(n); 300 for (int i = n - 1; i >= 0; --i) { 301 while (x[j] - x[i] > k) --j; 302 r[i] = j - i + 1; 303 if (i + 1 < n) r[i] = max(r[i], r[i + 1]); 304 } 305 j = 0; 306 for (int i = 0; i < n; ++i) { 307 while (x[i] - x[j] > k) ++j; 308 l[i] = i - j + 1; 309 if (i > 0) l[i] = max(l[i], l[i - 1]); 310 } 311 int ans = 1; 312 for (int i = 0; i < n - 1; ++i) { 313 ans = max(ans, r[i + 1] + l[i]); 314 } 315 cout << ans << endl; 316 } 317 318 return 0; 319 } 320 ``` 321 322 [1409F - Subsequences of Length Two](/contest/1409/problem/F "Codeforces Round 667 (Div. 3)") 323 324 Idea: [vovuh](/profile/vovuh "Master vovuh") 325 326 **Tutorial** 327 328 Tutorial is loading... 329 330 **Solution** 331 332 ``` 333 #include <bits/stdc++.h> 334 335 using namespace std; 336 337 const int INF = 1e9; 338 339 int main() { 340 #ifdef _DEBUG 341 freopen("input.txt", "r", stdin); 342 // freopen("output.txt", "w", stdout); 343 #endif 344 345 int n, k; 346 string s, t; 347 cin >> n >> k >> s >> t; 348 vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF))); 349 dp[0][0][0] = 0; 350 for (int i = 0; i < n; ++i) { 351 for (int ck = 0; ck <= k; ++ck) { 352 for (int cnt0 = 0; cnt0 <= n; ++cnt0) { 353 if (dp[i][ck][cnt0] == -INF) continue; 354 int e0 = s[i] == t[0]; 355 int e1 = s[i] == t[1]; 356 int e01 = t[0] == t[1]; 357 358 dp[i + 1][ck][cnt0 + e0] = max(dp[i + 1][ck][cnt0 + e0], dp[i][ck][cnt0] + (e1 ? cnt0 : 0)); 359 360 if (ck < k) { 361 dp[i + 1][ck + 1][cnt0 + 1] = max(dp[i + 1][ck + 1][cnt0 + 1], dp[i][ck][cnt0] + (e01 ? cnt0 : 0)); 362 dp[i + 1][ck + 1][cnt0 + e01] = max(dp[i + 1][ck + 1][cnt0 + e01], dp[i][ck][cnt0] + cnt0); 363 } 364 } 365 } 366 } 367 368 int ans = 0; 369 for (int ck = 0; ck <= k; ++ck) { 370 for (int cnt0 = 0; cnt0 <= n; ++cnt0) { 371 ans = max(ans, dp[n][ck][cnt0]); 372 } 373 } 374 375 cout << ans << endl; 376 377 return 0; 378 } 379 ``` 380 381 **Solution (Gassa, greedy, O(n^4))** 382 383 ``` 384 // Author: Ivan Kazmenko ([email protected]) 385 module solution; 386 import std.algorithm; 387 import std.conv; 388 import std.range; 389 import std.stdio; 390 import std.string; 391 392 void main () 393 { 394 int n, k; 395 while (readf !(" %s %s") (n, k) > 0) 396 { 397 readln; 398 auto s0 = readln.strip; 399 auto t = readln.strip; 400 auto s = s0.dup; 401 int res = 0; 402 foreach (b0; 0..k + 1) 403 { 404 auto e0 = k - b0; 405 loop_x0: 406 foreach (x0; 0..b0 + 1) 407 { 408 loop_y0: 409 foreach (y0; 0..e0 + 1) 410 { 411 int b = b0; 412 int e = e0; 413 int x = x0; 414 int y = y0; 415 s[] = s0[]; 416 for (int i = 0; i < n && b; i++) 417 { 418 if (s[i] == t[0]) 419 { 420 } 421 else if (s[i] != t[1]) 422 { 423 s[i] = t[0]; 424 b -= 1; 425 } 426 else if (x > 0) 427 { 428 s[i] = t[0]; 429 x -= 1; 430 b -= 1; 431 } 432 } 433 434 for (int j = n - 1; j >= 0 && e; j--) 435 { 436 if (s[j] == t[1]) 437 { 438 } 439 else if (s[j] != t[0]) 440 { 441 s[j] = t[1]; 442 e -= 1; 443 } 444 else if (y > 0) 445 { 446 s[j] = t[1]; 447 y -= 1; 448 e -= 1; 449 } 450 } 451 452 int cur = 0; 453 int add = 0; 454 for (int i = 0; i < n; i++) 455 { 456 if (s[i] == t[1]) 457 { 458 cur += add; 459 } 460 if (s[i] == t[0]) 461 { 462 add += 1; 463 } 464 } 465 res = max (res, cur); 466 467 if (x > 0) 468 { 469 break loop_x0; 470 } 471 if (y > 0) 472 { 473 break loop_y0; 474 } 475 } 476 } 477 } 478 479 writeln (res); 480 } 481 } 482 ```