codeforces-scrape

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

1221.md (9543B)


      1 Source: https://codeforces.com/blog/entry/69925
      2 
      3 [1221A - 2048 Game](/contest/1221/problem/A "Educational Codeforces Round 73 (Rated for Div. 2)")
      4 
      5 Idea: [Roms](/profile/Roms "Master Roms")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Roms)**
     12 
     13 ```
     14 for t in range(int(input())):
     15 	n = input()
     16 	l = filter(lambda x : x <= 2048,  map(int, input().split()) )
     17 	print('YES' if sum(l) >= 2048 else 'NO')
     18 ```
     19 
     20 [1221B - Knights](/contest/1221/problem/B "Educational Codeforces Round 73 (Rated for Div. 2)")
     21 
     22 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     23 
     24 **Tutorial**
     25 
     26 Tutorial is loading...
     27 
     28 **Solution (PikMike)**
     29 
     30 ```
     31 n = int(input())
     32 for i in range(n):
     33 	print(''.join(['W' if (i + j) % 2 == 0 else 'B' for j in range(n)]))
     34 ```
     35 
     36 [1221C - Perfect Team](/contest/1221/problem/C "Educational Codeforces Round 73 (Rated for Div. 2)")
     37 
     38 Idea: [Roms](/profile/Roms "Master Roms")
     39 
     40 **Tutorial**
     41 
     42 Tutorial is loading...
     43 
     44 **Solution 1 (BledDest)**
     45 
     46 ```
     47 t = int(input())
     48 for i in range(t):
     49 	c, m, x = map(int, input().split())
     50 	d = max(c, m) - min(c, m)
     51 	x += d
     52 	if(c > m):
     53 		c -= d
     54 	else:
     55 		m -= d
     56 	ans = min(c, m, x)
     57 	c -= ans
     58 	m -= ans
     59 	x -= ans
     60 	ans += (c + m) // 3
     61 	print(ans)
     62 ```
     63 
     64 **Solution 2 (PikMike)**
     65 
     66 ```
     67 #include <bits/stdc++.h>
     68 
     69 using namespace std;
     70 
     71 int main(){
     72 	int q;
     73 	cin >> q;
     74 	for (int i = 0; i < q; ++i){
     75 		int c, m, x;
     76 		cin >> c >> m >> x;
     77 		int l = 0, r = min(c, m);
     78 		int ans = 0;
     79 		while (l <= r){
     80 			int mid = (l + r) / 2;
     81 			if (c + m + x - 2 * mid >= mid){
     82 				l = mid + 1;
     83 				ans = mid;
     84 			}
     85 			else{
     86 				r = mid - 1;
     87 			}
     88 		}
     89 		cout << ans << "\n";
     90 	}
     91 }
     92 ```
     93 
     94 [1221D - Make The Fence Great Again](/contest/1221/problem/D "Educational Codeforces Round 73 (Rated for Div. 2)")
     95 
     96 Idea: [Roms](/profile/Roms "Master Roms")
     97 
     98 **Tutorial**
     99 
    100 Tutorial is loading...
    101 
    102 **Solution (Roms)**
    103 
    104 ```
    105 #include <bits/stdc++.h>
    106 
    107 using namespace std;
    108 
    109 const int N = int(3e5) + 99;
    110 const long long INF64 = (long long)(1e18) + 100;
    111 
    112 int t;
    113 int n;
    114 int a[N];
    115 int b[N];
    116 long long dp[3][N];
    117 
    118 long long calc(int add, int pos){
    119 	long long &res = dp[add][pos];
    120 	if(res != -1) return res;
    121 
    122 	res = INF64;
    123 	if(pos == n) return res = 0;
    124 	for(long long x = 0; x <= 2; ++x)
    125 		if(pos == 0 || a[pos] + x != a[pos - 1] + add)
    126 			res = min(res, calc(x, pos + 1) + x * b[pos]);
    127 		
    128 	return res;
    129 }
    130 
    131 int main() {	
    132 	scanf("%d", &t);
    133 	for(int tc = 0; tc < t; ++tc){
    134 		scanf("%d", &n);
    135 		for(int i = 0; i < n; ++i){
    136 			scanf("%d", a + i);
    137 			scanf("%d", b + i);
    138 		}
    139 
    140 		for(int i = 0; i <= n; ++i) 
    141 			dp[0][i] = dp[1][i] = dp[2][i] = -1;				
    142 		printf("%lld\n", calc(0, 0));
    143 	}
    144 	return 0;
    145 }
    146 ```
    147 
    148 [1221E - Game With String](/contest/1221/problem/E "Educational Codeforces Round 73 (Rated for Div. 2)")
    149 
    150 Idea: [Roms](/profile/Roms "Master Roms")
    151 
    152 **Tutorial**
    153 
    154 Tutorial is loading...
    155 
    156 **Solution (Roms)**
    157 
    158 ```
    159 #include <bits/stdc++.h>
    160 
    161 using namespace std;
    162 
    163 const int N = int(2e5) + 99;
    164 
    165 int t;
    166 int a, b;
    167 string s;
    168 
    169 int main() {
    170 	cin >> t;
    171 	for(int tc = 0; tc < t; ++tc){
    172 		cin >> a >> b >> s;
    173 		vector <int> v;
    174 		int l = 0;
    175 		while(l < s.size()){
    176 			if(s[l] == 'X'){
    177 				++l;
    178 				continue;
    179 			}
    180 
    181 			int r = l + 1;
    182 			while(r < s.size() && s[r] == '.') ++r;
    183 			v.push_back(r - l);
    184 			l = r;
    185 		}
    186 		
    187 		bool ok = true;
    188 		int id = -1;
    189 		int cnt = 0;
    190 		for(int i = 0; i < v.size(); ++i){
    191 			if(b <= v[i] && v[i] < a) ok = false;
    192 			if(b + b <= v[i]){
    193 				if(id == -1) id = i;
    194 				else ok = false;
    195 			}
    196 			if(a <= v[i] && v[i] < b + b) ++cnt; 
    197 		}
    198 
    199 		if(!ok){
    200 			cout << "NO" << endl;			
    201 			continue;
    202 		}
    203 
    204 		if(id == -1){
    205 			if(cnt & 1) cout << "YES" << endl;
    206 			else cout << "NO" << endl;
    207 			continue;
    208 		}
    209 
    210 		ok = false;
    211 		int sz = v[id];
    212 		assert(sz >= a);
    213 		for(int rem1 = 0; sz - a - rem1 >= 0; ++rem1){
    214 			int rem2 = sz - a - rem1;
    215 			int ncnt = cnt;
    216 			if((rem1 >= b + b) || (b <= rem1 && rem1 < a)) continue;
    217 			if((rem2 >= b + b) || (b <= rem2 && rem2 < a)) continue;
    218 
    219 			if(rem1 >= a) ++ncnt;
    220 			if(rem2 >= a) ++ncnt;
    221 			if(ncnt % 2 == 0) ok = true;
    222 		}
    223 		
    224 		if(ok) cout << "YES" << endl;
    225 		else cout << "NO" << endl;
    226 	}
    227 	return 0;
    228 }                             	
    229 ```
    230 
    231 [1221F - Choose a Square](/contest/1221/problem/F "Educational Codeforces Round 73 (Rated for Div. 2)")
    232 
    233 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    234 
    235 **Tutorial**
    236 
    237 Tutorial is loading...
    238 
    239 **Solution (Ne0n25)**
    240 
    241 ```
    242 #include <bits/stdc++.h>
    243 
    244 using namespace std;
    245 
    246 #define x first
    247 #define y second
    248 #define mp make_pair
    249 #define pb push_back
    250 #define all(a) (a).begin(), (a).end()
    251 #define sz(a) int((a).size())
    252 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    253 
    254 typedef long long li;
    255 typedef pair<int, int> pt;
    256 
    257 const int N = 1000 * 1000 + 13;
    258 
    259 int n;
    260 pair<pt, int> a[N];
    261 vector<int> vals;
    262 vector<pt> ev[N];
    263 pair<li, int> t[4 * N];
    264 li add[4 * N];
    265 
    266 void build(int v, int l, int r) {
    267 	if (l == r) {
    268 		t[v] = mp(-vals[l], l);
    269 		add[v] = 0;
    270 		return;
    271 	}
    272 	int m = (l + r) >> 1;
    273 	build(v * 2 + 1, l, m);
    274 	build(v * 2 + 2, m + 1, r);
    275 	t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
    276 }
    277 
    278 void push(int v, int l, int r) {
    279 	if (add[v] == 0) return;
    280 	t[v].x += add[v];
    281 	if (l != r) {
    282 		add[v * 2 + 1] += add[v];
    283 		add[v * 2 + 2] += add[v];
    284 	}
    285 	add[v] = 0;
    286 }
    287 
    288 void upd(int v, int l, int r, int L, int R, int val) {
    289 	push(v, l, r);
    290 	if (L > R) return;
    291 	if (l == L && r == R) {
    292 		add[v] += val;
    293 		push(v, l, r);
    294 		return;
    295 	}
    296 	int m = (l + r) >> 1;
    297 	upd(v * 2 + 1, l, m, L, min(m, R), val);
    298 	upd(v * 2 + 2, m + 1, r, max(m + 1, L), R, val);
    299 	t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
    300 }
    301 
    302 pair<li, int> get(int v, int l, int r, int L, int R) {
    303 	push(v, l, r);
    304 	if (L > R) return mp(-li(1e18), 0);
    305 	if (l == L && r == R) return t[v];
    306 	int m = (l + r) >> 1;
    307 	auto r1 = get(v * 2 + 1, l, m, L, min(m, R));
    308 	auto r2 = get(v * 2 + 2, m + 1, r, max(m + 1, L), R);
    309 	return max(r1, r2);
    310 }
    311 
    312 int main() {
    313 	scanf("%d", &n);
    314 	forn(i, n) scanf("%d%d%d", &a[i].x.x, &a[i].x.y, &a[i].y);
    315 	
    316 	forn(i, n) {
    317 		vals.pb(a[i].x.x);
    318 		vals.pb(a[i].x.y);
    319 	}
    320 	
    321 	vals.pb(0);
    322 	sort(all(vals));
    323 	vals.pb(vals.back() + 1);
    324 	
    325 	vals.resize(unique(all(vals)) - vals.begin());
    326 	
    327 	forn(i, n) {
    328 		int x = lower_bound(all(vals), a[i].x.x) - vals.begin();
    329 		int y = lower_bound(all(vals), a[i].x.y) - vals.begin();
    330 		ev[min(x, y)].pb(mp(max(x, y), a[i].y));
    331 	}
    332 	
    333 	n = sz(vals);
    334 	
    335 	build(0, 0, n - 1);
    336 	
    337 	li ans = -1;
    338 	int ansl = -1, ansr = -1;
    339 	
    340 	for (int i = sz(vals) - 1; i >= 0; i--) {
    341 		for (auto it : ev[i]) upd(0, 0, n - 1, it.x, n - 1, it.y);
    342 		auto cur = get(0, 0, n - 1, i, n - 1);
    343 		if (cur.x + vals[i] > ans) {
    344 			ans = cur.x + vals[i];
    345 			ansl = vals[i]; ansr = vals[cur.y]; 
    346 		}
    347 	}
    348 	
    349 	printf("%lld\n%d %d %d %d\n", ans, ansl, ansl, ansr, ansr);
    350 	
    351 }
    352 ```
    353 
    354 [1221G - Graph And Numbers](/contest/1221/problem/G "Educational Codeforces Round 73 (Rated for Div. 2)")
    355 
    356 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    357 
    358 **Tutorial**
    359 
    360 Tutorial is loading...
    361 
    362 **Solution (BledDest)**
    363 
    364 ```
    365 #include <bits/stdc++.h>
    366 
    367 using namespace std;
    368 
    369 const int N = 40;
    370 const int M = 20;
    371 
    372 long long incident_mask[N];
    373 vector<int> g[N];
    374 int n, m;
    375 long long ans = 0;
    376 long long cntmask[1 << M];
    377 
    378 long long binpow(long long x, long long y)
    379 {
    380 	long long z = 1;
    381 	while(y > 0)
    382 	{
    383 		if(y % 2 == 1) z *= x;
    384 		x *= x;
    385 		y /= 2;
    386 	}
    387 	return z;
    388 }
    389 
    390 int used[N];
    391 
    392 void dfs(int x, int c)
    393 {
    394 	if(used[x])
    395 		return;
    396 	used[x] = c;
    397 	for(auto y : g[x])
    398 		dfs(y, 3 - c);
    399 }
    400 
    401 long long countIsolated()
    402 {
    403 	long long ans = 0;
    404 	for(int i = 0; i < n; i++)
    405 		if(g[i].empty())
    406 			ans++;
    407 	return ans;
    408 }
    409 
    410 long long countComponents()
    411 {
    412 	memset(used, 0, sizeof used);
    413 	long long ans = 0;
    414 	for(int i = 0; i < n; i++)
    415 		if(!used[i])
    416 		{
    417 			ans++;
    418 			dfs(i, 1);
    419 		}
    420 	return ans;
    421 }
    422 
    423 bool bipartite()
    424 {
    425 	memset(used, 0, sizeof used);
    426 	for(int i = 0; i < n; i++)
    427 		if(!used[i])
    428 			dfs(i, 1);
    429 	for(int i = 0; i < n; i++)
    430 		for(auto j : g[i])
    431 			if(used[i] == used[j])
    432 				return false;
    433 	return true;
    434 }
    435 
    436 long long countIndependentSets()
    437 {
    438 	int m1 = min(n, 20);
    439 	int m2 = n - m1;
    440 	//cerr << m1 << " " << m2 << endl;
    441 	memset(cntmask, 0, sizeof cntmask);
    442 	for(int i = 0; i < (1 << m1); i++)
    443 	{
    444 		long long curmask = 0;
    445 		bool good = true;
    446 		for(int j = 0; j < m1; j++)
    447 		{
    448 			if((i & (1 << j)) == 0)
    449 				continue;
    450 			if(curmask & (1 << j))
    451 				good = false;
    452 			curmask |= ((1 << j) | incident_mask[j]);
    453 		}
    454 		if(good)
    455 		{
    456 			cntmask[curmask >> m1]++;
    457 		}
    458 	}	
    459 	for(int i = 0; i < m2; i++)
    460 		for(int j = 0; j < (1 << m2); j++)
    461 			if(j & (1 << i))
    462 				cntmask[j] += cntmask[j ^ (1 << i)];
    463 	long long ans = 0;
    464 	for(int i = 0; i < (1 << m2); i++)
    465 	{
    466 		long long curmask = 0;
    467 		bool good = true;
    468 		for(int j = m1; j < n; j++)
    469 		{
    470 			if((i & (1 << (j - m1))) == 0)
    471 				continue;
    472 			if(curmask & (1ll << j))
    473 				good = false;
    474 			curmask |= (1ll << j) | incident_mask[j];
    475 		}
    476 		if(good)
    477 		{
    478 			//cerr << i << endl;
    479 			ans += cntmask[(i ^ ((1 << m2) - 1))];
    480 		}
    481 	}
    482 	return ans;
    483 }
    484 
    485 long long calc(int mask)
    486 {
    487 	if(mask == 0)
    488 		return binpow(2, n);
    489 	if(mask == 1 || mask == 4)
    490 		return countIndependentSets();
    491 	if(mask == 2)
    492 		return binpow(2, countComponents());
    493 	if(mask == 3 || mask == 6)
    494 		return binpow(2, countIsolated());
    495 	if(mask == 5)
    496 		return (bipartite() ? binpow(2, countComponents()) : 0);
    497 	if(mask == 7)
    498 		return (m == 0 ? binpow(2, n) : 0);
    499 	return 0;
    500 }
    501 
    502 int main() {
    503 	cin >> n >> m;
    504 	for(int i = 0; i < m; i++)
    505 	{
    506 		int x, y;
    507 		cin >> x >> y;
    508 		--x;
    509 		--y;
    510 		g[x].push_back(y);
    511 		g[y].push_back(x);
    512 		incident_mask[x] ^= (1ll << y);
    513 		incident_mask[y] ^= (1ll << x);
    514 	}
    515 	for(int i = 0; i < 8; i++)
    516 	{
    517 		//cerr << i << " " << calc(i) << endl;
    518 		if(__builtin_popcount(i) % 2 == 0)
    519 			ans += calc(i);
    520 		else
    521 			ans -= calc(i);
    522 	}
    523 	cout << ans << endl;
    524     return 0;
    525 }
    526 ```