988.md (9082B)
1 Source: https://codeforces.com/blog/entry/59810 2 3 [988A - Diverse Team](/contest/988/problem/A "Codeforces Round 486 (Div. 3)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (Vovuh)** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 int main() { 17 #ifdef _DEBUG 18 freopen("input.txt", "r", stdin); 19 // freopen("output.txt", "w", stdout); 20 #endif 21 22 int n, k; 23 cin >> n >> k; 24 set<int> el; 25 vector<int> ans; 26 for (int i = 0; i < n; ++i) { 27 int x; 28 cin >> x; 29 if (!el.count(x)) { 30 ans.push_back(i); 31 el.insert(x); 32 } 33 } 34 35 if (int(ans.size()) < k) { 36 cout << "NO\n"; 37 } else { 38 cout << "YES\n"; 39 for (int i = 0; i < k; ++i) 40 cout << ans[i] + 1 << " "; 41 cout << endl; 42 } 43 44 return 0; 45 } 46 ``` 47 48 [988B - Substrings Sort](/contest/988/problem/B "Codeforces Round 486 (Div. 3)") 49 50 **Tutorial** 51 52 Tutorial is loading... 53 54 **Solution (Vovuh)** 55 56 ``` 57 #include <bits/stdc++.h> 58 59 using namespace std; 60 61 int main() { 62 #ifdef _DEBUG 63 freopen("input.txt", "r", stdin); 64 // freopen("output.txt", "w", stdout); 65 #endif 66 67 int n; 68 cin >> n; 69 vector<string> s(n); 70 for (int i = 0; i < n; ++i) 71 cin >> s[i]; 72 73 sort(s.begin(), s.end(), [&] (const string &s, const string &t) { 74 return s.size() < t.size(); 75 }); 76 77 for (int i = 0; i < n - 1; ++i) { 78 if (s[i + 1].find(s[i]) == string::npos) { 79 cout << "NO\n"; 80 return 0; 81 } 82 } 83 84 cout << "YES\n"; 85 for (auto it : s) 86 cout << it << endl; 87 88 return 0; 89 } 90 ``` 91 92 [988C - Equal Sums](/contest/988/problem/C "Codeforces Round 486 (Div. 3)") 93 94 **Tutorial** 95 96 Tutorial is loading... 97 98 **Solution (Vovuh)** 99 100 ``` 101 #include <bits/stdc++.h> 102 103 using namespace std; 104 105 int main() { 106 #ifdef _DEBUG 107 freopen("input.txt", "r", stdin); 108 // freopen("output.txt", "w", stdout); 109 #endif 110 111 int k; 112 cin >> k; 113 vector<pair<int, pair<int, int>>> a; 114 for (int i = 0; i < k; ++i) { 115 int n; 116 cin >> n; 117 vector<int> x(n); 118 for (int j = 0; j < n; ++j) 119 cin >> x[j]; 120 int sum = accumulate(x.begin(), x.end(), 0); 121 for (int j = 0; j < n; ++j) 122 a.push_back(make_pair(sum - x[j], make_pair(i, j))); 123 } 124 125 stable_sort(a.begin(), a.end()); 126 for (int i = 0; i < int(a.size()) - 1; ++i) { 127 if (a[i].first == a[i + 1].first && (a[i].second.first != a[i + 1].second.first)) { 128 cout << "YES" << endl; 129 cout << a[i + 1].second.first + 1 << " " << a[i + 1].second.second + 1 << endl; 130 cout << a[i].second.first + 1 << " " << a[i].second.second + 1 << endl; 131 return 0; 132 } 133 } 134 135 cout << "NO\n"; 136 137 return 0; 138 } 139 ``` 140 141 [988D - Points and Powers of Two](/contest/988/problem/D "Codeforces Round 486 (Div. 3)") 142 143 **Tutorial** 144 145 Tutorial is loading... 146 147 **Solution (Vovuh)** 148 149 ``` 150 #include <bits/stdc++.h> 151 152 using namespace std; 153 154 int main() { 155 #ifdef _DEBUG 156 freopen("input.txt", "r", stdin); 157 // freopen("output.txt", "w", stdout); 158 #endif 159 160 int n; 161 cin >> n; 162 vector<int> x(n); 163 for (int i = 0; i < n; ++i) { 164 cin >> x[i]; 165 } 166 167 sort(x.begin(), x.end()); 168 vector<int> res = { x[0] }; 169 170 for (int i = 0; i < n; ++i) { 171 for (int j = 0; j < 31; ++j) { 172 int lx = x[i] - (1 << j); 173 int rx = x[i] + (1 << j); 174 bool isl = binary_search(x.begin(), x.end(), lx); 175 bool isr = binary_search(x.begin(), x.end(), rx); 176 if (isl && isr && int(res.size()) < 3) { 177 res = { lx, x[i], rx }; 178 } 179 if (isl && int(res.size()) < 2) { 180 res = { lx, x[i] }; 181 } 182 if (isr && int(res.size()) < 2) { 183 res = { x[i], rx }; 184 } 185 } 186 } 187 188 cout << int(res.size()) << endl; 189 for (auto it : res) 190 cout << it << " "; 191 cout << endl; 192 193 return 0; 194 } 195 ``` 196 197 [988E - Divisibility by 25](/contest/988/problem/E "Codeforces Round 486 (Div. 3)") 198 199 **Tutorial** 200 201 Tutorial is loading... 202 203 **Solution (Vovuh)** 204 205 ``` 206 #include <bits/stdc++.h> 207 208 using namespace std; 209 210 const int INF = 1000 * 1000 * 1000; 211 212 int main() { 213 #ifdef _DEBUG 214 freopen("input.txt", "r", stdin); 215 // freopen("output.txt", "w", stdout); 216 #endif 217 218 long long n; 219 cin >> n; 220 221 string s = to_string(n); 222 223 int ans = INF; 224 225 int len = s.size(); 226 for (int i = 0; i < len; ++i) { 227 for (int j = 0; j < len; ++j) { 228 if (i == j) continue; 229 string t = s; 230 int cur = 0; 231 for (int k = i; k < len - 1; ++k) { 232 swap(t[k], t[k + 1]); 233 ++cur; 234 } 235 236 for (int k = j - (j > i); k < len - 2; ++k) { 237 swap(t[k], t[k + 1]); 238 ++cur; 239 } 240 241 int pos = -1; 242 for (int k = 0; k < len; ++k) { 243 if (t[k] != '0') { 244 pos = k; 245 break; 246 } 247 } 248 249 for (int k = pos; k > 0; --k) { 250 swap(t[k], t[k - 1]); 251 ++cur; 252 } 253 254 long long nn = atoll(t.c_str()); 255 if (nn % 25 == 0) 256 ans = min(ans, cur); 257 } 258 } 259 260 if (ans == INF) 261 ans = -1; 262 263 cout << ans << endl; 264 265 return 0; 266 } 267 ``` 268 269 [988F - Rain and Umbrellas](/contest/988/problem/F "Codeforces Round 486 (Div. 3)") 270 271 **Tutorial** 272 273 Tutorial is loading... 274 275 **Solution (Vovuh)** 276 277 ``` 278 #include <bits/stdc++.h> 279 280 using namespace std; 281 282 const int INF = 1000 * 1000 * 1000; 283 284 int main() { 285 #ifdef _DEBUG 286 freopen("input.txt", "r", stdin); 287 // freopen("output.txt", "w", stdout); 288 #endif 289 290 int a, n, m; 291 cin >> a >> n >> m; 292 vector<int> rain(a + 1); 293 vector<pair<int, int>> umb(a + 1, make_pair(INF, -1)); 294 vector<int> costs(m); 295 296 for (int i = 0; i < n; ++i) { 297 int l, r; 298 cin >> l >> r; 299 for (int j = l; j < r; ++j) 300 rain[j] = 1; 301 } 302 303 for (int i = 0; i < m; ++i) { 304 int x, p; 305 cin >> x >> p; 306 costs[i] = p; 307 umb[x] = min(umb[x], make_pair(p, i)); 308 } 309 310 vector<vector<int>> dp(a + 1, vector<int>(m + 1, INF)); 311 dp[0][m] = 0; 312 for (int i = 0; i < a; ++i) { 313 for (int j = 0; j <= m; ++j) { 314 if (dp[i][j] == INF) 315 continue; 316 if (rain[i] == 0) 317 dp[i + 1][m] = min(dp[i + 1][m], dp[i][j]); 318 if (j < m) 319 dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + costs[j]); 320 if (umb[i].first != INF) 321 dp[i + 1][umb[i].second] = min(dp[i + 1][umb[i].second], dp[i][j] + umb[i].first); 322 } 323 } 324 325 int ans = INF; 326 for (int i = 0; i <= m; ++i) 327 ans = min(ans, dp[a][i]); 328 if (ans == INF) 329 ans = -1; 330 cout << ans << endl; 331 332 return 0; 333 } 334 ``` 335 336 **Solution (step_by_step)** 337 338 ``` 339 //#pragma comment(linker, "/stack:200000000") 340 //#pragma GCC optimize("Ofast") 341 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 342 //#pragma GCC optimize("unroll-loops") 343 344 #include <stdio.h> 345 #include <bits/stdc++.h> 346 347 #define uint unsigned int 348 #define ll long long 349 #define ull unsigned long long 350 #define ld long double 351 #define rep(i, l, r) for (int i = l; i < r; i++) 352 #define repb(i, r, l) for (int i = r; i > l; i--) 353 #define sz(a) (int)a.size() 354 #define fi first 355 #define se second 356 #define mp(a, b) make_pair(a, b) 357 358 using namespace std; 359 360 inline void setmin(int &x, int y) { if (y < x) x = y; } 361 inline void setmax(int &x, int y) { if (y > x) x = y; } 362 inline void setmin(ll &x, ll y) { if (y < x) x = y; } 363 inline void setmax(ll &x, ll y) { if (y > x) x = y; } 364 365 const int N = 2001; 366 const int inf = (int)1e9 + 1; 367 const ll big = (ll)1e18 + 1; 368 const int P = 239; 369 const int MOD = (int)1e9 + 7; 370 const int MOD1 = (int)1e9 + 9; 371 const double eps = 1e-9; 372 const double pi = atan2(0, -1); 373 const int ABC = 26; 374 375 struct Line 376 { 377 ll k, b; 378 Line() {} 379 Line(ll k, ll b) : k(k), b(b) {} 380 ll val(ll x) { return k * x + b; } 381 }; 382 383 int cnt_v; 384 Line tree[N * 4]; 385 386 void build(int n) 387 { 388 cnt_v = 1; 389 while (cnt_v < n) 390 cnt_v <<= 1; 391 rep(i, 0, cnt_v * 2 - 1) 392 tree[i] = Line(0, inf); 393 } 394 395 void upd(int x, int lx, int rx, int l, int r, Line line) 396 { 397 if (lx >= r || l >= rx) 398 return; 399 else if (lx >= l && rx <= r) 400 { 401 int m = (lx + rx) / 2; 402 if (line.val(m) < tree[x].val(m)) 403 swap(tree[x], line); 404 if (rx - lx == 1) 405 return; 406 if (line.val(lx) < tree[x].val(lx)) 407 upd(x * 2 + 1, lx, (lx + rx) / 2, l, r, line); 408 else 409 upd(x * 2 + 2, (lx + rx) / 2, rx, l, r, line); 410 } 411 else 412 { 413 upd(x * 2 + 1, lx, (lx + rx) / 2, l, r, line); 414 upd(x * 2 + 2, (lx + rx) / 2, rx, l, r, line); 415 } 416 } 417 418 ll get(ll p) 419 { 420 int x = p + cnt_v - 1; 421 ll res = tree[x].val(p); 422 while (x > 0) 423 { 424 x = (x - 1) / 2; 425 setmin(res, tree[x].val(p)); 426 } 427 return res; 428 } 429 430 int add[N]; 431 int best[N]; 432 433 ll dp[N]; 434 435 int main() 436 { 437 //freopen("a.in", "r", stdin); 438 //freopen("a.out", "w", stdout); 439 ios_base::sync_with_stdio(0); 440 cin.tie(0); 441 cout.precision(20); 442 cout << fixed; 443 //ll TL = 0.95 * CLOCKS_PER_SEC; 444 //clock_t time = clock(); 445 int L, n, m; 446 cin >> L >> n >> m; 447 448 rep(i, 0, n) 449 { 450 int l, r; 451 cin >> l >> r; 452 add[l]++; 453 add[r]--; 454 } 455 rep(i, 1, L + 1) 456 add[i] += add[i - 1]; 457 458 fill(best, best + L + 1, inf); 459 rep(i, 0, m) 460 { 461 int x, p; 462 cin >> x >> p; 463 setmin(best[x], p); 464 } 465 466 // dp[i] + best[i] * (j - i) = best[i] * j + (dp[i] - best[i] * i) 467 build(L + 1); 468 fill(dp, dp + L + 1, inf); 469 dp[0] = 0; 470 upd(0, 0, cnt_v, 0 + 1, cnt_v, Line(best[0], dp[0] - best[0] * 0)); 471 rep(i, 1, L + 1) 472 { 473 dp[i] = get(i); 474 if (add[i - 1] == 0) 475 setmin(dp[i], dp[i - 1]); 476 upd(0, 0, cnt_v, i + 1, cnt_v, Line(best[i], dp[i] - best[i] * i)); 477 } 478 cout << (dp[L] != inf ? dp[L] : -1) << "\n"; 479 return 0; 480 } 481 ```