1886.md (9174B)
1 Source: https://codeforces.com/blog/entry/121255 2 3 [1886A - Sum of Three](/contest/1886/problem/A "Educational Codeforces Round 156 (Rated for Div. 2)") 4 5 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (fcspartakm)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int n; 19 20 inline void read() { 21 cin >> n; 22 } 23 24 inline void solve() { 25 for (int x = 1; x <= 20; x++) { 26 for (int y = 1; y <= 20; y++) { 27 if (x + y >= n || x == y) continue; 28 int z = n - x - y; 29 if (z == x || z == y) continue; 30 if (x % 3 == 0 || y % 3 == 0 || z % 3 == 0) { 31 continue; 32 } 33 puts("YES"); 34 cout << x << ' ' << y << ' ' << z << endl; 35 return; 36 } 37 } 38 puts("NO"); 39 } 40 41 int main () { 42 int t; 43 cin >> t; 44 while (t--){ 45 read(); 46 solve(); 47 } 48 } 49 ``` 50 51 [1886B - Fear of the Dark](/contest/1886/problem/B "Educational Codeforces Round 156 (Rated for Div. 2)") 52 53 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 54 55 **Tutorial** 56 57 Tutorial is loading... 58 59 **Solution (Neon)** 60 61 ``` 62 #include <bits/stdc++.h> 63 64 using namespace std; 65 66 int main() { 67 auto dist = [](int x1, int y1, int x2, int y2) { 68 return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); 69 }; 70 71 int t; 72 cin >> t; 73 while (t--) { 74 int px, py, ax, ay, bx, by; 75 cin >> px >> py >> ax >> ay >> bx >> by; 76 double pa = dist(px, py, ax, ay), pb = dist(px, py, bx, by); 77 double oa = dist(0, 0, ax, ay), ob = dist(0, 0, bx, by); 78 double ab = dist(ax, ay, bx, by); 79 double ans = 1e9; 80 ans = min(ans, max(pa, oa)); 81 ans = min(ans, max(pb, ob)); 82 ans = min(ans, max({ab / 2, pa, ob})); 83 ans = min(ans, max({ab / 2, pb, oa})); 84 cout << setprecision(10) << fixed << ans << '\n'; 85 } 86 } 87 ``` 88 89 [1886C - Decreasing String](/contest/1886/problem/C "Educational Codeforces Round 156 (Rated for Div. 2)") 90 91 Idea: [Roms](/profile/Roms "Master Roms") 92 93 **Tutorial** 94 95 Tutorial is loading... 96 97 **Solution (Roms)** 98 99 ``` 100 #include <bits/stdc++.h> 101 102 using namespace std; 103 104 const int N = 200000; 105 106 int t; 107 108 int main() { 109 cin >> t; 110 for (int tc = 0; tc < t; ++tc) { 111 string s; 112 long long pos; 113 cin >> s >> pos; 114 --pos; 115 116 int curLen = s.size(); 117 vector <char> st; 118 bool ok = pos < curLen; 119 s += '$'; 120 121 for (auto c : s) { 122 while (!ok && st.size() > 0 && st.back() > c) { 123 pos -= curLen; 124 --curLen; 125 st.pop_back(); 126 127 if(pos < curLen) 128 ok = true; 129 } 130 st.push_back(c); 131 } 132 133 cout << st[pos]; 134 } 135 return 0; 136 } 137 ``` 138 139 [1886D - Monocarp and the Set](/contest/1886/problem/D "Educational Codeforces Round 156 (Rated for Div. 2)") 140 141 Idea: [Roms](/profile/Roms "Master Roms") 142 143 **Tutorial** 144 145 Tutorial is loading... 146 147 **Solution (Roms)** 148 149 ``` 150 #include <bits/stdc++.h> 151 152 using namespace std; 153 154 const int MOD = 998244353; 155 156 const int N = 300009; 157 158 int bp(int a, int n) { 159 int res = 1; 160 while(n > 0) { 161 if (n & 1) 162 res = (res * 1LL * a) % MOD; 163 a = (a * 1LL * a) % MOD; 164 n >>= 1; 165 } 166 return res; 167 } 168 169 int n, m; 170 string s; 171 int inv[N]; 172 173 void upd(int &res, int x) { 174 res = (res * 1LL * x) % MOD; 175 } 176 177 int main() { 178 inv[1] = 1; 179 for (int i = 2; i < N; ++i){ 180 inv[i] = bp(i, MOD - 2); 181 } 182 183 cin >> n >> m >> s; 184 185 int res = 1, k = n; 186 bool isZero = false; 187 for (int i = 0; i < s.size(); ++i) 188 if (s[i] == '?') { 189 if (i == 0) { 190 isZero = true; 191 } else { 192 upd(res, i); 193 } 194 } 195 196 cout << (isZero? 0 : res) << endl; 197 198 for(int i = 0; i < m; ++i) { 199 int pos; 200 char c; 201 cin >> pos >> c; 202 --pos; 203 204 if (s[pos] == '?' && (c == '<' || c == '>')) { 205 if (pos == 0) 206 isZero = false; 207 else 208 upd(res, inv[pos]); 209 } else if ((s[pos] == '<' || s[pos] == '>') && c == '?') { 210 if (pos == 0) 211 isZero = true; 212 else 213 upd(res, pos); 214 } 215 216 s[pos] = c; 217 cout << (isZero? 0 : res) << endl; 218 } 219 return 0; 220 } 221 ``` 222 223 [1886E - I Wanna be the Team Leader](/contest/1886/problem/E "Educational Codeforces Round 156 (Rated for Div. 2)") 224 225 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 226 227 **Tutorial** 228 229 Tutorial is loading... 230 231 **Solution (awoo)** 232 233 ``` 234 #include <bits/stdc++.h> 235 236 #define forn(i, n) for (int i = 0; i < int(n); i++) 237 238 using namespace std; 239 240 int main() { 241 int n, m; 242 scanf("%d%d", &n, &m); 243 vector<int> a(n), b(m); 244 forn(i, n) scanf("%d", &a[i]); 245 forn(i, m) scanf("%d", &b[i]); 246 vector<int> ord(n); 247 iota(ord.begin(), ord.end(), 0); 248 sort(ord.begin(), ord.end(), [&a](int i, int j){ 249 return a[i] > a[j]; 250 }); 251 vector<vector<int>> mn(m, vector<int>(n + 2)); 252 forn(i, m){ 253 int r = 0; 254 forn(l, n + 2){ 255 r = min(n + 1, max(r, l + 1)); 256 while (r <= n && a[ord[r - 1]] * (r - l) < b[i]) ++r; 257 mn[i][l] = r; 258 } 259 } 260 vector<int> dp(1 << m, n + 1); 261 dp[0] = 0; 262 vector<int> p(1 << m, -1); 263 forn(mask, 1 << m) forn(i, m) if (!((mask >> i) & 1) && dp[mask | (1 << i)] > mn[i][dp[mask]]){ 264 dp[mask | (1 << i)] = mn[i][dp[mask]]; 265 p[mask | (1 << i)] = mask; 266 } 267 int mask = (1 << m) - 1; 268 if (dp[mask] > n){ 269 puts("NO"); 270 return 0; 271 } 272 puts("YES"); 273 vector<vector<int>> ans(n); 274 forn(_, m){ 275 int i = __builtin_ctz(mask ^ p[mask]); 276 for (int j = dp[p[mask]]; j < dp[mask]; ++j) 277 ans[i].push_back(ord[j]); 278 mask = p[mask]; 279 } 280 forn(i, m){ 281 printf("%d", int(ans[i].size())); 282 for (int x : ans[i]) printf(" %d", x + 1); 283 puts(""); 284 } 285 return 0; 286 } 287 ``` 288 289 [1886F - Diamond Theft](/contest/1886/problem/F "Educational Codeforces Round 156 (Rated for Div. 2)") 290 291 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 292 293 **Tutorial** 294 295 Tutorial is loading... 296 297 **Solution (Neon)** 298 299 ``` 300 #include <bits/stdc++.h> 301 302 using namespace std; 303 304 const int N = 3003; 305 306 int n; 307 int k[4]; 308 vector<int> a[4]; 309 310 struct segtree { 311 int sz; 312 int tot; 313 vector<int> t, p; 314 315 segtree(int sz) : sz(sz) { 316 tot = 0; 317 t = vector<int>(4 * sz); 318 p = vector<int>(4 * sz); 319 build(0, 0, sz); 320 } 321 322 void build(int v, int l, int r) { 323 if (l + 1 == r) { 324 t[v] = -l; 325 return; 326 } 327 int m = (l + r) / 2; 328 build(v * 2 + 1, l, m); 329 build(v * 2 + 2, m, r); 330 t[v] = max(t[v * 2 + 1], t[v * 2 + 2]); 331 } 332 333 void push(int v) { 334 if (p[v] == 0) return; 335 if (v + 1 < 2 * sz) { 336 t[v * 2 + 1] += p[v]; 337 p[v * 2 + 1] += p[v]; 338 t[v * 2 + 2] += p[v]; 339 p[v * 2 + 2] += p[v]; 340 p[v] = 0; 341 } 342 } 343 344 void upd(int v, int l, int r, int L, int R, int x) { 345 if (L >= R) return; 346 if (l == L && r == R) { 347 t[v] += x; 348 p[v] += x; 349 return; 350 } 351 push(v); 352 int m = (l + r) / 2; 353 upd(v * 2 + 1, l, m, L, min(m, R), x); 354 upd(v * 2 + 2, m, r, max(L, m), R, x); 355 t[v] = max(t[v * 2 + 1], t[v * 2 + 2]); 356 } 357 358 void upd(int pos, int x) { 359 tot += x; 360 upd(0, 0, sz, max(0, pos), sz, x); 361 } 362 363 int get(int v, int l, int r, int L, int R) { 364 if (L >= R) return -1e9; 365 if (l == L && r == R) return t[v]; 366 push(v); 367 int m = (l + r) / 2; 368 return max( 369 get(v * 2 + 1, l, m, L, min(m, R)), 370 get(v * 2 + 2, m, r, max(L, m), R) 371 ); 372 } 373 374 int get(int L) { 375 return get(0, 0, sz, max(0, L), sz); 376 } 377 378 int getBad(int v, int l, int r) { 379 if (t[v] <= 0) return -1; 380 if (l + 1 == r) return l; 381 push(v); 382 int m = (l + r) / 2; 383 if (t[v * 2 + 1] > 0) { 384 return getBad(v * 2 + 1, l, m); 385 } else { 386 return getBad(v * 2 + 2, m, r); 387 } 388 } 389 390 int getBad() { 391 return getBad(0, 0, sz); 392 } 393 }; 394 395 int main() { 396 cin >> n; 397 int sz = 1; 398 for (int i = 0; i < n; ++i) { 399 int t, s; 400 cin >> t >> s; 401 a[t].push_back(s); 402 sz = max(sz, s + 1); 403 } 404 for (int t = 1; t < 4; ++t) { 405 sort(a[t].begin(), a[t].end()); 406 k[t] = a[t].size(); 407 } 408 reverse(a[2].begin(), a[2].end()); 409 int ans = 1e4; 410 for (int len = 1; len <= k[2] + k[3] + 1; ++len) { 411 segtree L(sz), R(sz); 412 multiset<int> used; 413 for (int x : a[1]) L.upd(x, +1); 414 for (int x : a[2]) R.upd(x, +1); 415 for (int x : a[3]) { 416 L.upd(x - len, +1); 417 if (L.t[0] <= 0) { 418 used.insert(x - len); 419 } else { 420 L.upd(x - len, -1); 421 L.upd(x, +1); 422 R.upd(x, +1); 423 } 424 } 425 for (int i = 0; i <= k[2]; ++i) { 426 if (L.t[0] <= 0 && R.t[0] <= 0 && R.tot + 1 <= len) 427 ans = min(ans, n + (k[3] - (int)used.size()) + 2); 428 if (i == k[2]) break; 429 R.upd(a[2][i], -1); 430 L.upd(a[2][i] - len, +1); 431 int pos; 432 while ((pos = L.getBad()) != -1) { 433 auto it = used.upper_bound(pos); 434 if (it == used.begin()) break; 435 --it; 436 L.upd(*it, -1); 437 L.upd(*it + len, +1); 438 R.upd(*it + len, +1); 439 used.erase(it); 440 } 441 } 442 } 443 if (ans == 1e4) ans = -1; 444 cout << ans << '\n'; 445 } 446 ```