1374.md (8774B)
1 Source: https://codeforces.com/blog/entry/79517 2 3 [1374A - Required Remainder](/contest/1374/problem/A "Codeforces Round 653 (Div. 3)") 4 5 Idea: [vovuh](/profile/vovuh "Master vovuh") 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 #ifdef _DEBUG 20 freopen("input.txt", "r", stdin); 21 // freopen("output.txt", "w", stdout); 22 #endif 23 24 int t; 25 cin >> t; 26 while (t--) { 27 int x, y, n; 28 cin >> x >> y >> n; 29 if (n - n % x + y <= n) { 30 cout << n - n % x + y << endl; 31 } else { 32 cout << n - n % x - (x - y) << endl; 33 } 34 } 35 36 return 0; 37 } 38 ``` 39 40 [1374B - Multiply by 2, divide by 6](/contest/1374/problem/B "Codeforces Round 653 (Div. 3)") 41 42 Idea: [vovuh](/profile/vovuh "Master vovuh") 43 44 **Tutorial** 45 46 Tutorial is loading... 47 48 **Solution** 49 50 ``` 51 #include <bits/stdc++.h> 52 53 using namespace std; 54 55 int main() { 56 #ifdef _DEBUG 57 freopen("input.txt", "r", stdin); 58 // freopen("output.txt", "w", stdout); 59 #endif 60 61 int t; 62 cin >> t; 63 while (t--) { 64 int n; 65 cin >> n; 66 int cnt2 = 0, cnt3 = 0; 67 while (n % 2 == 0) { 68 n /= 2; 69 ++cnt2; 70 } 71 while (n % 3 == 0) { 72 n /= 3; 73 ++cnt3; 74 } 75 if (n == 1 && cnt2 <= cnt3) { 76 cout << 2 * cnt3 - cnt2 << endl; 77 } else { 78 cout << -1 << endl; 79 } 80 } 81 82 return 0; 83 } 84 ``` 85 86 [1374C - Move Brackets](/contest/1374/problem/C "Codeforces Round 653 (Div. 3)") 87 88 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 89 90 **Tutorial** 91 92 Tutorial is loading... 93 94 **Solution** 95 96 ``` 97 #include <bits/stdc++.h> 98 99 using namespace std; 100 101 int main() { 102 #ifdef _DEBUG 103 freopen("input.txt", "r", stdin); 104 // freopen("output.txt", "w", stdout); 105 #endif 106 107 int t; 108 cin >> t; 109 while (t--) { 110 int n; 111 string s; 112 cin >> n >> s; 113 int ans = 0; 114 int bal = 0; 115 for (int i = 0; i < n; ++i) { 116 if (s[i] == '(') ++bal; 117 else { 118 --bal; 119 if (bal < 0) { 120 bal = 0; 121 ++ans; 122 } 123 } 124 } 125 cout << ans << endl; 126 } 127 128 return 0; 129 } 130 ``` 131 132 [1374D - Zero Remainder Array](/contest/1374/problem/D "Codeforces Round 653 (Div. 3)") 133 134 Idea: [vovuh](/profile/vovuh "Master vovuh") 135 136 **Tutorial** 137 138 Tutorial is loading... 139 140 **Solution** 141 142 ``` 143 #include <bits/stdc++.h> 144 145 using namespace std; 146 147 int main() { 148 #ifdef _DEBUG 149 freopen("input.txt", "r", stdin); 150 // freopen("output.txt", "w", stdout); 151 #endif 152 153 int t; 154 cin >> t; 155 while (t--) { 156 int n, k; 157 cin >> n >> k; 158 vector<int> a(n); 159 for (auto &it : a) cin >> it; 160 map<int, int> cnt; 161 int mx = 0; 162 for (auto &it : a) { 163 if (it % k == 0) continue; 164 ++cnt[k - it % k]; 165 mx = max(mx, cnt[k - it % k]); 166 } 167 long long ans = 0; 168 for (auto [key, value] : cnt) { 169 if (value == mx) { 170 ans = k * 1ll * (value - 1) + key + 1; 171 } 172 } 173 cout << ans << endl; 174 } 175 176 return 0; 177 } 178 ``` 179 180 [1374E1 - Reading Books (easy version)](/contest/1374/problem/E1 "Codeforces Round 653 (Div. 3)") 181 182 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 183 184 **Tutorial** 185 186 Tutorial is loading... 187 188 **Solution** 189 190 ``` 191 #include <bits/stdc++.h> 192 193 using namespace std; 194 195 const int INF = 2e9 + 1; 196 197 int main() { 198 #ifdef _DEBUG 199 freopen("input.txt", "r", stdin); 200 // freopen("output.txt", "w", stdout); 201 #endif 202 203 int n, k; 204 cin >> n >> k; 205 vector<int> times[4]; 206 vector<int> sums[4]; 207 for (int i = 0; i < n; ++i) { 208 int t, a, b; 209 cin >> t >> a >> b; 210 times[a * 2 + b].push_back(t); 211 } 212 for (int i = 0; i < 4; ++i) { 213 sort(times[i].begin(), times[i].end()); 214 sums[i].push_back(0); 215 for (auto it : times[i]) { 216 sums[i].push_back(sums[i].back() + it); 217 } 218 } 219 220 int ans = INF; 221 for (int cnt = 0; cnt < min(k + 1, int(sums[3].size())); ++cnt) { 222 if (k - cnt < int(sums[1].size()) && k - cnt < int(sums[2].size())) { 223 ans = min(ans, sums[3][cnt] + sums[1][k - cnt] + sums[2][k - cnt]); 224 } 225 } 226 227 if (ans == INF) ans = -1; 228 cout << ans << endl; 229 230 return 0; 231 } 232 ``` 233 234 [1374E2 - Reading Books (hard version)](/contest/1374/problem/E2 "Codeforces Round 653 (Div. 3)") 235 236 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 237 238 **Tutorial** 239 240 Tutorial is loading... 241 242 **Solution** 243 244 ``` 245 #include <bits/stdc++.h> 246 247 using namespace std; 248 249 const int INF = 2e9 + 1; 250 251 #define size(a) int((a).size()) 252 253 void updateSt(set<pair<int, int>> &st, set<pair<int, int>> &fr, int &sum, int need) { 254 need = max(need, 0); 255 while (true) { 256 bool useful = false; 257 while (size(st) > need) { 258 sum -= st.rbegin()->first; 259 fr.insert(*st.rbegin()); 260 st.erase(prev(st.end())); 261 useful = true; 262 } 263 while (size(st) < need && size(fr) > 0) { 264 sum += fr.begin()->first; 265 st.insert(*fr.begin()); 266 fr.erase(fr.begin()); 267 useful = true; 268 } 269 while (!st.empty() && !fr.empty() && fr.begin()->first < st.rbegin()->first) { 270 sum -= st.rbegin()->first; 271 sum += fr.begin()->first; 272 fr.insert(*st.rbegin()); 273 st.erase(prev(st.end())); 274 st.insert(*fr.begin()); 275 fr.erase(fr.begin()); 276 useful = true; 277 } 278 if (!useful) break; 279 } 280 } 281 282 int main() { 283 #ifdef _DEBUG 284 freopen("input.txt", "r", stdin); 285 // freopen("output.txt", "w", stdout); 286 #endif 287 288 int n, m, k; 289 cin >> n >> m >> k; 290 vector<pair<int, int>> times[4]; 291 vector<int> sums[4]; 292 for (int i = 0; i < n; ++i) { 293 int t, a, b; 294 cin >> t >> a >> b; 295 times[a * 2 + b].push_back({t, i}); 296 } 297 for (int i = 0; i < 4; ++i) { 298 sort(times[i].begin(), times[i].end()); 299 sums[i].push_back(0); 300 for (auto it : times[i]) { 301 sums[i].push_back(sums[i].back() + it.first); 302 } 303 } 304 305 int ans = INF; 306 int pos = INF; 307 set<pair<int, int>> st; 308 set<pair<int, int>> fr; 309 int sum = 0; 310 vector<int> res; 311 for (int iter = 0; iter < 2; ++iter) { 312 st.clear(); 313 fr.clear(); 314 sum = 0; 315 int start = 0; 316 while (k - start >= size(sums[1]) || k - start >= size(sums[2]) || m - start - (k - start) * 2 < 0) { 317 ++start; 318 } 319 if (start >= size(sums[3])) { 320 cout << -1 << endl; 321 return 0; 322 } 323 int need = m - start - (k - start) * 2; 324 for (int i = 0; i < 3; ++i) { 325 for (int p = size(times[i]) - 1; p >= (i == 0 ? 0 : k - start); --p) { 326 fr.insert(times[i][p]); 327 } 328 } 329 updateSt(st, fr, sum, need); 330 for (int cnt = start; cnt < (iter == 0 ? size(sums[3]) : pos); ++cnt) { 331 if (k - cnt >= 0) { 332 if (cnt + (k - cnt) * 2 + size(st) == m) { 333 if (ans > sums[3][cnt] + sums[1][k - cnt] + sums[2][k - cnt] + sum) { 334 ans = sums[3][cnt] + sums[1][k - cnt] + sums[2][k - cnt] + sum; 335 pos = cnt + 1; 336 } 337 } 338 } else { 339 if (cnt + size(st) == m) { 340 if (ans > sums[3][cnt] + sum) { 341 ans = sums[3][cnt] + sum; 342 pos = cnt + 1; 343 } 344 } 345 } 346 if (iter == 1 && cnt + 1 == pos) break; 347 need -= 1; 348 if (k - cnt > 0) { 349 need += 2; 350 fr.insert(times[1][k - cnt - 1]); 351 fr.insert(times[2][k - cnt - 1]); 352 } 353 updateSt(st, fr, sum, need); 354 } 355 if (iter == 1) { 356 for (int i = 0; i + 1 < pos; ++i) res.push_back(times[3][i].second); 357 for (int i = 0; i <= k - pos; ++i) { 358 res.push_back(times[1][i].second); 359 res.push_back(times[2][i].second); 360 } 361 for (auto [value, position] : st) res.push_back(position); 362 } 363 } 364 365 cout << ans << endl; 366 for (auto it : res) cout << it + 1 << " "; 367 cout << endl; 368 369 return 0; 370 } 371 ``` 372 373 [1374F - Cyclic Shifts Sorting](/contest/1374/problem/F "Codeforces Round 653 (Div. 3)") 374 375 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 376 377 **Tutorial** 378 379 Tutorial is loading... 380 381 **Solution** 382 383 ``` 384 #include <bits/stdc++.h> 385 386 using namespace std; 387 388 int main() { 389 #ifdef _DEBUG 390 freopen("input.txt", "r", stdin); 391 // freopen("output.txt", "w", stdout); 392 #endif 393 394 auto make = [](vector<int> &a, int pos) { 395 swap(a[pos + 1], a[pos + 2]); 396 swap(a[pos], a[pos + 1]); 397 }; 398 399 int t; 400 cin >> t; 401 while (t--) { 402 int n; 403 cin >> n; 404 vector<int> a(n); 405 vector<pair<int, int>> res(n); 406 for (int i = 0; i < n; ++i) { 407 cin >> a[i]; 408 res[i] = { a[i], i }; 409 } 410 sort(res.begin(), res.end()); 411 for (int i = 0; i < n; ++i) { 412 a[res[i].second] = i; 413 } 414 int cnt = 0; 415 for (int i = 0; i < n; ++i) { 416 for (int j = i + 1; j < n; ++j) { 417 cnt += a[j] < a[i]; 418 } 419 } 420 if (cnt & 1) { 421 for (int i = 0; i < n - 1; ++i) { 422 if (res[i].first == res[i + 1].first) { 423 swap(a[res[i].second], a[res[i + 1].second]); 424 break; 425 } 426 } 427 } 428 vector<int> ans; 429 for (int i = 0; i < n - 2; ++i) { 430 int pos = min_element(a.begin() + i, a.end()) - a.begin(); 431 while (pos > i + 1) { 432 make(a, pos - 2); 433 ans.push_back(pos - 2); 434 pos -= 2; 435 } 436 if (pos != i) { 437 make(a, i); 438 make(a, i); 439 ans.push_back(i); 440 ans.push_back(i); 441 pos = i; 442 } 443 } 444 for (int i = 0; i < 3; ++i) { 445 if (is_sorted(a.begin(), a.end())) { 446 break; 447 } 448 make(a, n - 3); 449 ans.push_back(n - 3); 450 } 451 if (!is_sorted(a.begin(), a.end())) { 452 cout << -1 << endl; 453 } else { 454 cout << ans.size() << endl; 455 for (auto it : ans) cout << it + 1 << " "; 456 cout << endl; 457 } 458 } 459 460 return 0; 461 } 462 ```