1845.md (8995B)
1 Source: https://codeforces.com/blog/entry/117791 2 3 [1845A - Forbidden Integer](/contest/1845/problem/A "Educational Codeforces Round 151 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (awoo)** 12 13 ``` 14 for _ in range(int(input())): 15 n, k, x = map(int, input().split()) 16 if x != 1: 17 print("YES") 18 print(n) 19 print(*([1] * n)) 20 elif k == 1 or (k == 2 and n % 2 == 1): 21 print("NO") 22 else: 23 print("YES") 24 print(n // 2) 25 print(*([3 if n % 2 == 1 else 2] + [2] * (n // 2 - 1))) 26 ``` 27 28 [1845B - Come Together](/contest/1845/problem/B "Educational Codeforces Round 151 (Rated for Div. 2)") 29 30 Idea: [adedalic](/profile/adedalic "International Master adedalic") 31 32 **Tutorial** 33 34 Tutorial is loading... 35 36 **Solution (adedalic)** 37 38 ``` 39 #include<bits/stdc++.h> 40 41 using namespace std; 42 43 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 44 #define sz(a) int((a).size()) 45 46 #define x first 47 #define y second 48 49 typedef long long li; 50 typedef pair<int, int> pt; 51 52 pt A, B, C; 53 54 inline bool read() { 55 if(!(cin >> A.x >> A.y)) 56 return false; 57 cin >> B.x >> B.y; 58 cin >> C.x >> C.y; 59 return true; 60 } 61 62 int dist(const pt &A, const pt &B) { 63 return abs(A.x - B.x) + abs(A.y - B.y); 64 } 65 66 inline void solve() { 67 cout << (dist(A, B) + dist(A, C) - dist(B, C)) / 2 + 1 << endl; 68 } 69 70 int main() { 71 #ifdef _DEBUG 72 freopen("input.txt", "r", stdin); 73 int tt = clock(); 74 #endif 75 ios_base::sync_with_stdio(false); 76 cin.tie(0), cout.tie(0); 77 cout << fixed << setprecision(15); 78 79 int t; cin >> t; 80 while (t--) { 81 read(); 82 solve(); 83 84 #ifdef _DEBUG 85 cerr << "TIME = " << clock() - tt << endl; 86 tt = clock(); 87 #endif 88 } 89 return 0; 90 } 91 ``` 92 93 [1845C - Strong Password](/contest/1845/problem/C "Educational Codeforces Round 151 (Rated for Div. 2)") 94 95 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 96 97 **Tutorial** 98 99 Tutorial is loading... 100 101 **Solution (awoo)** 102 103 ``` 104 import sys 105 for _ in range(int(sys.stdin.readline())): 106 s = [int(c) for c in sys.stdin.readline().strip()] 107 n = len(s) 108 m = int(sys.stdin.readline()) 109 l = sys.stdin.readline() 110 r = sys.stdin.readline() 111 mx = 0 112 for i in range(m): 113 li = int(l[i]) 114 ri = int(r[i]) 115 nmx = mx 116 for c in range(li, ri + 1): 117 cur = mx 118 while cur < n and s[cur] != c: 119 cur += 1 120 nmx = max(nmx, cur) 121 mx = nmx + 1 122 print("YES" if mx > n else "NO") 123 ``` 124 125 [1845D - Rating System](/contest/1845/problem/D "Educational Codeforces Round 151 (Rated for Div. 2)") 126 127 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 128 129 **Tutorial** 130 131 Tutorial is loading... 132 133 **Solution (Neon)** 134 135 ``` 136 #include <bits/stdc++.h> 137 138 using namespace std; 139 140 using li = long long; 141 142 int main() { 143 ios::sync_with_stdio(false); cin.tie(0); 144 int t; 145 cin >> t; 146 while (t--) { 147 int n; 148 cin >> n; 149 li delta = 0, ans = 0; 150 li sum = 0, mx = 0; 151 for (int i = 0; i < n; ++i) { 152 li x; cin >> x; 153 sum += x; 154 mx = max(mx, sum); 155 if (sum - mx < delta) { 156 delta = sum - mx; 157 ans = mx; 158 } 159 } 160 cout << ans << '\n'; 161 } 162 } 163 ``` 164 165 [1845E - Boxes and Balls](/contest/1845/problem/E "Educational Codeforces Round 151 (Rated for Div. 2)") 166 167 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 168 169 **Tutorial** 170 171 Tutorial is loading... 172 173 **Solution (awoo)** 174 175 ``` 176 #include <bits/stdc++.h> 177 178 #define forn(i, n) for (int i = 0; i < int(n); i++) 179 180 using namespace std; 181 182 const int MOD = int(1e9) + 7; 183 184 int add(int a, int b){ 185 a += b; 186 if (a >= MOD) 187 a -= MOD; 188 return a; 189 } 190 191 int main() { 192 int n, k; 193 scanf("%d%d", &n, &k); 194 vector<int> a(n); 195 forn(i, n) scanf("%d", &a[i]); 196 int lim = 1; 197 while (lim * (lim + 1) < k * 2) ++lim; 198 vector<vector<vector<int>>> dp(2, vector<vector<int>>(2 * lim + 1, vector<int>(k + 1))); 199 dp[0][lim][0] = 1; 200 forn(ii, n){ 201 int i = ii & 1; 202 int ni = i ^ 1; 203 dp[ni] = vector<vector<int>>(2 * lim + 1, vector<int>(k + 1)); 204 forn(j, 2 * lim + 1) forn(t, k + 1) if (dp[i][j][t]){ 205 forn(z, 2){ 206 int nj = j + z - a[ii]; 207 int nt = t + abs(nj - lim); 208 if (nt <= k) dp[ni][nj][nt] = add(dp[ni][nj][nt], dp[i][j][t]); 209 } 210 } 211 } 212 int ans = 0; 213 for (int t = k & 1; t <= k; t += 2) 214 ans = add(ans, dp[n & 1][lim][t]); 215 printf("%d\n", ans); 216 return 0; 217 } 218 ``` 219 220 [1845F - Swimmers in the Pool](/contest/1845/problem/F "Educational Codeforces Round 151 (Rated for Div. 2)") 221 222 Idea: [adedalic](/profile/adedalic "International Master adedalic") 223 224 **Tutorial** 225 226 Tutorial is loading... 227 228 **Solution (adedalic)** 229 230 ``` 231 #include<bits/stdc++.h> 232 233 using namespace std; 234 235 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 236 #define forn(i, n) for(int i = 0; i < int(n); i++) 237 #define sz(a) int((a).size()) 238 239 #define x first 240 #define y second 241 242 typedef long long li; 243 typedef pair<int, int> pt; 244 245 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 246 return out << "(" << p.x << ", " << p.y << ")"; 247 } 248 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 249 fore(i, 0, sz(v)) { 250 if(i) out << " "; 251 out << v[i]; 252 } 253 return out; 254 } 255 256 const int INF = int(1e9); 257 const li INF64 = li(1e18); 258 259 const int LOGN = 19; 260 const int N = (1 << LOGN) + 555; 261 262 struct comp { 263 double x, y; 264 comp(double x = .0, double y = .0) : x(x), y(y) {} 265 inline comp conj() { return comp(x, -y); } 266 }; 267 268 inline comp operator +(const comp &a, const comp &b) { 269 return comp(a.x + b.x, a.y + b.y); 270 } 271 272 inline comp operator -(const comp &a, const comp &b) { 273 return comp(a.x - b.x, a.y - b.y); 274 } 275 276 inline comp operator *(const comp &a, const comp &b) { 277 return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); 278 } 279 280 inline comp operator /(const comp &a, const double &b) { 281 return comp(a.x / b, a.y / b); 282 } 283 284 namespace FFT { 285 const double PI = acosl(-1.0); 286 vector<comp> w[LOGN]; 287 vector<int> rv; 288 289 void precalc() { 290 forn(st, LOGN) { 291 w[st].resize(1 << st); 292 forn(i, 1 << st) { 293 double ang = PI / (1 << st) * i; 294 w[st][i] = comp(cos(ang), sin(ang)); 295 } 296 } 297 rv.assign(1 << LOGN, 0); 298 fore(i, 1, sz(rv)) 299 rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (LOGN - 1)); 300 } 301 302 inline void fft(comp a[N], int n, bool inv) { 303 int ln = __builtin_ctz(n); 304 forn(i, n) { 305 int ni = rv[i] >> (LOGN - ln); 306 if(i < ni) swap(a[i], a[ni]); 307 } 308 309 for(int st = 0; st < ln; st++) { 310 int len = 1 << st; 311 for(int k = 0; k < n; k += (len << 1)) 312 fore(pos, k, k + len) { 313 comp l = a[pos]; 314 comp r = a[pos + len] * w[st][pos - k]; 315 316 a[pos] = l + r; 317 a[pos + len] = l - r; 318 } 319 } 320 321 if(inv) { 322 forn(i, n) 323 a[i] = a[i] / n; 324 reverse(a + 1, a + n); 325 } 326 } 327 328 comp aa[N], bb[N], cc[N]; 329 330 inline void multiply(int a[N], int sza, int b[N], int szb, int c[N], int &szc) { 331 int ln = 1; 332 while(ln < (sza + szb)) // sometimes works max(sza, szb) 333 ln <<= 1; 334 335 forn(i, ln) 336 aa[i] = (i < sza ? a[i] : comp()); 337 forn(i, ln) 338 bb[i] = (i < szb ? b[i] : comp()); 339 340 fft(aa, ln, false); 341 fft(bb, ln, false); 342 343 forn(i, ln) 344 cc[i] = aa[i] * bb[i]; 345 346 fft(cc, ln, true); 347 348 szc = ln; 349 forn(i, szc) 350 c[i] = int(cc[i].x + 0.5); 351 } 352 } 353 354 const int MOD = int(1e9) + 7; 355 int norm(int a) { 356 while (a >= MOD) 357 a -= MOD; 358 while (a < 0) 359 a += MOD; 360 return a; 361 } 362 int mul(int a, int b) { 363 return int(a * 1ll * b % MOD); 364 } 365 366 li l, t; 367 int n; 368 vector<int> v; 369 370 inline bool read() { 371 if(!(cin >> l >> t >> n)) 372 return false; 373 v.resize(n); 374 fore (i, 0, n) 375 cin >> v[i]; 376 return true; 377 } 378 379 int mu[N], minD[N]; 380 vector<int> divs[N]; 381 382 void precalcDivs(int N) { 383 fore (d, 1, N) { 384 for (int v = d; v < N; v += d) 385 divs[v].push_back(d); 386 } 387 388 mu[1] = 1; 389 fore (d, 2, N) { 390 if (minD[d] == 0) 391 minD[d] = d; 392 393 if (minD[d] != minD[d / minD[d]]) 394 mu[d] = -mu[d / minD[d]]; 395 396 for (int v = 2 * d; v < N; v += d) { 397 if (minD[v] == 0) 398 minD[v] = d; 399 } 400 } 401 } 402 403 int vs[2][N], res[N], ps[N]; 404 li mxk[N]; 405 406 inline void solve() { 407 FFT::precalc(); 408 409 fore (i, 0, n) { 410 vs[0][v[i]] = 1; 411 vs[1][v[i]] = 1; 412 } 413 int sz = 1 + *max_element(v.begin(), v.end()); 414 415 int szRes = 0; 416 FFT::multiply(vs[0], sz, vs[1], sz, res, szRes); 417 418 fore (i, 0, szRes) { 419 if (!(i & 1) && vs[0][i >> 1] > 0) 420 res[i]--; 421 if (res[i] > 0) { 422 ps[i] = 1; 423 } 424 } 425 426 memset(vs[1], 0, sizeof vs[1]); 427 fore (i, 0, n) 428 vs[1][sz - 1 - v[i]] = 1; 429 FFT::multiply(vs[0], sz, vs[1], sz, res, szRes); 430 431 fore (i, sz, szRes) { 432 if (res[i] > 0) { 433 ps[i - sz + 1] = 1; 434 } 435 } 436 437 precalcDivs(2 * sz); 438 439 int ans = 0; 440 for (int i = N - 1; i > 0; i--) { 441 if (ps[i] > 0) 442 mxk[i] = max(mxk[i], t * 1ll * i / (2ll * l)); 443 444 for (int d : divs[i]) { 445 // ans += mu[d] * (mxk[i] / d); 446 ans = norm(ans + mu[d] * int((mxk[i] / d) % MOD)); 447 mxk[i / d] = max(mxk[i / d], mxk[i] / d); 448 } 449 } 450 cout << ans << endl; 451 } 452 453 int main() { 454 #ifdef _DEBUG 455 freopen("input.txt", "r", stdin); 456 int tt = clock(); 457 #endif 458 ios_base::sync_with_stdio(false); 459 cin.tie(0), cout.tie(0); 460 cout << fixed << setprecision(15); 461 462 if(read()) { 463 solve(); 464 465 #ifdef _DEBUG 466 cerr << "TIME = " << clock() - tt << endl; 467 tt = clock(); 468 #endif 469 } 470 return 0; 471 } 472 ```