1840.md (10451B)
1 Source: https://codeforces.com/blog/entry/117060 2 3 [1840A - Cipher Shifer](/contest/1840/problem/A "Codeforces Round 878 (Div. 3)") 4 5 Idea: [isosto](/profile/isosto "Candidate Master isosto"), preparation: [isosto](/profile/isosto "Candidate Master isosto") 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 int main() { 19 int t; cin >> t; 20 while (t--) { 21 int n; cin >> n; 22 string s; cin >> s; 23 int i = 0; 24 while (i < n) { 25 int start = i; 26 cout << s[i++]; 27 while (s[i++] != s[start]); 28 } 29 cout << endl; 30 } 31 } 32 ``` 33 34 **Rate the problem** 35 36 * Didn't solve 37 * Good task 38 * Average task 39 * Bad task 40 41 [1840B - Binary Cafe](/contest/1840/problem/B "Codeforces Round 878 (Div. 3)") 42 43 Idea: [diskoteka](/profile/diskoteka "Master diskoteka"), preparation: [diskoteka](/profile/diskoteka "Master diskoteka") 44 45 **Tutorial** 46 47 Tutorial is loading... 48 49 **Solution** 50 51 ``` 52 #include <bits/stdc++.h> 53 54 using namespace std; 55 56 int32_t main() { 57 int t; 58 cin >> t; 59 while (t--) { 60 int n, k; 61 cin >> n >> k; 62 k = min(k, 30); 63 cout << min(n, (1 << k) - 1) + 1 << "\n"; 64 } 65 return 0; 66 } 67 ``` 68 69 **Rate the problem** 70 71 * Didn't solve 72 * Good task 73 * Average task 74 * Bad task 75 76 [1840C - Ski Resort](/contest/1840/problem/C "Codeforces Round 878 (Div. 3)") 77 78 Idea: [pavlekn](/profile/pavlekn "Master pavlekn"), preparation: [playerr17](/profile/playerr17 "Expert playerr17") 79 80 **Tutorial** 81 82 Tutorial is loading... 83 84 **Solution** 85 86 ``` 87 testCases = int(input()) 88 89 for testCase in range(testCases): 90 n, k, q = map(int, input().split(' ')) 91 a = list(map(int, input().split(' '))) 92 93 ans = 0 94 len = 0 95 for i in range(n): 96 if a[i] <= q: 97 len += 1 98 else: 99 if len >= k: 100 ans += (len - k + 1) * (len - k + 2) // 2 101 len = 0 102 103 if len >= k: 104 ans += (len - k + 1) * (len - k + 2) // 2 105 print(ans) 106 ``` 107 108 **Rate the problem** 109 110 * Didn't solve 111 * Good task 112 * Average task 113 * Bad task 114 115 [1840D - Wooden Toy Festival](/contest/1840/problem/D "Codeforces Round 878 (Div. 3)") 116 117 Idea: [diskoteka](/profile/diskoteka "Master diskoteka"), preparation: [diskoteka](/profile/diskoteka "Master diskoteka") 118 119 **Tutorial** 120 121 Tutorial is loading... 122 123 **Solution** 124 125 ``` 126 #include <bits/stdc++.h> 127 128 using namespace std; 129 130 int main() { 131 int t; 132 cin >> t; 133 while (t--) { 134 int n; 135 cin >> n; 136 vector<int> a(n); 137 for (int i = 0; i < n; ++i) { 138 cin >> a[i]; 139 } 140 sort(a.begin(), a.end()); 141 int l = -1, r = 1e9; 142 while (r - l > 1) { 143 int m = (l + r) >> 1; 144 int i = 0; 145 while (i + 1 < a.size() && a[i + 1] - a[0] <= 2 * m) { 146 ++i; 147 } 148 int j = n - 1; 149 while (j - 1 >= 0 && a.back() - a[j - 1] <= 2 * m) { 150 --j; 151 } 152 ++i; --j; 153 if (i > j || a[j] - a[i] <= 2 * m) { 154 r = m; 155 } else { 156 l = m; 157 } 158 } 159 cout << r << "\n"; 160 } 161 return 0; 162 } 163 ``` 164 165 **Rate the problem** 166 167 * Didn't solve 168 * Good task 169 * Average task 170 * Bad task 171 172 [1840E - Character Blocking](/contest/1840/problem/E "Codeforces Round 878 (Div. 3)") 173 174 Idea: [diskoteka](/profile/diskoteka "Master diskoteka"), preparation: [diskoteka](/profile/diskoteka "Master diskoteka") 175 176 **Tutorial** 177 178 Tutorial is loading... 179 180 **Solution** 181 182 ``` 183 #include <bits/stdc++.h> 184 185 using namespace std; 186 187 int main() { 188 int x; 189 cin >> x; 190 while (x--) { 191 vector<string> s(2); 192 cin >> s[0] >> s[1]; 193 int n = s[0].size(); 194 int bad = 0; 195 for (int i = 0; i < n; ++i) { 196 if (s[0][i] != s[1][i]) { 197 ++bad; 198 } 199 } 200 int t, q; 201 cin >> t >> q; 202 queue<pair<int, int>> unblock; 203 for (int i = 0; i < q; ++i) { 204 while (!unblock.empty() && unblock.front().first == i) { 205 if (s[0][unblock.front().second] != s[1][unblock.front().second]) { 206 ++bad; 207 } 208 unblock.pop(); 209 } 210 int type; 211 cin >> type; 212 if (type == 1) { 213 int pos; 214 cin >> pos; 215 if (s[0][pos - 1] != s[1][pos - 1]) { 216 --bad; 217 } 218 unblock.emplace(i + t, pos - 1); 219 } else if (type == 2) { 220 int num1, pos1, num2, pos2; 221 cin >> num1 >> pos1 >> num2 >> pos2; 222 --num1; --pos1; --num2; --pos2; 223 if (s[num1][pos1] != s[1 ^ num1][pos1]) { 224 --bad; 225 } 226 if (s[num2][pos2] != s[1 ^ num2][pos2]) { 227 --bad; 228 } 229 swap(s[num1][pos1], s[num2][pos2]); 230 if (s[num1][pos1] != s[1 ^ num1][pos1]) { 231 ++bad; 232 } 233 if (s[num2][pos2] != s[1 ^ num2][pos2]) { 234 ++bad; 235 } 236 } else { 237 cout << (!bad ? "YES" : "NO") << "\n"; 238 } 239 } 240 } 241 return 0; 242 } 243 ``` 244 245 **Rate the problem** 246 247 * Didn't solve 248 * Good task 249 * Average task 250 * Bad task 251 252 [1840F - Railguns](/contest/1840/problem/F "Codeforces Round 878 (Div. 3)") 253 254 Idea: [diskoteka](/profile/diskoteka "Master diskoteka"), preparation: [diskoteka](/profile/diskoteka "Master diskoteka") 255 256 **Tutorial** 257 258 Tutorial is loading... 259 260 **Solution** 261 262 ``` 263 #include <bits/stdc++.h> 264 265 using namespace std; 266 267 int main() { 268 ios_base::sync_with_stdio(false); 269 cin.tie(0); cout.tie(0); 270 int q; 271 cin >> q; 272 while (q--) { 273 int n, m; 274 cin >> n >> m; 275 int r; 276 cin >> r; 277 bool free[n + 1][m + 1][r + 1]; 278 for (int i = 0; i <= n; ++i) { 279 for (int j = 0; j <= m; ++j) { 280 for (int k = 0; k <= r; ++k) { 281 free[i][j][k] = true; 282 } 283 } 284 } 285 for (int i = 0; i < r; ++i) { 286 int t, d, coord; 287 cin >> t >> d >> coord; 288 if (d == 1) { 289 for (int j = 0; j <= m; ++j) { 290 if (0 <= t - coord - j && t - coord - j <= r) { 291 free[coord][j][t - coord - j] = false; 292 } 293 } 294 } else { 295 for (int j = 0; j <= n; ++j) { 296 if (0 <= t - coord - j && t - coord - j <= r) { 297 free[j][coord][t - coord - j] = false; 298 } 299 } 300 } 301 } 302 bool dp[n + 1][m + 1][r + 1]; 303 for (int i = 0; i <= n; ++i) { 304 for (int j = 0; j <= m; ++j) { 305 for (int k = 0; k <= r; ++k) { 306 dp[i][j][k] = !(i || j || k); 307 if (free[i][j][k]) { 308 if (i && dp[i - 1][j][k]) { 309 dp[i][j][k] = true; 310 } 311 if (j && dp[i][j - 1][k]) { 312 dp[i][j][k] = true; 313 } 314 if (k && dp[i][j][k - 1]) { 315 dp[i][j][k] = true; 316 } 317 } 318 } 319 } 320 } 321 int ans = -1; 322 for (int t = r; t >= 0; --t) { 323 if (dp[n][m][t]) { 324 ans = n + m + t; 325 } 326 } 327 cout << ans << "\n"; 328 } 329 return 0; 330 } 331 ``` 332 333 **Rate the problem** 334 335 * Didn't solve 336 * Good task 337 * Average task 338 * Bad task 339 340 [1840G1 - In Search of Truth (Easy Version)](/contest/1840/problem/G1 "Codeforces Round 878 (Div. 3)") 341 342 Idea: [pavlekn](/profile/pavlekn "Master pavlekn"), preparation: [pavlekn](/profile/pavlekn "Master pavlekn") 343 344 **Tutorial** 345 346 Tutorial is loading... 347 348 **Solution** 349 350 ``` 351 #include <bits/stdc++.h> 352 353 using namespace std; 354 355 #define int long long 356 357 const int MAXN = 1e6 + 7; 358 359 int pos[MAXN]; 360 361 int32_t main() { 362 int num; 363 cin >> num; 364 int ans = 0; 365 int cur = 1; 366 pos[num] = 1; 367 for (int i = 0; i < 1000; ++i) { 368 cout << '+' << " " << 1 << endl; 369 ++cur; 370 cin >> num; 371 if (pos[num]) { 372 cout << '!' << " " << cur - pos[num] << endl; 373 return 0; 374 } 375 pos[num] = cur; 376 } 377 while (true) { 378 cout << '+' << " " << 1000 << endl; 379 cur += 1000; 380 cin >> num; 381 if (pos[num]) { 382 cout << '!' << " " << cur - pos[num] << endl; 383 return 0; 384 } 385 pos[num] = cur; 386 } 387 return 0; 388 } 389 ``` 390 391 **Rate the problem** 392 393 * Didn't solve 394 * Good task 395 * Average task 396 * Bad task 397 398 [1840G2 - In Search of Truth (Hard Version)](/contest/1840/problem/G2 "Codeforces Round 878 (Div. 3)") 399 400 Idea: [pavlekn](/profile/pavlekn "Master pavlekn"), preparation: [pavlekn](/profile/pavlekn "Master pavlekn") 401 402 **Tutorial** 403 404 Tutorial is loading... 405 406 **Solution** 407 408 ``` 409 #include <bits/stdc++.h> 410 411 using namespace std; 412 413 #define int long long 414 415 const int MAXN = 1e6 + 7; 416 417 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 418 419 int pos[MAXN]; 420 421 const int K = 400; 422 const int T = 300; 423 424 int get() { 425 return rng() % MAXN; 426 } 427 428 int32_t main() { 429 int num; 430 cin >> num; 431 int start = num; 432 int cur_delta = 0; 433 int N0 = num; 434 for (int i = 0; i < K; ++i) { 435 int delta = get(); 436 cout << '+' << " " << delta << endl; 437 cur_delta += delta; 438 cin >> num; 439 N0 = max(N0, num); 440 } 441 cout << '-' << " " << cur_delta << endl; 442 cin >> num; 443 cout << '+' << " " << N0 - 1 << endl; 444 cur_delta = N0 - 1; 445 cin >> num; 446 pos[num] = N0; 447 for (int i = 0; i < T; ++i) { 448 ++cur_delta; 449 cout << '+' << " " << 1 << endl; 450 cin >> num; 451 pos[num] = N0 + i + 1; 452 if (num == start) { 453 cout << '!' << " " << N0 + i << endl; 454 return 0; 455 } 456 } 457 cout << '-' << " " << cur_delta << endl; 458 cin >> num; 459 int ans = 0; 460 while (true) { 461 cout << '-' << " " << T << endl; 462 ans += T; 463 cin >> num; 464 if (pos[num]) { 465 cout << '!' << " " << ans + pos[num] - 1 << endl; 466 return 0; 467 } 468 } 469 return 0; 470 } 471 ``` 472 473 **Rate the problem** 474 475 * Didn't solve 476 * Good task 477 * Average task 478 * Bad task