codeforces-scrape

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

1249.md (10051B)


      1 Source: https://codeforces.com/blog/entry/70779
      2 
      3 All ideas belong to [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov").
      4 
      5 [1249A - Yet Another Dividing into Teams](/contest/1249/problem/A "Codeforces Round 595 (Div. 3)")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19 #ifdef _DEBUG
     20 	freopen("input.txt", "r", stdin);
     21 //	freopen("output.txt", "w", stdout);
     22 #endif
     23 	
     24 	int q;
     25 	cin >> q;
     26 	for (int i = 0; i < q; ++i) {
     27 		int n;
     28 		cin >> n;
     29 		vector<int> a(n);
     30 		for (int j = 0; j < n; ++j) {
     31 			cin >> a[j];
     32 		}
     33 		bool ok = true;
     34 		for (int p1 = 0; p1 < n; ++p1) {
     35 			for (int p2 = 0; p2 < p1; ++p2) {
     36 				ok &= abs(a[p1] - a[p2]) != 1;
     37 			}
     38 		}
     39 		cout << 2 - ok << endl;
     40 	}
     41 	
     42 	return 0;
     43 }
     44 ```
     45 
     46 [1249B1 - Books Exchange (easy version)](/contest/1249/problem/B1 "Codeforces Round 595 (Div. 3)")
     47 
     48 **Tutorial**
     49 
     50 Tutorial is loading...
     51 
     52 **Solution**
     53 
     54 ```
     55 #include <bits/stdc++.h>
     56 
     57 using namespace std;
     58 
     59 int main() {
     60 #ifdef _DEBUG
     61 	freopen("input.txt", "r", stdin);
     62 //	freopen("output.txt", "w", stdout);
     63 #endif
     64 	
     65 	int q;
     66 	cin >> q;
     67 	for (int i = 0; i < q; ++i) {
     68 		int n;
     69 		cin >> n;
     70 		vector<int> p(n);
     71 		for (int j = 0; j < n; ++j) {
     72 			cin >> p[j];
     73 			--p[j];
     74 		}
     75 		for (int j = 0; j < n; ++j) {
     76 			int cnt = 0;
     77 			int k = j;
     78 			do {
     79 				++cnt;
     80 				k = p[k];
     81 			} while (k != j);
     82 			cout << cnt << " ";
     83 		}
     84 		cout << endl;
     85 	}
     86 	
     87 	return 0;
     88 }
     89 ```
     90 
     91 [1249B2 - Books Exchange (hard version)](/contest/1249/problem/B2 "Codeforces Round 595 (Div. 3)")
     92 
     93 **Tutorial**
     94 
     95 Tutorial is loading...
     96 
     97 **Solution**
     98 
     99 ```
    100 #include <bits/stdc++.h>
    101 
    102 using namespace std;
    103 
    104 int main() {
    105 #ifdef _DEBUG
    106 	freopen("input.txt", "r", stdin);
    107 //	freopen("output.txt", "w", stdout);
    108 #endif
    109 	
    110 	int q;
    111 	cin >> q;
    112 	for (int i = 0; i < q; ++i) {
    113 		int n;
    114 		cin >> n;
    115 		vector<int> p(n);
    116 		for (int j = 0; j < n; ++j) {
    117 			cin >> p[j];
    118 			--p[j];
    119 		}
    120 		vector<int> used(n);
    121 		vector<int> ans(n);
    122 		for (int j = 0; j < n; ++j) {
    123 			if (!used[j]) {
    124 				vector<int> cur;
    125 				while (!used[j]) {
    126 					cur.push_back(j);
    127 					used[j] = true;
    128 					j = p[j];
    129 				}
    130 				for (auto el : cur) ans[el] = cur.size();
    131 			}
    132 		}
    133 		for (int j = 0; j < n; ++j) cout << ans[j] << " ";
    134 		cout << endl;
    135 	}
    136 	
    137 	return 0;
    138 }
    139 ```
    140 
    141 [1249C1 - Good Numbers (easy version)](/contest/1249/problem/C1 "Codeforces Round 595 (Div. 3)")
    142 
    143 **Tutorial**
    144 
    145 Tutorial is loading...
    146 
    147 **Solution**
    148 
    149 ```
    150 #include <bits/stdc++.h>
    151 
    152 using namespace std;
    153 
    154 int main() {
    155 #ifdef _DEBUG
    156 	freopen("input.txt", "r", stdin);
    157 //	freopen("output.txt", "w", stdout);
    158 #endif
    159 	
    160 	int q;
    161 	cin >> q;
    162 	for (int i = 0; i < q; ++i) {
    163 		int n;
    164 		cin >> n;
    165 		while (true) {
    166 			bool ok = true;
    167 			int cur = n;
    168 			while (cur > 0) {
    169 				if (ok && cur % 3 == 2) ok = false;
    170 				cur /= 3;
    171 			}
    172 			if (ok) break;
    173 			++n;
    174 		}
    175 		cout << n << endl;
    176 	}
    177 	
    178 	return 0;
    179 }
    180 ```
    181 
    182 [1249C2 - Good Numbers (hard version)](/contest/1249/problem/C2 "Codeforces Round 595 (Div. 3)")
    183 
    184 **Tutorial**
    185 
    186 Tutorial is loading...
    187 
    188 **Solution**
    189 
    190 ```
    191 #include <bits/stdc++.h>
    192 
    193 using namespace std;
    194 
    195 const long long INF64 = 1e18;
    196 
    197 int main() {
    198 #ifdef _DEBUG
    199 	freopen("input.txt", "r", stdin);
    200 //	freopen("output.txt", "w", stdout);
    201 #endif
    202 	
    203 	int q;
    204 	cin >> q;
    205 	for (int i = 0; i < q; ++i) {
    206 		long long n;
    207 		cin >> n;
    208 		vector<int> vals;
    209 		int pos2 = -1;
    210 		while (n > 0) {
    211 			vals.push_back(n % 3);
    212 			if (vals.back() == 2) pos2 = int(vals.size()) - 1;
    213 			n /= 3;
    214 		}
    215 		vals.push_back(0);
    216 		if (pos2 != -1) {
    217 			int pos0 = find(vals.begin() + pos2, vals.end(), 0) - vals.begin();
    218 			vals[pos0] = 1;
    219 			for (int i = pos0 - 1; i >= 0; --i) {
    220 				vals[i] = 0;
    221 			}
    222 		}
    223 		long long ans = 0;
    224 		long long pw = 1;
    225 		for (int i = 0; i < int(vals.size()); ++i) {
    226 			ans += pw * vals[i];
    227 			pw *= 3;
    228 		}
    229 		if (vals.back() == 1) ans = pw / 3;
    230 		cout << ans << endl;
    231 	}
    232 	
    233 	return 0;
    234 }
    235 ```
    236 
    237 [1249D1 - Too Many Segments (easy version)](/contest/1249/problem/D1 "Codeforces Round 595 (Div. 3)")
    238 
    239 **Tutorial**
    240 
    241 Tutorial is loading...
    242 
    243 **Solution**
    244 
    245 ```
    246 #include <bits/stdc++.h>
    247 
    248 using namespace std;
    249 
    250 const int N = 250;
    251 
    252 int main() {
    253 #ifdef _DEBUG
    254 	freopen("input.txt", "r", stdin);
    255 //	freopen("output.txt", "w", stdout);
    256 #endif
    257 	
    258 	int n, k;
    259 	cin >> n >> k;
    260 	vector<pair<int, int>> segs(n);
    261 	vector<int> cnt(N);
    262 	for (int i = 0; i < n; ++i) {
    263 		cin >> segs[i].first >> segs[i].second;
    264 		++cnt[segs[i].first];
    265 		--cnt[segs[i].second + 1];
    266 	}
    267 	
    268 	for (int i = 0; i + 1 < N; ++i) {
    269 		cnt[i + 1] += cnt[i];
    270 	}
    271 	
    272 	vector<int> ans(n);
    273 	for (int i = 0; i < N; ++i) {
    274 		while (cnt[i] > k) {
    275 			int pos = -1;
    276 			for (int p = 0; p < n; ++p) {
    277 				if (!ans[p] && (segs[p].first <= i && i <= segs[p].second) && (pos == -1 || segs[p].second > segs[pos].second)) {
    278 					pos = p;
    279 				}
    280 			}
    281 			assert(pos != -1);
    282 			for (int j = segs[pos].first; j <= segs[pos].second; ++j) {
    283 				--cnt[j];
    284 			}
    285 			ans[pos] = 1;
    286 		}
    287 	}
    288 	
    289 	cout << accumulate(ans.begin(), ans.end(), 0) << endl;
    290 	for (int i = 0; i < n; ++i) {
    291 		if (ans[i]) cout << i + 1 << " ";
    292 	}
    293 	cout << endl;
    294 	
    295 	return 0;
    296 }
    297 ```
    298 
    299 [1249D2 - Too Many Segments (hard version)](/contest/1249/problem/D2 "Codeforces Round 595 (Div. 3)")
    300 
    301 **Tutorial**
    302 
    303 Tutorial is loading...
    304 
    305 **Solution**
    306 
    307 ```
    308 #include <bits/stdc++.h>
    309 
    310 using namespace std;
    311 
    312 const int N = 200200;
    313 
    314 int main() {
    315 #ifdef _DEBUG
    316 	freopen("input.txt", "r", stdin);
    317 //	freopen("output.txt", "w", stdout);
    318 #endif
    319 	
    320 	int n, k;
    321 	cin >> n >> k;
    322 	vector<pair<int, int>> segs(n);
    323 	vector<int> cnt(N);
    324 	vector<vector<int>> ev(N);
    325 	for (int i = 0; i < n; ++i) {
    326 		cin >> segs[i].first >> segs[i].second;
    327 		++cnt[segs[i].first];
    328 		--cnt[segs[i].second + 1];
    329 		ev[segs[i].first].push_back(i + 1);
    330 		ev[segs[i].second + 1].push_back(-i - 1);
    331 	}
    332 	
    333 	for (int i = 0; i + 1 < N; ++i) {
    334 		cnt[i + 1] += cnt[i];
    335 	}
    336 	
    337 	vector<int> ans(n), sub(N);
    338 	set<pair<int, int>> curSegs;
    339 	int curSub = 0;																																				
    340 	for (int i = 0; i < N; ++i) {
    341 		curSub += sub[i];
    342 		for (auto it : ev[i]) {
    343 			if (it > 0) {
    344 				curSegs.insert(make_pair(segs[it - 1].second, it - 1));
    345 			} else {
    346 				auto iter = curSegs.find(make_pair(segs[-it - 1].second, -it - 1));
    347 				if (iter != curSegs.end()) curSegs.erase(iter);
    348 			}
    349 		}
    350 		while (cnt[i] - curSub > k) {
    351 			assert(!curSegs.empty());
    352 			int pos = curSegs.rbegin()->second;
    353 			curSegs.erase(prev(curSegs.end()));
    354 			++curSub;
    355 			--sub[segs[pos].second + 1];
    356 			ans[pos] = 1;
    357 		}
    358 	}
    359 	
    360 	cout << accumulate(ans.begin(), ans.end(), 0) << endl;
    361 	for (int i = 0; i < n; ++i) {
    362 		if (ans[i]) cout << i + 1 << " ";
    363 	}
    364 	cout << endl;
    365 	
    366 	return 0;
    367 }
    368 ```
    369 
    370 [1249E - By Elevator or Stairs?](/contest/1249/problem/E "Codeforces Round 595 (Div. 3)")
    371 
    372 **Tutorial**
    373 
    374 Tutorial is loading...
    375 
    376 **Solution**
    377 
    378 ```
    379 #include <bits/stdc++.h>
    380 
    381 using namespace std;
    382 
    383 const int INF = 1e9;
    384 
    385 int main() {
    386 #ifdef _DEBUG
    387 	freopen("input.txt", "r", stdin);
    388 //	freopen("output.txt", "w", stdout);
    389 #endif
    390 	
    391 	int n, c;
    392 	cin >> n >> c;
    393 	vector<int> a(n - 1), b(n - 1);
    394 	for (int i = 0; i < n - 1; ++i) {
    395 		cin >> a[i];
    396 	}
    397 	for (int i = 0; i < n - 1; ++i) {
    398 		cin >> b[i];
    399 	}
    400 	vector<vector<int>> dp(n, vector<int>(2, INF));
    401 	dp[0][0] = 0, dp[0][1] = c;
    402 	for (int i = 0; i < n - 1; ++i) {
    403 		dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + a[i]);
    404 		dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + a[i]);
    405 		dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + b[i]);
    406 		dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + b[i] + c);
    407 	}
    408 	
    409 	for (int i = 0; i < n; ++i) {
    410 		cout << min(dp[i][0], dp[i][1]) << " ";
    411 	}
    412 	cout << endl;
    413 	
    414 	return 0;
    415 }
    416 ```
    417 
    418 [1249F - Maximum Weight Subset](/contest/1249/problem/F "Codeforces Round 595 (Div. 3)")
    419 
    420 Thanks to [neal](/profile/neal "International Grandmaster neal") for the [additional editorial](https://codeforces.com/blog/entry/70822) of this problem and providing the linear solution!
    421 
    422 **Tutorial**
    423 
    424 Tutorial is loading...
    425 
    426 **Solution (Vovuh, n^3)**
    427 
    428 ```
    429 #include <bits/stdc++.h>
    430 
    431 using namespace std;
    432 
    433 const int N = 210;
    434 
    435 int n, k;
    436 vector<int> a;
    437 vector<vector<int>> g, dp;
    438 
    439 void dfs(int v, int p) {
    440 	dp[v][0] = a[v];
    441 	for (auto to : g[v]) {
    442 		if (to != p) dfs(to, v);
    443 	}
    444 	for (int dep = 0; dep < N; ++dep) {
    445 		if (dep == 0) {
    446 			for (auto to : g[v]) {
    447 				if (to == p) continue;
    448 				dp[v][dep] += dp[to][max(0, k - dep - 1)];
    449 			}
    450 		} else {
    451 			for (auto to : g[v]) {
    452 				if (to == p) continue;
    453 				int cur = dp[to][dep - 1];
    454 				for (auto other : g[v]) {
    455 					if (other == p || other == to) continue;
    456 					cur += dp[other][max(dep - 1, k - dep - 1)];
    457 				}
    458 				dp[v][dep] = max(dp[v][dep], cur);
    459 			}
    460 		}
    461 	}
    462 	for (int dep = N - 1; dep > 0; --dep) {
    463 		dp[v][dep - 1] = max(dp[v][dep - 1], dp[v][dep]);
    464 	}
    465 }
    466 
    467 int main() {
    468 #ifdef _DEBUG
    469 	freopen("input.txt", "r", stdin);
    470 //	freopen("output.txt", "w", stdout);
    471 #endif
    472 	
    473 	cin >> n >> k;
    474 	++k;
    475 	a = vector<int>(n);
    476 	for (int i = 0; i < n; ++i) {
    477 		cin >> a[i];
    478 	}
    479 	g = vector<vector<int>>(n);
    480 	for (int i = 0; i < n - 1; ++i) {
    481 		int x, y;
    482 		cin >> x >> y;
    483 		--x, --y;
    484 		g[x].push_back(y);
    485 		g[y].push_back(x);
    486 	}
    487 	
    488 	dp = vector<vector<int>>(n, vector<int>(N));
    489 	dfs(0, -1);
    490 	cout << dp[0][0] << endl;
    491 	
    492 	return 0;
    493 }
    494 ```
    495 
    496 **Solution (PikMike, n^2)**
    497 
    498 ```
    499 #include <bits/stdc++.h>
    500 
    501 using namespace std;
    502 
    503 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    504 
    505 const int N = 200 + 13;
    506 const int INF = 1e9;
    507 
    508 int n, k;
    509 int a[N];
    510 vector<int> g[N];
    511 int dp[N][N];
    512 int d[N];
    513 int tmp[N];
    514 
    515 void dfs(int v, int p = -1){
    516 	d[v] = 1;
    517 	dp[v][0] = a[v];
    518 	for (auto u : g[v]) if (u != p){
    519 		dfs(u, v);
    520 		int nw = max(d[v], d[u] + 1);
    521 		forn(i, nw)
    522 			tmp[i] = -INF;
    523 		forn(i, d[v]) for (int j = max(0, k - i); j < d[u]; ++j)
    524 			tmp[min(i, j + 1)] = max(tmp[min(i, j + 1)], dp[v][i] + dp[u][j]);
    525 		forn(i, d[u])
    526 			tmp[i + 1] = max(tmp[i + 1], dp[u][i]);
    527 		forn(i, d[v])
    528 			dp[v][i] = max(dp[v][i], tmp[i]);
    529 		for (int i = d[v]; i < nw; ++i)
    530 			dp[v][i] = tmp[i];
    531 		d[v] = nw;
    532 		for (int i = d[v] - 1; i > 0; --i)
    533 			dp[v][i - 1] = max(dp[v][i - 1], dp[v][i]);
    534 	}
    535 }
    536 
    537 int main(){
    538 	scanf("%d%d", &n, &k);
    539 	forn(i, n)
    540 		scanf("%d", &a[i]);
    541 	forn(i, n - 1){
    542 		int v, u;
    543 		scanf("%d%d", &v, &u);
    544 		--v, --u;
    545 		g[v].push_back(u);
    546 		g[u].push_back(v);
    547 	}
    548 	dfs(0);
    549 	printf("%d\n", dp[0][0]);
    550 }
    551 ```