codeforces-scrape

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

1452.md (11642B)


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