codeforces-scrape

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

1176.md (6738B)


      1 Source: https://codeforces.com/blog/entry/67598
      2 
      3 [1176A - Divide it!](/contest/1176/problem/A "Codeforces Round 565 (Div. 3)")
      4 
      5 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh")
      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 		long long n;
     28 		cin >> n;
     29 		int cnt2 = 0, cnt3 = 0, cnt5 = 0;
     30 		while (n % 2 == 0) {
     31 			n /= 2;
     32 			++cnt2;
     33 		}
     34 		while (n % 3 == 0) {
     35 			n /= 3;
     36 			++cnt3;
     37 		}
     38 		while (n % 5 == 0) {
     39 			n /= 5;
     40 			++cnt5;
     41 		}
     42 		if (n != 1) {
     43 			cout << -1 << endl;
     44 		} else {
     45 			cout << cnt2 + cnt3 * 2 + cnt5 * 3 << endl;
     46 		}
     47 	}
     48 	
     49 	return 0;
     50 }
     51 ```
     52 
     53 [1176B - Merge it!](/contest/1176/problem/B "Codeforces Round 565 (Div. 3)")
     54 
     55 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     56 
     57 **Tutorial**
     58 
     59 Tutorial is loading...
     60 
     61 **Solution**
     62 
     63 ```
     64 #include<bits/stdc++.h>
     65 
     66 using namespace std;
     67 
     68 int t, n;
     69 int cnt[3];
     70 
     71 int main(){
     72     cin >> t;
     73     for(int tc = 0; tc < t; ++tc){
     74         memset(cnt, 0, sizeof cnt);
     75         cin >> n;
     76         for(int i = 0; i < n; ++i){
     77             int x;
     78             cin >> x;
     79             ++cnt[x % 3];
     80         }
     81     	
     82     	int res = cnt[0];
     83         int mn = min(cnt[1], cnt[2]);
     84         res += mn;
     85         cnt[1] -= mn, cnt[2] -= mn;
     86         res += (cnt[1] + cnt[2]) / 3;
     87         cout << res << endl;
     88     }
     89     return 0;
     90 }
     91 ```
     92 
     93 [1176C - Lose it!](/contest/1176/problem/C "Codeforces Round 565 (Div. 3)")
     94 
     95 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh")
     96 
     97 **Tutorial**
     98 
     99 Tutorial is loading...
    100 
    101 **Solution**
    102 
    103 ```
    104 #include <bits/stdc++.h>
    105 
    106 using namespace std;
    107 
    108 int main() {
    109 #ifdef _DEBUG
    110 	freopen("input.txt", "r", stdin);
    111 //	freopen("output.txt", "w", stdout);
    112 #endif
    113 	
    114 	vector<int> p({4, 8, 15, 16, 23, 42});
    115 
    116 	int n;
    117 	cin >> n;
    118 	vector<int> a(n);
    119 	for (int i = 0; i < n; ++i) {
    120 		cin >> a[i];
    121 		a[i] = lower_bound(p.begin(), p.end(), a[i]) - p.begin();
    122 	}
    123 	
    124 	vector<int> seq(6);
    125 	for (int i = 0; i < n; ++i) {
    126 		if (a[i] == 0) {
    127 			++seq[0];
    128 		} else {
    129 			if (seq[a[i] - 1] > 0) {
    130 				--seq[a[i] - 1];
    131 				++seq[a[i]];
    132 			}
    133 		}
    134 	}
    135 	
    136 	cout << n - seq[5] * 6 << endl;
    137 	
    138 	return 0;
    139 }
    140 ```
    141 
    142 [1176D - Recover it!](/contest/1176/problem/D "Codeforces Round 565 (Div. 3)")
    143 
    144 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    145 
    146 **Tutorial**
    147 
    148 Tutorial is loading...
    149 
    150 **Solution**
    151 
    152 ```
    153 #include <bits/stdc++.h>
    154 
    155 #define forn(i, n) for (int i = 0; i < int(n); i++)
    156 
    157 using namespace std;
    158 
    159 const int N = 3 * 1000 * 1000 + 13;
    160 
    161 int lst[N];
    162 int num[N];
    163 
    164 void sieve(){
    165 	forn(i, N) lst[i] = i;
    166 	for (int i = 2; i < N; ++i){
    167 		if (lst[i] != i){
    168 			lst[i] = i / lst[i];
    169 			continue;
    170 		}
    171 		for (long long j = i * 1ll * i; j < N; j += i)
    172 			lst[j] = min(lst[j], i);
    173 	}
    174 	int cur = 0;
    175 	for (int i = 2; i < N; ++i) if (lst[i] == i)
    176 		num[i] = ++cur;
    177 }
    178 
    179 int cnt[N];
    180 
    181 int main() {
    182 	int n;
    183 	scanf("%d", &n);
    184 	forn(i, 2 * n){
    185 		int x;
    186 		scanf("%d", &x);
    187 		++cnt[x];
    188 	}
    189 	
    190 	sieve();
    191 	
    192 	vector<int> res;
    193 	for (int i = N - 1; i >= 0; --i){
    194 		while (cnt[i] > 0){
    195 			if (lst[i] == i){
    196 				--cnt[num[i]];
    197 				res.push_back(num[i]);
    198 			}
    199 			else{
    200 				--cnt[lst[i]];
    201 				res.push_back(i);
    202 			}
    203 			--cnt[i];
    204 		}
    205 	}
    206 	
    207 	for (auto it : res)
    208 		printf("%d ", it);
    209 	return 0;
    210 }
    211 ```
    212 
    213 [1176E - Cover it!](/contest/1176/problem/E "Codeforces Round 565 (Div. 3)")
    214 
    215 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    216 
    217 **Tutorial**
    218 
    219 Tutorial is loading...
    220 
    221 **Solution**
    222 
    223 ```
    224 #include <bits/stdc++.h>
    225 
    226 using namespace std;
    227 
    228 const int INF = 1e9;
    229 
    230 int n, m;
    231 vector<int> d;
    232 vector<vector<int>> g;
    233 
    234 void bfs(int s) {
    235 	d = vector<int>(n, INF);
    236 	d[s] = 0;
    237 	
    238 	queue<int> q;
    239 	q.push(s);
    240 	
    241 	while (!q.empty()) {
    242 		int v = q.front();
    243 		q.pop();
    244 		
    245 		for (auto to : g[v]) {
    246 			if (d[to] == INF) {
    247 				d[to] = d[v] + 1;
    248 				q.push(to);
    249 			}
    250 		}
    251 	}
    252 }
    253 
    254 int main() {
    255 #ifdef _DEBUG
    256 	freopen("input.txt", "r", stdin);
    257 //	freopen("output.txt", "w", stdout);
    258 #endif
    259 	
    260 	int t;
    261 	cin >> t;
    262 	
    263 	for (int tc = 0; tc < t; ++tc){
    264 		cin >> n >> m;
    265 		g = vector<vector<int>>(n);
    266 		for (int i = 0; i < m; ++i) {
    267 			int x, y;
    268 			cin >> x >> y;
    269 			--x, --y;
    270 			g[x].push_back(y);
    271 			g[y].push_back(x);
    272 		}
    273 	
    274 		bfs(0);
    275 		vector<int> even, odd;
    276 		for (int i = 0; i < n; ++i) {
    277 			if (d[i] & 1) odd.push_back(i);
    278 			else even.push_back(i);
    279 		}
    280 	
    281 		if (even.size() < odd.size()) {
    282 			cout << even.size() << endl;
    283 			for (auto v : even) cout << v + 1 << " ";
    284 		} else {
    285 			cout << odd.size() << endl;
    286 			for (auto v : odd) cout << v + 1 << " ";
    287 		}
    288 		cout << endl;
    289 	}
    290 	
    291 	return 0;
    292 }
    293 ```
    294 
    295 [1176F - Destroy it!](/contest/1176/problem/F "Codeforces Round 565 (Div. 3)")
    296 
    297 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest")
    298 
    299 **Tutorial**
    300 
    301 Tutorial is loading...
    302 
    303 **Solution**
    304 
    305 ```
    306 #define _CRT_SECURE_NO_WARNINGS
    307 
    308 #include<iostream>
    309 #include<cstdio>
    310 #include<vector>
    311 #include<algorithm>
    312 
    313 using namespace std;
    314 
    315 typedef long long li;
    316 
    317 const li INF64 = li(1e18);
    318 
    319 const int N = 200043;
    320 vector<int> cards[N][4];
    321 li dp[N][10];
    322 int n;
    323 li dp2[4][2];
    324 
    325 int main()
    326 {
    327 #ifdef _DEBUG
    328 	freopen("input.txt", "r", stdin);
    329 	freopen("output.txt", "w", stdout);
    330 #endif
    331 	for(int i = 0; i < N; i++)
    332 		for(int j = 0; j < 10; j++)
    333 			dp[i][j] = -INF64;
    334 	dp[0][0] = 0;
    335 	scanf("%d", &n);
    336 	for (int i = 0; i < n; i++)
    337 	{
    338 		int k;
    339 		scanf("%d", &k);
    340 		for (int j = 0; j < k; j++)
    341 		{
    342 			int c, d;
    343 			scanf("%d %d", &c, &d);
    344 			cards[i][c].push_back(d);
    345 		}
    346 	}
    347 	for (int i = 0; i < n; i++)
    348 	{
    349 		for (int j = 1; j <= 3; j++)
    350 		{
    351 			int s = (j == 1 ? 3 : 1);
    352 			sort(cards[i][j].begin(), cards[i][j].end());
    353 			reverse(cards[i][j].begin(), cards[i][j].end());
    354 			while (cards[i][j].size() > s)
    355 				cards[i][j].pop_back();
    356 		}
    357 	}
    358 	for (int i = 0; i < n; i++)
    359 	{
    360 		for (int j = 0; j < 4; j++)
    361 			for (int k = 0; k < 2; k++)
    362 				dp2[j][k] = -INF64;
    363 		dp2[0][0] = 0;
    364 		vector<pair<int, int> > cur;
    365 		for (int j = 1; j <= 3; j++)
    366 			for (auto x : cards[i][j])
    367 				cur.push_back(make_pair(j, x));
    368 		sort(cur.begin(), cur.end());
    369 		do
    370 		{
    371 			int mana = 3;
    372 			li score = 0;
    373 			li mx = 0;
    374 			int cnt = 0;
    375 			for (auto x : cur)
    376 			{
    377 				cnt++;
    378 				if (mana < x.first)
    379 					break;
    380 				mana -= x.first;
    381 				mx = max(mx, li(x.second));
    382 				score += x.second;
    383 				dp2[cnt][0] = max(dp2[cnt][0], score);
    384 				dp2[cnt][1] = max(dp2[cnt][1], score + mx);
    385 			}
    386 		} while (next_permutation(cur.begin(), cur.end()));
    387 		for(int j = 0; j < 10; j++)
    388 			for (int k = 0; k <= 3; k++)
    389 			{
    390 				int nxt = (j + k) % 10;
    391 				int f = (j + k >= 10 ? 1 : 0);
    392 				dp[i + 1][nxt] = max(dp[i + 1][nxt], dp[i][j] + dp2[k][f]);
    393 			}
    394 	}
    395 	li ans = 0;
    396 	for (int i = 0; i <= 9; i++)
    397 		ans = max(ans, dp[n][i]);
    398 	printf("%lld\n", ans);
    399 	return 0;
    400 }
    401 ```