codeforces-scrape

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

990.md (11940B)


      1 Source: https://codeforces.com/blog/entry/59962
      2 
      3 [990A - Commentary Boxes](/contest/990/problem/A "Educational Codeforces Round 45 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (PikMike)**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 #define forn(i, n) for(int i = 0; i < int(n); i++)
     15  
     16 using namespace std;
     17 
     18 int main() {
     19 	long long n, m;
     20 	int a, b;
     21 	
     22 	cin >> n >> m >> a >> b;
     23 	cout << min(n % m * b, (m - n % m) * a) << endl;
     24 	return 0;
     25 }
     26 ```
     27 
     28 [990B - Micro-World](/contest/990/problem/B "Educational Codeforces Round 45 (Rated for Div. 2)")
     29 
     30 **Tutorial**
     31 
     32 Tutorial is loading...
     33 
     34 **Solution (adedalic)**
     35 
     36 ```
     37 #include<bits/stdc++.h>
     38 
     39 using namespace std;
     40 
     41 const int N = 200 * 1000 + 555;
     42 int n, k, a[N];
     43 
     44 inline bool read() {
     45 	if(!(cin >> n >> k))
     46 		return false;
     47 	for(int i = 0; i < n; i++)
     48 		assert(scanf("%d", &a[i]) == 1);
     49 	return true;
     50 }
     51 
     52 inline void solve() {
     53 	sort(a, a + n);
     54 	a[n++] = int(2e9);
     55 	
     56 	int ans = 0, u = 0;
     57 	for(int i = 0; i < n - 1; i++) {
     58 		while(u < n && a[i] == a[u])
     59 			u++;
     60 		if(a[u] - a[i] > k)
     61 			ans++;
     62 	}
     63 	cout << ans << endl;
     64 }
     65 
     66 int main() {
     67 #ifdef _DEBUG
     68 	freopen("input.txt", "r", stdin);
     69 	int tt = clock();
     70 #endif
     71 
     72 	if(read()) {
     73 		solve();
     74 #ifdef _DEBUG
     75 		cerr << "TIME = " << clock() - tt << endl;
     76 #endif
     77 	}
     78 	return 0;
     79 }
     80 ```
     81 
     82 [990C - Bracket Sequences Concatenation Problem](/contest/990/problem/C "Educational Codeforces Round 45 (Rated for Div. 2)")
     83 
     84 **Tutorial**
     85 
     86 Tutorial is loading...
     87 
     88 **Solution (Ajosteen)**
     89 
     90 ```
     91 #include <bits/stdc++.h>
     92 
     93 using namespace std;
     94 
     95 const int N = int(3e5) + 7;
     96 
     97 int n;
     98 string s[N];
     99 char buf[N];
    100 int cnt[N];
    101 
    102 int getBalance(string &s){
    103 	int bal = 0;
    104 	for(int i = 0; i < s.size(); ++i){
    105 		if(s[i] == '(')
    106 			++bal;
    107 		else
    108 			--bal;
    109 		
    110 		if(bal < 0)
    111 			return -1;
    112 	}
    113 	
    114 	return bal;
    115 }
    116 
    117 string rev(string &s){
    118 	string revs = s;
    119 	reverse(revs.begin(), revs.end());
    120 	for(int i = 0; i < revs.size(); ++i)
    121 		if(revs[i] == '(')
    122 			revs[i] = ')';
    123 		else
    124 			revs[i] = '(';
    125 		
    126 	return revs;
    127 }
    128 
    129 int main(){
    130 	scanf("%d", &n);
    131 	for(int i = 0; i < n; ++i){
    132 		scanf("%s", buf);
    133 		s[i] = buf;
    134 	}
    135 
    136 	for(int i = 0; i < n; ++i){
    137 		int bal = getBalance(s[i]);
    138 		if(bal != -1)
    139 			++cnt[bal];
    140 	}
    141 	
    142 	long long res = 0;	
    143 	for(int i = 0; i < n; ++i){
    144 		s[i] = rev(s[i]);
    145 		int bal = getBalance(s[i]);
    146 		if(bal != -1)
    147 			res += cnt[bal];
    148 	}
    149 	
    150 	printf("%I64d\n", res);
    151 	return 0;
    152 }
    153 ```
    154 
    155 [990D - Graph And Its Complement](/contest/990/problem/D "Educational Codeforces Round 45 (Rated for Div. 2)")
    156 
    157 **Tutorial**
    158 
    159 Tutorial is loading...
    160 
    161 **Solution (Ajosteen)**
    162 
    163 ```
    164 #include <bits/stdc++.h>
    165 
    166 using namespace std;
    167 
    168 const int N = int(1e3) + 7;
    169 
    170 int n, a, b;
    171 bool mat[N][N];
    172 
    173 int main(){
    174 	scanf("%d %d %d", &n, &a, &b);
    175 
    176 	if(min(a, b) > 1){
    177 		puts("NO");
    178 		return 0;
    179 	}
    180 	
    181 	if(a == 1 && b == 1){
    182 		if(n == 2 || n == 3){
    183 			puts("NO");
    184 			return 0;
    185 		}
    186 		puts("YES");
    187 		for(int i = 1; i < n; ++i)
    188 			mat[i][i - 1] = mat[i - 1][i] = true;
    189 		for(int i = 0; i < n; ++i){
    190 			for(int j = 0; j < n; ++j)
    191 				printf("%c", '0' + mat[i][j]);
    192 			puts("");
    193 		}
    194 		return 0;
    195 	}
    196 	
    197 	bool x = false;
    198 	if(a == 1){
    199 		swap(a, b);
    200 		x = true;
    201 	}
    202 	for(int i = n - a; i > 0; --i)
    203 		mat[i][i - 1] = mat[i - 1][i] = true;
    204 	puts("YES");
    205 	for(int i = 0; i < n; ++i){
    206 			for(int j = 0; j < n; ++j)
    207 				printf("%c", '0' + ((x ^ mat[i][j]) && (i != j)));
    208 			puts("");
    209 		}
    210 	return 0;
    211 }
    212 ```
    213 
    214 [990E - Post Lamps](/contest/990/problem/E "Educational Codeforces Round 45 (Rated for Div. 2)")
    215 
    216 **Tutorial**
    217 
    218 Tutorial is loading...
    219 
    220 **Solution (PikMike)**
    221 
    222 ```
    223 #include <bits/stdc++.h>
    224 
    225 #define forn(i, n) for (int i = 0; i < int(n); i++)
    226 
    227 using namespace std;
    228 
    229 const int INF = 1e9;
    230 const long long INF64 = 1e18;
    231 const int N = 1000 * 1000 + 13;
    232 
    233 int n, m, k;
    234 bool pos[N];
    235 int lst[N], s[N], a[N];
    236 
    237 int get(int l){
    238 	int r = 0, i = -1, res = 0;
    239 	while (r < n){
    240 		if (lst[r] <= i)
    241 			return INF;
    242 		i = lst[r];
    243 		r = lst[r] + l;
    244 		++res;
    245 	}
    246 	return res;
    247 }
    248 
    249 int main() {
    250 	scanf("%d%d%d", &n, &m, &k);
    251 	forn(i, m) scanf("%d", &s[i]);
    252 	forn(i, k) scanf("%d", &a[i]);
    253 	forn(i, n) pos[i] = true;
    254 	forn(i, m) pos[s[i]] = false;
    255 	forn(i, n){
    256 		if (pos[i])
    257 			lst[i] = i;
    258 		else if (i)
    259 			lst[i] = lst[i - 1];
    260 		else
    261 			lst[i] = -1;
    262 	}
    263 	long long ans = INF64;
    264 	forn(i, k){
    265 		long long t = get(i + 1);
    266 		if (t != INF)
    267 			ans = min(ans, a[i] * t);
    268 	}
    269 	printf("%lld\n", ans == INF64 ? -1 : ans);
    270 	return 0;
    271 }
    272 ```
    273 
    274 [990F - Flow Control](/contest/990/problem/F "Educational Codeforces Round 45 (Rated for Div. 2)")
    275 
    276 **Tutorial**
    277 
    278 Tutorial is loading...
    279 
    280 **Solution (PikMike)**
    281 
    282 ```
    283 #include <bits/stdc++.h>
    284 
    285 #define forn(i, n) for (int i = 0; i < int(n); i++)
    286 
    287 using namespace std;
    288 
    289 mt19937 rnd(time(NULL));
    290 
    291 const int N = 1'000'013;
    292 
    293 int n, m;
    294 pair<int, int> e[N];
    295 int a[N], rk[N];
    296 long long sum[N], ans[N];
    297 
    298 int p[N];
    299 
    300 int getP(int a){
    301 	return (a == p[a] ? a : p[a] = getP(p[a]));
    302 }
    303 
    304 bool merge(int a, int b){
    305 	a = getP(a);
    306 	b = getP(b);
    307 	if (a == b) return false;
    308 	if (rk[a] > rk[b]) swap(a, b);
    309 	p[a] = b;
    310 	rk[b] += rk[a];
    311 	return true;
    312 }
    313 
    314 bool used[N];
    315 vector<int> g[N];
    316 int h[N];
    317 
    318 void dfs(int v, int p){
    319 	sum[v] = a[v];
    320 	for (auto u : g[v]){
    321 		if (u != p){
    322 			h[u] = h[v] + 1;
    323 			dfs(u, v);
    324 			sum[v] += sum[u];
    325 		}
    326 	}
    327 }
    328 
    329 int main() {
    330 	scanf("%d", &n);
    331 	forn(i, n)
    332 		scanf("%d", &a[i]);
    333 	
    334 	forn(i, n) p[i] = i, rk[i] = 1;
    335 	scanf("%d", &m);
    336 	forn(i, m){
    337 		int &v = e[i].first;
    338 		int &u = e[i].second;
    339 		scanf("%d%d", &v, &u);
    340 		--v, --u;
    341 		if (merge(v, u)){
    342 			g[v].push_back(u);
    343 			g[u].push_back(v);
    344 			used[i] = true;
    345 		}
    346 	}
    347 	
    348 	long long tot = 0;
    349 	forn(i, n) tot += a[i];
    350 	if (tot != 0){
    351 		puts("Impossible");
    352 		return 0;
    353 	}
    354 	
    355 	dfs(0, -1);
    356 	
    357 	puts("Possible");
    358 	forn(i, m){
    359 		if (used[i]){
    360 			int v = e[i].first, u = e[i].second;
    361 			if (h[v] < h[u])
    362 				ans[i] = sum[u];
    363 			else
    364 				ans[i] = -sum[v];
    365 		}
    366 		printf("%lld\n", ans[i]);
    367 	}
    368 	return 0;
    369 }
    370 ```
    371 
    372 [990G - GCD Counting](/contest/990/problem/G "Educational Codeforces Round 45 (Rated for Div. 2)")
    373 
    374 **Tutorial**
    375 
    376 Tutorial is loading...
    377 
    378 **Solution with Möbius (Bleddest)**
    379 
    380 ```
    381 #include<bits/stdc++.h>
    382 
    383 using namespace std;
    384 
    385 const int N = 200043;
    386 
    387 int d[N];
    388 
    389 void sieve()
    390 {
    391 	vector<int> pr;
    392  	for(int i = 2; i < N; i++) 
    393  	{
    394 		if (d[i] == 0) 
    395 		{
    396 			d[i] = i;
    397 			pr.push_back(i);
    398 		}
    399 		for(auto x : pr)
    400 		{
    401 			if (x > d[i] || x * 1ll * i >= N)
    402 				break;
    403 			d[i * x] = x;
    404 		}
    405 	}
    406 }
    407 
    408 int mobius(int x)
    409 {
    410 	int last = -1;
    411 	int res = 1;
    412 	while(x != 1)
    413 	{
    414 		if(last == d[x])
    415 			res = 0;
    416 		else
    417 			res = -res;
    418 		last = d[x];
    419 		x /= d[x];
    420 	}
    421 	return res;
    422 }
    423 
    424 int mb[N];
    425 
    426 vector<int> need_bfs[N];
    427 int used[N];
    428 vector<int> g[N];
    429 int a[N];
    430 int cc = 0;
    431 int q[N];
    432 int hd, tl;
    433 int good[N];
    434 
    435 int bfs(int x, int gc)
    436 {
    437     hd = 0;
    438     tl = 0;
    439     q[tl++] = x;
    440     used[x] = cc;
    441     while(hd < tl)
    442     {
    443         int z = q[hd++];
    444         for(auto y : g[z])
    445         {
    446             if(good[a[y]] == cc && used[y] < cc)
    447             {
    448                 used[y] = cc;
    449                 q[tl++] = y;
    450             }
    451         }
    452     }
    453 	return tl;
    454 }
    455 
    456 long long ans1[N];
    457 long long ans2[N];
    458 
    459 int main() {
    460 	sieve();
    461 	for(int i = 1; i < N; i++)
    462 		mb[i] = mobius(i);
    463 	int n;
    464 	scanf("%d", &n);
    465 	for(int i = 0; i < n; i++)
    466 		scanf("%d", &a[i]);
    467 	for(int i = 0; i < n - 1; i++)
    468 	{
    469 		int x, y;
    470 		scanf("%d %d", &x, &y);
    471 		--x;
    472 		--y;
    473 		g[x].push_back(y);
    474 		g[y].push_back(x);
    475 	}
    476 	for(int i = 0; i < n; i++)
    477 	{
    478 		need_bfs[a[i]].push_back(i);
    479 	}
    480 	for(int i = 200000; i >= 1; i--)
    481 	{
    482 		cc++;
    483 		for(int j = i; j <= 200000; j += i)
    484 		    good[j] = cc;
    485 		for(int j = i; j <= 200000; j += i)
    486 		    for(auto x : need_bfs[j])
    487 		    {
    488 		        if(used[x] == cc) continue;
    489 			    int z = bfs(x, i);
    490 			    ans1[i] += z * 1ll * (z + 1) / 2;
    491 		    }
    492 	    for(int j = i, k = 1; j <= 200000; j += i, k++)
    493 	        ans2[i] += mb[k] * ans1[j];
    494 	}
    495 	for(int i = 1; i <= 200000; i++)
    496 		if(ans2[i])
    497 			printf("%d %lld\n", i, ans2[i]);
    498 	return 0;
    499 }
    500 ```
    501 
    502 **Solution with centroid (adedalic)**
    503 
    504 ```
    505 #include<bits/stdc++.h>
    506 
    507 using namespace std;
    508 
    509 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    510 
    511 #define x first
    512 #define y second
    513 
    514 typedef long long li;
    515 typedef long double ld;
    516 typedef pair<int, int> pt;
    517 
    518 template<class A, class B> ostream& operator <<(ostream &out, const pair<A, B> &p) {
    519 	return out << "(" << p.x << ", " << p.y << ")";
    520 }
    521 
    522 template<class A> ostream& operator <<(ostream &out, const vector<A> &v) {
    523 	out << "[";
    524 	for(auto &e : v)
    525 		out << e << ", ";
    526 	return out << "]";
    527 }
    528 
    529 const int N = 1000 * 1000 + 555;
    530 const int LOGN = 21;
    531 int mind[N];
    532 int pw[LOGN][N];
    533 
    534 int n, a[N];
    535 vector<int> g[N];
    536 li res[N];
    537 
    538 bool gen() {
    539 	mt19937 rnd(42);
    540 	n = 200 * 1000;
    541 	fore(i, 0, n)
    542 		a[i] = 831600;
    543 	fore(i, 1, n) {
    544 		int u = rnd() % i, v = i;
    545 		g[u].push_back(v);
    546 		g[v].push_back(u);
    547 	}
    548 	return true;
    549 }
    550 
    551 inline bool read() {
    552 //	return gen();
    553 	if(!(cin >> n))
    554 		return false;
    555 	fore(i, 0, n)
    556 		assert(scanf("%d", &a[i]) == 1);
    557 	fore(i, 0, n - 1) {
    558 		int u, v;
    559 		assert(scanf("%d%d", &u, &v) == 2);
    560 		u--, v--;
    561 		
    562 		g[u].push_back(v);
    563 		g[v].push_back(u);
    564 	}
    565 	return true;
    566 }
    567 
    568 vector<pt> dv[N];
    569 
    570 inline int gcd(int a, int b) {
    571 	int ans = 1;
    572 	unsigned int u = 0, v = 0;
    573 	while(u < dv[a].size() && v < dv[b].size()) {
    574 		if(dv[a][u].x < dv[b][v].x)
    575 			u++;
    576 		else if(dv[a][u].x > dv[b][v].x)
    577 			v++;
    578 		else {
    579 			ans *= pw[min(dv[a][u].y, dv[b][v].y)][dv[a][u].x];
    580 			u++, v++;
    581 		}
    582 	}
    583 	return ans;
    584 }
    585 
    586 bool used[N];
    587 int sz[N];
    588 
    589 void calcSz(int v, int p) {
    590 	sz[v] = 1;
    591 	for(int to : g[v]) {
    592 		if(to == p || used[to])
    593 			continue;
    594 		calcSz(to, v);
    595 		sz[v] += sz[to];
    596 	}
    597 }
    598 
    599 int findC(int v, int p, int all) {
    600 	for(int to : g[v]) {
    601 		if(to == p || used[to])
    602 			continue;
    603 		if(sz[to] > all / 2)
    604 			return findC(to, v, all);
    605 	}
    606 	return v;
    607 }
    608 
    609 int u[N], T = 0;
    610 int cntD[N];
    611 
    612 inline void addDiv(int d, int cnt) {
    613 	if(u[d] != T)
    614 		u[d] = T, cntD[d] = 0;
    615 	cntD[d] += cnt;
    616 }
    617 
    618 int cds[N], szcds;
    619 
    620 void calcDs(int v, int p, int gc) {
    621 	gc = gcd(a[v], gc);
    622 	cds[szcds++] = gc;
    623 	for(int to : g[v]) {
    624 		if(to == p || used[to])
    625 			continue;
    626 		calcDs(to, v, gc);
    627 	}
    628 }
    629 
    630 vector<int> cps, cmx, vmx;
    631 
    632 void check(int curd, int curg, int pos, int add) {
    633 	if(pos >= (int)cps.size()) {
    634 		if(u[curd] == T)
    635 			res[curg] += cntD[curd] * 1ll * add;
    636 		return;
    637 	}
    638 	
    639 	fore(st, 0, cmx[pos] + 1) {
    640 		check(curd, curg, pos + 1, add);
    641 		
    642 		curd *= cps[pos];
    643 		if(st < vmx[pos])
    644 			curg *= cps[pos];
    645 	}
    646 }
    647 
    648 pt ops[N]; int szops;
    649 int cntDiff[N];
    650 
    651 void calc(int v) {
    652 	calcSz(v, -1);
    653 	int c = findC(v, -1, sz[v]);
    654 	used[c] = 1;
    655 	
    656 //	cerr << "C = "<< c << endl;
    657 	
    658 	cps.resize(dv[a[c]].size());
    659 	cmx.resize(cps.size());
    660 	vmx.resize(cmx.size());
    661 	
    662 	fore(i, 0, cps.size()) {
    663 		cps[i] = dv[a[c]][i].x;
    664 		cmx[i] = dv[a[c]][i].y;
    665 	}
    666 	
    667 	T++;
    668 	addDiv(a[c], 1);
    669 	
    670 	for(int to : g[c]) {
    671 		if(used[to]) continue;
    672 		
    673 		szcds = 0;
    674 		calcDs(to, c, a[c]);
    675 		fore(i, 0, szcds)
    676 			cntDiff[cds[i]]++;
    677 			
    678 		szops = 0;
    679 		fore(j, 0, szcds) {
    680 			if(cntDiff[cds[j]] == 0)
    681 				continue;
    682 			
    683 			int p = 0, val = cds[j];
    684 			fore(i, 0, vmx.size()) {
    685 				if(p >= (int)dv[val].size() || dv[val][p].x > cps[i])
    686 					vmx[i] = 0;
    687 				else
    688 					vmx[i] = dv[val][p].y, p++;
    689 			}
    690 			
    691 			check(1, 1, 0, cntDiff[cds[j]]);
    692 			ops[szops++] = {cds[j], cntDiff[cds[j]]};
    693 			cntDiff[cds[j]] = 0;
    694 		}
    695 		
    696 		fore(j, 0, szops)
    697 			addDiv(ops[j].x, ops[j].y);
    698 	}
    699 	
    700 	for(int to : g[c]) {
    701 		if(used[to]) continue;
    702 		calc(to);
    703 	}
    704 }
    705 
    706 inline void solve() {
    707 	iota(mind, mind + N, 0);
    708 	fore(i, 2, N) {
    709 		if(mind[i] != i)
    710 			continue;
    711 		
    712 		pw[0][i] = 1;
    713 		fore(st, 1, LOGN)
    714 			pw[st][i] = pw[st - 1][i] * i;
    715 		
    716 		for(li j = i * 1ll * i; j < N; j += i)
    717 			mind[j] = min(mind[j], i);
    718 	}
    719 	fore(i, 2, N) {
    720 		int val = i;
    721 		while(mind[val] > 1) {
    722 			if(dv[i].empty() || dv[i].back().x != mind[val])
    723 				dv[i].emplace_back(mind[val], 0);
    724 			dv[i].back().y++;
    725 			val /= mind[val];
    726 		}
    727 	}
    728 	
    729 	memset(res, 0, sizeof res);
    730 	
    731 	T = 0;
    732 	calc(0);
    733 	
    734 	fore(i, 0, n)
    735 		res[a[i]]++;
    736 	
    737 	fore(i, 1, 1000'000 + 1) {
    738 		if(res[i])
    739 			printf("%d %lld\n", i, res[i]);
    740 	}
    741 }
    742 
    743 int main() {
    744 #ifdef _DEBUG
    745 	freopen("input.txt", "r", stdin);
    746 	int tt = clock();
    747 #endif
    748 
    749 	if(read()) {
    750 		solve();
    751 #ifdef _DEBUG
    752 		cerr << "TIME = " << clock() - tt << endl;
    753 #endif
    754 	}
    755 	return 0;
    756 }
    757 ```