codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```