codeforces-scrape

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

1101.md (10129B)


      1 Source: https://codeforces.com/blog/entry/64483
      2 
      3 [1101A - Minimum Integer](/contest/1101/problem/A "Educational Codeforces Round 58 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (BledDest)**
     10 
     11 ```
     12 q = int(input())
     13 for i in range(q):
     14     l, r, d = map(int, input().split())
     15     if(d < l or d > r):
     16         print(d)
     17     else:
     18         print((r // d) * d + d)
     19 ```
     20 
     21 [1101B - Accordion](/contest/1101/problem/B "Educational Codeforces Round 58 (Rated for Div. 2)")
     22 
     23 **Tutorial**
     24 
     25 Tutorial is loading...
     26 
     27 **Solution (Vovuh)**
     28 
     29 ```
     30 #include <bits/stdc++.h>
     31 
     32 using namespace std;
     33 
     34 void rem(string &s, const string &c) {
     35 	auto pos = s.find(c);
     36 	if (pos == string::npos) {
     37 		cout << -1 << endl;
     38 		exit(0);
     39 	}
     40 	s.erase(0, pos + 1);
     41 }
     42 
     43 int main() {
     44 #ifdef _DEBUG
     45 	freopen("input.txt", "r", stdin);
     46 //	freopen("output.txt", "w", stdout);
     47 #endif
     48 	
     49 	string s;
     50 	cin >> s;
     51 	
     52 	rem(s, "[");
     53 	rem(s, ":");
     54 	reverse(s.begin(), s.end());
     55 	rem(s, "]");
     56 	rem(s, ":");
     57 	
     58 	cout << count(s.begin(), s.end(), '|') + 4 << endl;
     59 	
     60 	return 0;
     61 }
     62 ```
     63 
     64 [1101C - Division and Union](/contest/1101/problem/C "Educational Codeforces Round 58 (Rated for Div. 2)")
     65 
     66 **Tutorial**
     67 
     68 Tutorial is loading...
     69 
     70 **Solution (adedalic)**
     71 
     72 ```
     73 #include<bits/stdc++.h>
     74 
     75 using namespace std;
     76 
     77 #define x first
     78 #define y second
     79 
     80 typedef pair<int, int> pt;
     81 
     82 int n;
     83 vector< pair<pt, int> > segs;
     84 
     85 inline bool read() {
     86 	if(!(cin >> n))
     87 		return false;
     88 	segs.resize(n);
     89 	for(int i = 0; i < n; i++) {
     90 		cin >> segs[i].x.x >> segs[i].x.y;
     91 		segs[i].y = i;
     92 	}
     93 	return true;
     94 }
     95 
     96 bool cmp(const pair<pt, int> &a, const pair<pt, int> &b) {
     97 	if(a.x.y != b.x.y)
     98 		return a.x.y < b.x.y;
     99 	if(a.x.x != b.x.x)
    100 		return a.x.x < b.x.x;
    101 	return a.y < b.y;
    102 }
    103 
    104 inline void solve() {
    105 	sort(segs.begin(), segs.end(), cmp);
    106 	
    107 	int mn = segs[n - 1].x.x;
    108 	for(int i = n - 2; i >= 0; i--) {
    109 		if(segs[i].x.y < mn) {
    110 			vector<int> ts(n, 2);
    111 			for(int id = 0; id <= i; id++)
    112 				ts[segs[id].y] = 1;
    113 			
    114 			for(int t : ts)
    115 				cout << t << ' ';
    116 			cout << '\n';
    117 				
    118 			return;
    119 		}
    120 		mn = min(mn, segs[i].x.x);
    121 	}
    122 	cout << -1 << '\n';
    123 }
    124 
    125 int main() {
    126 #ifdef _DEBUG
    127 	freopen("input.txt", "r", stdin);
    128 	int tt = clock();
    129 #endif
    130 	ios_base::sync_with_stdio(0);
    131 	cin.tie(0), cout.tie(0);
    132 	cout << fixed << setprecision(15);
    133 	
    134 	int tc;
    135 	cin >> tc;
    136 	
    137 	while(tc--) {
    138 		assert(read());
    139 		solve();
    140 		
    141 #ifdef _DEBUG
    142 		cerr << "TIME = " << clock() - tt << endl;
    143 		tt = clock();
    144 #endif
    145 	}
    146 	return 0;
    147 }
    148 ```
    149 
    150 [1101D - GCD Counting](/contest/1101/problem/D "Educational Codeforces Round 58 (Rated for Div. 2)")
    151 
    152 **Tutorial**
    153 
    154 Tutorial is loading...
    155 
    156 **Solution (PikMike)**
    157 
    158 ```
    159 #include <bits/stdc++.h>
    160 
    161 using namespace std;
    162 
    163 #define x first
    164 #define y second
    165 #define mp make_pair
    166 #define pb push_back
    167 #define sqr(a) ((a) * (a))
    168 #define sz(a) int(a.size())
    169 #define all(a) a.begin(), a.end()
    170 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    171 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    172 
    173 typedef long long li;
    174 typedef long double ld;
    175 typedef pair<int, int> pt;
    176 
    177 template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
    178 	return out << "(" << a.x << ", " << a.y << ")";
    179 }
    180 
    181 template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
    182 	out << "[";
    183 	forn(i, sz(v)) {
    184 		if(i) out << ", ";
    185 		out << v[i];
    186 	}
    187 	return out << "]";
    188 }
    189 
    190 mt19937 rnd(time(NULL));
    191 
    192 const int INF = int(1e9);
    193 const li INF64 = li(1e18);
    194 const int MOD = INF + 7;
    195 const ld EPS = 1e-9;
    196 const ld PI = acos(-1.0);
    197 
    198 const int N = 200 * 1000 + 13;
    199 
    200 int n;
    201 int a[N];
    202 vector<int> g[N];
    203 
    204 bool read () {
    205 	if (scanf("%d", &n) != 1)
    206 		return false;
    207 	forn(i, n)
    208 		g[i].clear();
    209 	forn(i, n)
    210 		scanf("%d", &a[i]);
    211 	forn(i, n - 1){
    212 		int x, y;
    213 		scanf("%d%d", &x, &y);
    214 		--x, --y;
    215 		g[x].pb(y);
    216 		g[y].pb(x);
    217 	}
    218 	return true;
    219 }
    220 
    221 vector<pt> dp[N];
    222 int ans;
    223 
    224 void calc(int v, int p = -1){
    225 	vector<pt> chd;
    226 	for (auto u : g[v]) if (u != p){
    227 		calc(u, v);
    228 		for (auto it : dp[u])
    229 			chd.pb(it);
    230 	}
    231 	
    232 	sort(all(chd));
    233 	forn(i, sz(chd)){
    234 		int j = i - 1;
    235 		int mx1 = 0, mx2 = 0;
    236 		while (j + 1 < sz(chd) && chd[j + 1].x == chd[i].x){
    237 			++j;
    238 			if (chd[j].y >= mx1)
    239 				mx2 = mx1, mx1 = chd[j].y;
    240 			else if (chd[j].y > mx2)
    241 				mx2 = chd[j].y;
    242 		}
    243 		if (a[v] % chd[i].x == 0){
    244 			ans = max(ans, mx1 + mx2 + 1);
    245 			dp[v].pb(mp(chd[i].x, mx1 + 1));
    246 			while (a[v] % chd[i].x == 0)
    247 				a[v] /= chd[i].x;
    248 		}
    249 		else{
    250 			ans = max(ans, mx1);
    251 		}
    252 		i = j;
    253 	}
    254 	
    255 	for (int i = 2; i * i <= a[v]; ++i) if (a[v] % i == 0){
    256 		dp[v].pb(mp(i, 1));
    257 		ans = max(ans, 1);
    258 		while (a[v] % i == 0)
    259 			a[v] /= i;
    260 	}
    261 	
    262 	if (a[v] > 1){
    263 		dp[v].pb(mp(a[v], 1));
    264 		ans = max(ans, 1);
    265 	}
    266 }
    267 
    268 void solve() {
    269 	forn(i, N) dp[i].clear();
    270 	ans = 0;
    271 	calc(0);
    272 	printf("%d\n", ans);
    273 }
    274 
    275 int main() {
    276 #ifdef _DEBUG
    277 	freopen("input.txt", "r", stdin);
    278 //	freopen("output.txt", "w", stdout);
    279 	
    280 	int tt = clock();
    281 	
    282 #endif
    283 	
    284 	cerr.precision(15);
    285 	cout.precision(15);
    286 	cerr << fixed;
    287 	cout << fixed;
    288 
    289 #ifdef _DEBUG
    290 	while(read()) {	
    291 #else
    292 	if (read()){
    293 #endif
    294 		solve();
    295 		
    296 #ifdef _DEBUG
    297 	cerr << "TIME = " << clock() - tt << endl;
    298 	tt = clock();
    299 #endif
    300 
    301 	}
    302 }
    303 ```
    304 
    305 [1101E - Polycarp's New Job](/contest/1101/problem/E "Educational Codeforces Round 58 (Rated for Div. 2)")
    306 
    307 **Tutorial**
    308 
    309 Tutorial is loading...
    310 
    311 **Solution (PikMike)**
    312 
    313 ```
    314 #include <bits/stdc++.h>
    315 
    316 #define forn(i, n) for (int i = 0; i < int(n); i++)
    317 
    318 using namespace std;
    319 
    320 int main() {
    321 	int n;
    322 	scanf("%d", &n);
    323 	int mxa = 0, mxb = 0;
    324 	static char buf[5];
    325 	forn(i, n){
    326 		int x, y;
    327 		scanf("%s%d%d", buf, &x, &y);
    328 		if (x < y)
    329 			swap(x, y);
    330 		if (buf[0] == '+'){
    331 			mxa = max(mxa, x);
    332 			mxb = max(mxb, y);
    333 		}
    334 		else{
    335 			puts(mxa <= x && mxb <= y ? "YES" : "NO");
    336 		}
    337 	}
    338 }
    339 ```
    340 
    341 [1101F - Trucks and Cities](/contest/1101/problem/F "Educational Codeforces Round 58 (Rated for Div. 2)")
    342 
    343 **Tutorial**
    344 
    345 Tutorial is loading...
    346 
    347 **Solution 1 (adedalic)**
    348 
    349 ```
    350 #include<bits/stdc++.h>
    351 using namespace std;
    352 
    353 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    354 
    355 #define sz(a) int((a).size())
    356 #define all(a) (a).begin(), (a).end()
    357 
    358 #define mp make_pair
    359 #define pb push_back
    360 
    361 #define x first
    362 #define y second
    363 
    364 typedef long long li;
    365 typedef pair<int, int> pt;
    366 
    367 const int INF = int(1e9);
    368 const int N = 411;
    369 
    370 int n, m;
    371 int a[N];
    372 vector< pair<pt, pt> > qs;
    373 
    374 inline bool read() {
    375 	if(!(cin >> n >> m))
    376 		return false;
    377 	fore(i, 0, n)
    378 		cin >> a[i];
    379 	qs.resize(m);
    380 	fore(i, 0, m) {
    381 		cin >> qs[i].x.x >> qs[i].x.y >> qs[i].y.x >> qs[i].y.y;
    382 		qs[i].x.x--; qs[i].x.y--;
    383 	}
    384 	return true;
    385 }
    386 
    387 vector<int> ids[N];
    388 int d[N][N];
    389 
    390 inline void solve() {
    391 	fore(i, 0, m)
    392 		ids[qs[i].x.x].push_back(i);
    393 	li ans = -1;
    394 	
    395 	fore(l, 0, n) {
    396 		fore(r, l, n)
    397 			d[0][r] = a[r] - a[l];
    398 		
    399 		fore(k, 1, n + 1) {
    400 			int opt = l;
    401 			fore(r, l, n) {
    402 				while(opt < r && max(d[k - 1][opt], a[r] - a[opt]) >= max(d[k - 1][opt + 1], a[r] - a[opt + 1]))
    403 					opt++;
    404 				
    405 				d[k][r] = max(d[k - 1][opt], a[r] - a[opt]);
    406 			}
    407 		}
    408 		
    409 		for(int id : ids[l])
    410 			ans = max(ans, d[qs[id].y.y][qs[id].x.y] * 1ll * qs[id].y.x);
    411 	}
    412 	
    413 	cout << ans << endl;
    414 }
    415 
    416 int main() {
    417 #ifdef _DEBUG
    418 	freopen("input.txt", "r", stdin);
    419 	int tt = clock();
    420 #endif
    421 	ios_base::sync_with_stdio(0);
    422 	cin.tie(0), cout.tie(0);
    423 	cout << fixed << setprecision(15);
    424 	
    425 	if(read()) {
    426 		solve();
    427 		
    428 #ifdef _DEBUG
    429 		cerr << "TIME = " << clock() - tt << endl;
    430 		tt = clock();
    431 #endif
    432 	}
    433 	return 0;
    434 }
    435 ```
    436 
    437 **Solution 2 (adedalic)**
    438 
    439 ```
    440 #include<bits/stdc++.h>
    441 using namespace std;
    442 
    443 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    444 
    445 #define sz(a) int((a).size())
    446 #define all(a) (a).begin(), (a).end()
    447 
    448 #define mp make_pair
    449 #define pb push_back
    450 
    451 #define x first
    452 #define y second
    453 
    454 typedef long long li;
    455 typedef pair<int, int> pt;
    456 
    457 const int INF = int(1e9);
    458 const li INF64 = li(1e18);
    459 const int N = 411;
    460 
    461 int n, m;
    462 int a[N];
    463 vector< pair<pt, pt> > qs;
    464 
    465 inline bool read() {
    466 	if(!(cin >> n >> m))
    467 		return false;
    468 	fore(i, 0, n)
    469 		cin >> a[i];
    470 	qs.resize(m);
    471 	fore(i, 0, m) {
    472 		cin >> qs[i].x.x >> qs[i].x.y >> qs[i].y.x >> qs[i].y.y;
    473 		qs[i].x.x--; qs[i].x.y--;
    474 	}
    475 	return true;
    476 }
    477 
    478 int getCnt(const pair<pt, pt> &q, li mx) {
    479 	li dist = mx / q.y.x;
    480 	
    481 	int s = q.x.x, f = q.x.y;
    482 	int u = s, cnt = 0;
    483 	while(u < f) {
    484 		int v = u;
    485 		while(v < f && a[v + 1] - a[u] <= dist)
    486 			v++;
    487 		
    488 		if(v == u)
    489 			return INF;
    490 		
    491 		cnt++;
    492 		u = v;
    493 	}
    494 	return cnt - 1;
    495 }
    496 
    497 li upd(const pair<pt, pt> &q, li lf, li rg) {
    498 	if(getCnt(q, lf) <= q.y.y)
    499 		return lf;
    500 	
    501 	while(rg - lf > 1) {
    502 		li mid = (lf + rg) >> 1;
    503 		(getCnt(q, mid) <= q.y.y ? rg : lf) = mid;
    504 	}
    505 	return rg;
    506 }
    507 
    508 inline unsigned int getHash(const vector<int> &vals) {
    509 	unsigned int hash = 0;
    510 	for(int v : vals)
    511 		hash = hash * 3 + v;
    512 	return hash;
    513 }
    514 
    515 inline void solve() {
    516 	auto seed = getHash(vector<int>(a, a + n));
    517 	fore(i, 0, m)
    518 		seed = seed * 3 + getHash({qs[i].x.x, qs[i].x.y, qs[i].y.x, qs[i].y.y});
    519 	mt19937 rnd(seed);
    520 	
    521 	vector<int> ids(m, 0);
    522 	iota(all(ids), 0);
    523 	shuffle(all(ids), rnd);
    524 	
    525 	li curv = 0;
    526 	for(int id : ids)
    527 		curv = upd(qs[id], curv, 2 * INF64);
    528 	cout << curv << endl;
    529 }
    530 
    531 int main() {
    532 #ifdef _DEBUG
    533 	freopen("input.txt", "r", stdin);
    534 	int tt = clock();
    535 #endif
    536 	ios_base::sync_with_stdio(0);
    537 	cin.tie(0), cout.tie(0);
    538 	cout << fixed << setprecision(15);
    539 	
    540 	if(read()) {
    541 		solve();
    542 		
    543 #ifdef _DEBUG
    544 		cerr << "TIME = " << clock() - tt << endl;
    545 		tt = clock();
    546 #endif
    547 	}
    548 	return 0;
    549 }
    550 ```
    551 
    552 [1101G - (Zero XOR Subset)-less](/contest/1101/problem/G "Educational Codeforces Round 58 (Rated for Div. 2)")
    553 
    554 **Tutorial**
    555 
    556 Tutorial is loading...
    557 
    558 **Solution (PikMike)**
    559 
    560 ```
    561 #include <bits/stdc++.h>
    562 
    563 #define forn(i, n) for (int i = 0; i < int(n); i++)
    564 
    565 using namespace std;
    566 
    567 const int N = 200 * 1000 + 13;
    568 const int LOGN = 30;
    569 
    570 int n;
    571 int a[N], pr[N];
    572 int base[LOGN];
    573 
    574 void try_gauss(int v){
    575 	for(int i = LOGN - 1; i >= 0; i--)
    576 		if (base[i] != -1 && (v & (1 << i)))
    577 			v ^= base[i];
    578 	if (v == 0)
    579 		return;
    580 	for(int i = LOGN - 1; i >= 0; i--) if (v & (1 << i)){
    581 		base[i] = v;
    582 		return;
    583 	}
    584 }
    585 
    586 int main() {
    587 	scanf("%d", &n);
    588 	forn(i, n)
    589 		scanf("%d", &a[i]);
    590 	memset(base, -1, sizeof(base));
    591 	forn(i, n){
    592 		pr[i + 1] = pr[i] ^ a[i];
    593 		try_gauss(pr[i + 1]);
    594 	}
    595 	if (pr[n] == 0){
    596 		puts("-1");
    597 		return 0;
    598 	}
    599 	int siz = 0;
    600 	forn(i, LOGN)
    601 		siz += (base[i] != -1);
    602 	printf("%d\n", siz);
    603 }
    604 ```