codeforces-scrape

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

1016.md (11791B)


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