codeforces-scrape

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

1051.md (11634B)


      1 Source: https://codeforces.com/blog/entry/61969
      2 
      3 [1051A - Vasya And Password](/contest/1051/problem/A "Educational Codeforces Round 51 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (Ajosteen)**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 string s;
     17 
     18 bool ok(string t){
     19     int msk = 0;
     20     
     21     for(int i = 0; i < int(t.size()); ++i){
     22 	    if(isupper(t[i])) msk |= 1;
     23 	    if(islower(t[i])) msk |= 2;
     24 	    if(isdigit(t[i])) msk |= 4;
     25 	}
     26 	
     27 	return msk == 7;
     28 }
     29 
     30 int main() {
     31 	//freopen("input.txt", "r", stdin);
     32 	int t;
     33 	cin >> t;
     34 	for(int i = 0; i < t; ++i){
     35     	cin >> s;
     36     	if(ok(s)){
     37     	    cout << s << endl;
     38     	    continue;
     39     	}
     40     	bool fnd = false;
     41         for(int i = 0; i < int(s.size()); ++i){
     42             string t = s;
     43             
     44             t[i] = '1';
     45             if(ok(t)){
     46     	        cout << t << endl;
     47     	        fnd = true;
     48     	        break;
     49     	    }
     50             t[i] = 'a';
     51             if(ok(t)){
     52     	        cout << t << endl;
     53     	        fnd = true;
     54     	        break;
     55     	    }
     56     	    t[i] = 'A';
     57             if(ok(t)){
     58     	        cout << t << endl;
     59     	        fnd = true;
     60     	        break;
     61     	    }
     62         }
     63     	
     64     	if(fnd) continue;
     65     	
     66     	if(isupper(s[2])){
     67     	    s[0] = 'a';
     68     	    s[1] = '1';
     69     	    cout << s << endl;
     70     	    continue;
     71     	}
     72     	if(islower(s[2])){
     73     	    s[0] = 'A';
     74     	    s[1] = '1';
     75     	    cout << s << endl;
     76     	    continue;
     77     	}
     78     	if(isdigit(s[2])){
     79     	    s[0] = 'a';
     80     	    s[1] = 'A';
     81     	    cout << s << endl;
     82     	    continue;
     83     	}
     84 	}
     85 	return  0;
     86 }
     87 ```
     88 
     89 [1051B - Relatively Prime Pairs](/contest/1051/problem/B "Educational Codeforces Round 51 (Rated for Div. 2)")
     90 
     91 **Tutorial**
     92 
     93 Tutorial is loading...
     94 
     95 **Solution (PikMike)**
     96 
     97 ```
     98 #include <bits/stdc++.h>
     99 
    100 using namespace std;
    101 
    102 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    103 
    104 int main() {
    105 	long long l, r;
    106 	scanf("%lld%lld", &l, &r);
    107 	puts("YES");
    108 	forn(i, (r - l) / 2 + 1)
    109 		printf("%lld %lld\n", l + i * 2, l + i * 2 + 1);
    110 }
    111 ```
    112 
    113 [1051C - Vasya and Multisets](/contest/1051/problem/C "Educational Codeforces Round 51 (Rated for Div. 2)")
    114 
    115 **Tutorial**
    116 
    117 Tutorial is loading...
    118 
    119 **Solution (Ajosteen)**
    120 
    121 ```
    122 #include <bits/stdc++.h>
    123 
    124 using namespace std;
    125 
    126 const int N = 109;
    127 
    128 int n;
    129 int a[N];
    130 map<int, int> m;
    131 set <int> s[2];
    132 
    133 int main() {
    134 	int n;
    135 	cin >> n;
    136 	for(int i = 0; i < n; ++i){
    137 		cin >> a[i];
    138 		m[a[i]]++;
    139 	}
    140 
    141 	int pos = 0;
    142 	for(auto p : m)
    143 		if(p.second == 1){
    144 			s[pos].insert(p.first);
    145 			pos = 1 - pos;
    146 		}
    147 		
    148 	if(s[0].size() == s[1].size()){
    149 		string res(n, 'A');
    150 		for(int i = 0; i < n; ++i)
    151 			if(s[1].count(a[i]))
    152 				res[i] = 'B';
    153 		
    154 		cout << "YES" << endl;
    155 		for(auto c : res) cout << c;
    156 		cout << endl;
    157 		return 0;
    158 	}
    159 	else{
    160 		assert(int(s[0].size()) - 1 == int(s[1].size()));
    161 		string res(n, 'A');
    162 		for(int i = 0; i < n; ++i)
    163 			if(s[1].count(a[i]))
    164 				res[i] = 'B';
    165 		
    166 		int id = -1;
    167 		for(auto p : m)
    168 			if(p.second >= 3){
    169 				id = p.first;
    170 				break;
    171 			}
    172 			
    173 		if(id == -1){
    174 			cout << "NO" << endl;
    175 			return 0;
    176 		}
    177 		
    178 		bool flag = false;
    179 		for(int i = 0; i < n; ++i){
    180 			if(a[i] == id)
    181 				if(!flag){
    182 					flag = true;
    183 					res[i] = 'B';
    184 				}
    185 		}
    186 		
    187 		cout << "YES" << endl;
    188 		for(auto c : res) cout << c;
    189 		cout << endl;
    190 		return 0;
    191 	}
    192 	return 0;
    193 }
    194                              	
    195 ```
    196 
    197 [1051D - Bicolorings](/contest/1051/problem/D "Educational Codeforces Round 51 (Rated for Div. 2)")
    198 
    199 **Tutorial**
    200 
    201 Tutorial is loading...
    202 
    203 **Solution (PikMike)**
    204 
    205 ```
    206 #include <bits/stdc++.h>
    207 
    208 using namespace std;
    209 
    210 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    211 
    212 const int N = 1000 + 7;
    213 const int MOD = 998244353;
    214 
    215 int dp[N][2 * N][4];
    216 
    217 int add(int a, int b){
    218 	return (a + b) % MOD;
    219 }
    220 
    221 bool full(int mask){
    222 	return (mask == 0 || mask == 3);
    223 }
    224 
    225 int get(int mask, int nmask){
    226 	int cnt = __builtin_popcount(mask ^ nmask);
    227 	if (cnt == 0) return 0;
    228 	if (cnt == 2) return (full(mask) ? 1 : 2);
    229 	return (full(mask) ? 0 : 1);
    230 }
    231 
    232 int main() {
    233 	int n, k;
    234 	scanf("%d%d", &n, &k);
    235 	forn(i, 4)
    236 		dp[1][0][i] = 1;
    237 	
    238 	for (int i = 1; i < n; ++i){
    239 		forn(j, k + 1){
    240 			forn(mask, 4){
    241 				forn(nmask, 4){
    242 					dp[i + 1][j + get(mask, nmask)][nmask] = add(dp[i + 1][j + get(mask, nmask)][nmask], dp[i][j][mask]);
    243 				}
    244 			}
    245 		}
    246 	}
    247 	
    248 	int ans = 0;
    249 	forn(mask, 4){
    250 		int nw = get(mask, mask ^ 3);
    251 		if (k >= nw)
    252 			ans = add(ans, dp[n][k - nw][mask]);
    253 	}
    254 	
    255 	printf("%d\n", ans);
    256 }        	
    257 ```
    258 
    259 [1051E - Vasya and Big Integers](/contest/1051/problem/E "Educational Codeforces Round 51 (Rated for Div. 2)")
    260 
    261 **Tutorial**
    262 
    263 Tutorial is loading...
    264 
    265 **Solution (Ajosteen)**
    266 
    267 ```
    268 #include<bits/stdc++.h>
    269 
    270 using namespace std;
    271 
    272 #define sz(a) (int)(a.size())
    273 
    274 const int N = int(1e6) + 9;
    275 const int MOD = 998244353;
    276 
    277 int n;
    278 string s, l, r;
    279 int dp[N];
    280 int sumDP[N];
    281 
    282 int sum(int a, int b){
    283 	a += b;
    284 	if(a >= MOD) a -= MOD;
    285 	return a;
    286 }
    287 
    288 vector <int> z_function(string s){
    289 	int n = sz(s);
    290 	vector <int> z(n);
    291 	for(int i = 1, l = 0, r = 0; i < n; ++i){
    292 		if(i <= r)
    293 			z[i] = min(r - i + 1, z[i - l]);
    294 		while(i + z[i] < n && s[z[i]] == s[i + z[i]])
    295 			++z[i];
    296 		if(i + z[i] - 1 > r)
    297 			l = i,  r = i + z[i] - 1;
    298 	}
    299 	return z;
    300 }
    301 
    302 //s[pos..] ? t
    303 char cmp(vector <int> &zf, string &t, int pos){
    304 	int len = sz(t);
    305 	assert(pos + len + 1 < sz(zf));
    306 	if(sz(s) - pos < len) return '<';
    307 	
    308 	int x = zf[len + 1 + pos];
    309 	assert(x <= len);
    310 	if(x == len) return '=';
    311 	assert(pos + x < sz(s));
    312 	assert(s[pos + x] != t[x]);
    313 	if(s[pos + x] < t[x]) return '<';
    314 	return '>';
    315 }
    316 
    317 int main() {
    318 	//freopen("input.txt", "r", stdin);
    319 	
    320 	ios_base::sync_with_stdio(false);
    321     cin.tie(NULL);
    322     
    323 	cin >> s >> l >> r;
    324 	n = int(s.size());
    325 	vector <int> zl = z_function(l + "#" + s);
    326 	vector <int> zr = z_function(r + "#" + s);
    327 	
    328 	sumDP[n] = dp[n] = 1;
    329 	for(int i = n - 1; i >= 0; --i){
    330 		if(s[i] == '0'){
    331 			if(l == "0") dp[i] = dp[i + 1];		
    332 			else dp[i] = 0;
    333 			sumDP[i] = sum(dp[i], sumDP[i + 1]);
    334 			continue;
    335 		}
    336 		
    337 		int L = sz(l) + i;
    338 		char cl = cmp(zl, l, i);
    339 		if(cl == '<') ++L;
    340 		
    341 		int R = sz(r) + i;
    342 		char cr = cmp(zr, r, i);
    343 		if(cr == '>') --R;
    344 
    345 	 	int cur = 0;
    346 	 	if(L <= R && L <= n){
    347 	 		R = min(R, n);
    348 	 		cur = sumDP[L];
    349 	 		if(R != n) cur = sum(cur, MOD - sumDP[R + 1]);
    350 	 	}
    351 	 	dp[i] = cur;
    352 	 	sumDP[i] = sum(dp[i], sumDP[i + 1]);
    353 	}
    354 	
    355 	cout << dp[0] << endl;
    356 	return 0;
    357 }
    358 ```
    359 
    360 [1051F - The Shortest Statement](/contest/1051/problem/F "Educational Codeforces Round 51 (Rated for Div. 2)")
    361 
    362 **Tutorial**
    363 
    364 Tutorial is loading...
    365 
    366 **Solution (Ajosteen)**
    367 
    368 ```
    369 #include <bits/stdc++.h>
    370 
    371 using namespace std;
    372 
    373 const int N = 300 * 1000 + 9;
    374 const int LOGN = 19;
    375 const int M = 21;
    376 const long long INF64 = 1e18;
    377 
    378 int n, m, q;
    379 vector <pair<int, int> > g[N];
    380 int p[LOGN][N];
    381 int tin[N], tout[N], T;
    382 long long h[N];
    383 set <pair<int, int> > badEdges;
    384 long long d[M + M][N];
    385 bool u[N];
    386 
    387 void dfs(int v, int pr){
    388 	tin[v] = T++;
    389 	p[0][v] = pr;
    390 	u[v] = true;
    391 	for(int i = 1; i < LOGN; ++i)
    392 		p[i][v] = p[i - 1][ p[i - 1][v] ];
    393 		
    394 	for(auto e : g[v]){
    395 		int to = e.first, len = e.second;
    396 		if(!u[to]){
    397 			h[to] = h[v] + len;
    398 			dfs(to, v);
    399 			
    400 			if(v < to)
    401 				badEdges.erase(make_pair(v, to));
    402 			else
    403 				badEdges.erase(make_pair(to, v));			
    404 		}
    405 	}	
    406 		
    407 	tout[v] = T;
    408 }
    409 
    410 bool isAncestor(int a, int b){
    411 	return tin[a] <= tin[b] && tout[a] >= tout[b];
    412 }
    413 
    414 int getLCA(int a, int b){
    415 	if(isAncestor(a, b)) return a;
    416 	if(isAncestor(b, a)) return b;
    417 	
    418 	for(int i = LOGN - 1; i >= 0; --i)
    419 		if(!isAncestor(p[i][a], b))
    420 			a = p[i][a];
    421 	
    422 	return p[0][a];
    423 }
    424 
    425 void dij(int st, long long d[N]){
    426 	set<pair<long long, int> > q;
    427 	for(int i = 0; i < n; ++i) d[i] = INF64;
    428 	d[st] = 0;
    429 	q.insert(make_pair(d[st], st));
    430 	
    431 	while(!q.empty()){
    432 		int v = q.begin()->second;
    433 		q.erase(q.begin());
    434 		
    435 		for(auto e : g[v]){
    436 			int to = e.first, len = e.second;
    437 			if(d[to] > d[v] + len){
    438 				q.erase(make_pair(d[to], to));
    439 				d[to] = d[v] + len;
    440 				q.insert(make_pair(d[to], to));
    441 			}
    442 		}
    443 	}
    444 }
    445 
    446 int main() {
    447 	//freopen("input.txt", "r", stdin);
    448 	
    449 	scanf("%d %d", &n, &m);
    450     for(int i = 0; i < m; ++i){
    451     	int u, v, w;
    452     	scanf("%d %d %d", &u, &v, &w);
    453     	--u, --v;
    454     	g[u].push_back(make_pair(v, w));
    455        	g[v].push_back(make_pair(u, w));
    456     }
    457 	
    458     for(int v = 0; v < n; ++v)
    459     	for(auto e : g[v])
    460     		if(v < e.first)
    461     			badEdges.insert(make_pair(v, e.first));
    462 
    463     dfs(0, 0);
    464 
    465     int cpos = 0;
    466     for(auto e : badEdges)
    467     	dij(e.first, d[cpos++]);
    468     scanf("%d", &q);
    469     for(int tc = 0; tc < q; ++tc){
    470     	int u, v;
    471     	scanf("%d %d", &u, &v);
    472     	--u, --v;
    473     	int lca = getLCA(u, v);
    474     	long long ans = h[u] + h[v] - 2 * h[lca];
    475     	for(int i = 0; i < badEdges.size(); ++i)
    476     		ans = min(ans, d[i][u] + d[i][v]);
    477     		
    478     	printf("%lld\n", ans);
    479     }	
    480     return 0;
    481 }
    482 ```
    483 
    484 [1051G - Distinctification](/contest/1051/problem/G "Educational Codeforces Round 51 (Rated for Div. 2)")
    485 
    486 **Tutorial**
    487 
    488 Tutorial is loading...
    489 
    490 **Solution (BledDest)**
    491 
    492 ```
    493 #include <bits/stdc++.h>
    494 
    495 using namespace std;
    496 
    497 #define x first
    498 #define y second
    499 
    500 typedef long long li;
    501 
    502 mt19937 rnd(time(NULL));
    503 
    504 struct node
    505 {
    506 	int x;
    507 	int y;
    508 	li sum;
    509 	int siz;
    510 	node* l;
    511 	node* r;
    512 	node() {};
    513 	node(int x, int y, li sum, int siz, node* l, node* r) : x(x), y(y), sum(sum), siz(siz), l(l), r(r) {};
    514 };
    515 
    516 typedef node* treap;
    517 typedef pair<treap, treap> ptt;
    518 
    519 int getSiz(treap t)
    520 {
    521 	return (t ? t->siz : 0);
    522 }
    523 
    524 li getSum(treap t)
    525 {
    526 	return (t ? t->sum : 0);
    527 }
    528 
    529 treap fix(treap t)
    530 {
    531 	if(!t) return t;
    532 	t->sum = getSum(t->l) + t->x + getSum(t->r);
    533 	t->siz = getSiz(t->l) + 1 + getSiz(t->r);
    534 	return t;
    535 }
    536 
    537 ptt split(treap t, int l)
    538 {
    539 	t = fix(t);
    540 	if(!t) return make_pair(t, t);
    541 	if(t->x < l)
    542 	{
    543 		auto z = split(t->r, l);
    544 		t->r = z.x;
    545 		return make_pair(fix(t), z.y);
    546 	}
    547 	else
    548 	{
    549 		auto z = split(t->l, l);
    550 		t->l = z.y;
    551 		return make_pair(z.x, fix(t));
    552 	}
    553 }
    554 
    555 treap merge(treap a, treap b)
    556 {
    557 	a = fix(a);
    558 	b = fix(b);
    559 	if(!a) return b;
    560 	if(!b) return a;
    561 	if(a->y > b->y)
    562 	{
    563 		a->r = merge(a->r, b);
    564 		return fix(a);
    565 	}
    566 	else
    567 	{
    568 		b->l = merge(a, b->l);
    569 		return fix(b);
    570 	}
    571 }
    572 
    573 struct comp
    574 {
    575 	li cur_sum;
    576 	int beg;
    577 	li treap_sum;
    578 	treap t;
    579 	
    580 	void upd()
    581 	{
    582 		cur_sum = treap_sum + beg * 1ll * getSum(t);
    583 	}
    584 	
    585 	void insert(int bi)
    586 	{
    587 		ptt p = split(t, bi);
    588 		treap_sum += getSum(p.x) + getSiz(p.y) * 1ll * bi;
    589 		t = merge(p.x, merge(new node(bi, rnd(), bi, 1, NULL, NULL), p.y));
    590 		upd();
    591 	}
    592 	
    593 	void fill_treap(treap t)
    594 	{
    595 		if(!t) return;
    596 		insert(t->x);
    597 		fill_treap(t->l);
    598 		fill_treap(t->r);
    599 	}
    600 };
    601 
    602 comp merge(comp a, comp b)
    603 {
    604 	if(getSiz(a.t) < getSiz(b.t))
    605 		swap(a, b);
    606 	a.beg = min(a.beg, b.beg);
    607 	a.fill_treap(b.t);
    608 	delete b.t;
    609 	a.upd();
    610 	return a;
    611 }
    612 
    613 set<int> free_pos;
    614 
    615 const int N = 400043;
    616 
    617 int p[N];
    618 int siz[N];
    619 comp cc[N];
    620 
    621 li start_sum = 0;
    622 li end_sum = 0;
    623 
    624 int get(int x)
    625 {
    626 	return (p[x] == x ? x : (p[x] = get(p[x])));
    627 }
    628 
    629 void merge(int x, int y)
    630 {
    631 	x = get(x);
    632 	y = get(y);
    633 	if(x == y) return;
    634 	if(siz[x] < siz[y]) swap(x, y);
    635 	end_sum -= cc[x].cur_sum;
    636 	end_sum -= cc[y].cur_sum;
    637 	p[y] = x;
    638 	siz[x] += siz[y];
    639 	cc[x] = merge(cc[x], cc[y]);
    640 	end_sum += cc[x].cur_sum;
    641 }
    642 
    643 void process(int ai, int bi)
    644 {
    645 	start_sum += ai * 1ll * bi;
    646 	int pos = *free_pos.lower_bound(ai);
    647 	free_pos.erase(pos);
    648 	siz[pos] = 1;
    649 	p[pos] = pos;
    650 	cc[pos].beg = pos;
    651 	cc[pos].insert(bi);
    652 	end_sum += cc[pos].cur_sum;
    653 	if(!free_pos.count(pos - 1))
    654 		merge(pos, pos - 1);
    655 	if(!free_pos.count(pos + 1))
    656 		merge(pos, pos + 1);
    657 	printf("%lld\n", end_sum - start_sum);
    658 }
    659 
    660 int main() {
    661 #ifdef _DEBUG
    662 	freopen("input.txt", "r", stdin);
    663 	freopen("output.txt", "w", stdout);
    664 #endif
    665     int n;
    666     scanf("%d", &n);
    667   	for(int i = 0; i < N; i++)
    668   		free_pos.insert(i);
    669 	for(int i = 0; i < n; i++)
    670 	{
    671 		int a, b;
    672 		scanf("%d %d", &a, &b);
    673 		process(a, b);
    674     }
    675     return 0;
    676 }
    677 ```