codeforces-scrape

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

1133.md (7289B)


      1 Source: https://codeforces.com/blog/entry/65807
      2 
      3 [1133A - Middle of the Contest](/contest/1133/problem/A "Codeforces Round 544 (Div. 3)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      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 h1, m1;
     25 	scanf("%d:%d", &h1, &m1);
     26 	int h2, m2;
     27 	scanf("%d:%d", &h2, &m2);
     28 	int t1 = h1 * 60 + m1;
     29 	int t2 = h2 * 60 + m2;
     30 	int t3 = (t1 + t2) / 2;
     31 	printf("%02d:%02d\n", t3 / 60, t3 % 60);
     32 	
     33 	return 0;
     34 }
     35 ```
     36 
     37 [1133B - Preparation for International Women's Day](/contest/1133/problem/B "Codeforces Round 544 (Div. 3)")
     38 
     39 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     40 
     41 **Tutorial**
     42 
     43 Tutorial is loading...
     44 
     45 **Solution**
     46 
     47 ```
     48 #include <bits/stdc++.h>
     49 
     50 using namespace std;
     51 
     52 int main() {
     53 #ifdef _DEBUG
     54 	freopen("input.txt", "r", stdin);
     55 //	freopen("output.txt", "w", stdout);
     56 #endif
     57 	
     58 	int n, k;
     59 	cin >> n >> k;
     60 	vector<int> cnt(k);
     61 	for (int i = 0; i < n; ++i) {
     62 		int x;
     63 		cin >> x;
     64 		++cnt[x % k];
     65 	}
     66 	int ans = cnt[0] / 2;
     67 	if (k % 2 == 0) ans += cnt[k / 2] / 2;
     68 	for (int i = 1; i < (k + 1) / 2; ++i) {
     69 		int j = k - i;
     70 		ans += min(cnt[i], cnt[j]);
     71 	}
     72 	
     73 	cout << ans * 2 << endl;
     74 	
     75 	return 0;
     76 }
     77 ```
     78 
     79 [1133C - Balanced Team](/contest/1133/problem/C "Codeforces Round 544 (Div. 3)")
     80 
     81 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     82 
     83 **Tutorial**
     84 
     85 Tutorial is loading...
     86 
     87 **Solution**
     88 
     89 ```
     90 #include <bits/stdc++.h>
     91 
     92 using namespace std;
     93 
     94 int main() {
     95 #ifdef _DEBUG
     96 	freopen("input.txt", "r", stdin);
     97 //	freopen("output.txt", "w", stdout);
     98 #endif
     99 	
    100 	int n;
    101 	cin >> n;
    102 	vector<int> a(n);
    103 	for (int i = 0; i < n; ++i) {
    104 		cin >> a[i];
    105 	}
    106 	sort(a.begin(), a.end());
    107 	int ans = 0;
    108 	int j = 0;
    109 	for (int i = 0; i < n; ++i) {
    110 		while (j < n && a[j] - a[i] <= 5) {
    111 			++j;
    112 			ans = max(ans, j - i);
    113 		}
    114 	}
    115 	
    116 	cout << ans << endl;
    117 	
    118 	return 0;
    119 }
    120 ```
    121 
    122 [1133D - Zero Quantity Maximization](/contest/1133/problem/D "Codeforces Round 544 (Div. 3)")
    123 
    124 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest")
    125 
    126 **Tutorial**
    127 
    128 Tutorial is loading...
    129 
    130 **Solution**
    131 
    132 ```
    133 #include<bits/stdc++.h>
    134 
    135 using namespace std;
    136 
    137 #define x first
    138 #define y second
    139 
    140 const int N = 200043;
    141 
    142 void norm(pair<int, int>& p)
    143 {
    144 	if(p.x < 0)
    145 	{
    146 		p.x *= -1;
    147 		p.y *= -1;
    148 	}
    149 	else if (p.x == 0 && p.y < 0)
    150 	{
    151 		p.y *= -1;
    152 	}
    153 	int d = __gcd(abs(p.x), abs(p.y));
    154 	p.x /= d;
    155 	p.y /= d;
    156 }
    157 
    158 map<pair<int, int>, int> m;
    159 
    160 int a[N];
    161 int b[N];
    162 int n;
    163 
    164 int main()
    165 {
    166 	scanf("%d", &n);
    167 	for(int i = 0; i < n; i++)
    168 		scanf("%d", &a[i]);
    169 	for(int i = 0; i < n; i++)
    170 		scanf("%d", &b[i]);
    171 	int ans = 0;
    172 	int cnt0 = 0;
    173 	for(int i = 0; i < n; i++)
    174 	{
    175 		if(a[i] == 0)
    176 		{
    177 			if(b[i] == 0)
    178 				cnt0++;
    179 		}
    180 		else
    181 		{
    182 			pair<int, int> p = make_pair(-b[i], a[i]);
    183 			norm(p);
    184 			m[p]++;
    185 			ans = max(ans, m[p]);
    186 		}
    187 	}
    188 	cout << cnt0 + ans << endl;
    189 }
    190 ```
    191 
    192 [1133E - K Balanced Teams](/contest/1133/problem/E "Codeforces Round 544 (Div. 3)")
    193 
    194 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    195 
    196 **Tutorial**
    197 
    198 Tutorial is loading...
    199 
    200 **Solution**
    201 
    202 ```
    203 #include <bits/stdc++.h>
    204 
    205 using namespace std;
    206 
    207 int main() {
    208 #ifdef _DEBUG
    209 	freopen("input.txt", "r", stdin);
    210 //	freopen("output.txt", "w", stdout);
    211 #endif
    212 	
    213 	int n, k;
    214 	cin >> n >> k;
    215 	vector<int> a(n);
    216 	for (int i = 0; i < n; ++i) {
    217 		cin >> a[i];
    218 	}
    219 	sort(a.begin(), a.end());
    220 	vector<int> cnt(n);
    221 	for (int i = 0; i < n; ++i) {
    222 		while (i + cnt[i] < n && a[i + cnt[i]] - a[i] <= 5) {
    223 			++cnt[i];
    224 		}
    225 	}
    226 	
    227 	vector<vector<int>> dp(n + 1, vector<int>(k + 1));
    228 	for (int i = 0; i < n; ++i) {
    229 		for (int j = 0; j <= k; ++j) {
    230 			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
    231 			if (j + 1 <= k) {
    232 				dp[i + cnt[i]][j + 1] = max(dp[i + cnt[i]][j + 1], dp[i][j] + cnt[i]);
    233 			}
    234 		}
    235 	}
    236 	
    237 	cout << dp[n][k] << endl;
    238 	
    239 	return 0;
    240 }
    241 ```
    242 
    243 [1133F1 - Spanning Tree with Maximum Degree](/contest/1133/problem/F1 "Codeforces Round 544 (Div. 3)")
    244 
    245 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    246 
    247 **Tutorial**
    248 
    249 Tutorial is loading...
    250 
    251 **Solution**
    252 
    253 ```
    254 #include <bits/stdc++.h>
    255 
    256 using namespace std;
    257 
    258 int n, m;
    259 vector<vector<int>> g;
    260 vector<int> deg, used;
    261 vector<pair<int, int>> ans;
    262 
    263 mt19937 rnd(time(NULL));
    264 
    265 void bfs(int s) {
    266 	used = vector<int>(n);
    267 	used[s] = 1;
    268 	queue<int> q;
    269 	q.push(s);
    270 	
    271 	while (!q.empty()) {
    272 		int v = q.front();
    273 		q.pop();
    274 		for (auto to : g[v]) {
    275 			if (used[to]) continue;
    276 			if (rnd() & 1) ans.push_back(make_pair(v, to));
    277 			else ans.push_back(make_pair(to, v));
    278 			used[to] = 1;
    279 			q.push(to);
    280 		}
    281 	}
    282 }
    283 
    284 int main() {
    285 #ifdef _DEBUG
    286 	freopen("input.txt", "r", stdin);
    287 //	freopen("output.txt", "w", stdout);
    288 #endif
    289 	
    290 	cin >> n >> m;
    291 	g = vector<vector<int>>(n);
    292 	deg = vector<int>(n);
    293 	for (int i = 0; i < m; ++i) {
    294 		int x, y;
    295 		cin >> x >> y;
    296 		--x, --y;
    297 		g[x].push_back(y);
    298 		g[y].push_back(x);
    299 		++deg[x];
    300 		++deg[y];
    301 	}
    302 	
    303 	int pos = 0;
    304 	for (int i = 0; i < n; ++i) {
    305 		if (deg[pos] < deg[i]) {
    306 			pos = i;
    307 		}
    308 	}
    309 	
    310 	bfs(pos);
    311 	shuffle(ans.begin(), ans.end(), rnd);
    312 	for (auto it : ans) cout << it.first + 1 << " " << it.second + 1 << endl;
    313 	
    314 	return 0;
    315 }
    316 ```
    317 
    318 [1133F2 - Spanning Tree with One Fixed Degree](/contest/1133/problem/F2 "Codeforces Round 544 (Div. 3)")
    319 
    320 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    321 
    322 **Tutorial**
    323 
    324 Tutorial is loading...
    325 
    326 **Solution**
    327 
    328 ```
    329 #include <bits/stdc++.h>
    330 
    331 using namespace std;
    332 
    333 int n, m, D;
    334 vector<vector<int>> g;
    335 
    336 int cnt;
    337 vector<int> p, color;
    338 vector<pair<int, int>> ans;
    339 
    340 mt19937 rnd(time(NULL));
    341 
    342 void bfs(int s, int bad) {
    343 	queue<int> q;
    344 	q.push(s);
    345 	color[s] = cnt;
    346 	while (!q.empty()) {
    347 		int v = q.front();
    348 		q.pop();
    349 		if (p[v] != -1) {
    350 			if (rnd() & 1) ans.push_back(make_pair(p[v], v));
    351 			else ans.push_back(make_pair(v, p[v]));
    352 		}
    353 		for (auto to : g[v]) {
    354 			if (to == bad || color[to] != -1) continue;
    355 			p[to] = v;
    356 			color[to] = cnt;
    357 			q.push(to);
    358 		}
    359 	}
    360 	++cnt;
    361 }
    362 
    363 int main() {
    364 #ifdef _DEBUG
    365 	freopen("input.txt", "r", stdin);
    366 //	freopen("output.txt", "w", stdout);
    367 #endif
    368 	
    369 	cin >> n >> m >> D;
    370 	g = vector<vector<int>>(n);
    371 	for (int i = 0; i < m; ++i) {
    372 		int x, y;
    373 		cin >> x >> y;
    374 		--x, --y;
    375 		g[x].push_back(y);
    376 		g[y].push_back(x);
    377 	}
    378 	
    379 	p = color = vector<int>(n, -1);
    380 	cnt = 0;
    381 	for (int i = 1; i < n; ++i) {
    382 		if (color[i] == -1) {
    383 			bfs(i, 0);
    384 		}
    385 	}
    386 	
    387 	if (cnt > D || D > int(g[0].size())) {
    388 		cout << "NO" << endl;
    389 		return 0;
    390 	}
    391 	
    392 	sort(g[0].begin(), g[0].end(), [](int a, int b) {
    393 		return color[a] < color[b];
    394 	});
    395 	
    396 	for (int i = 0; i < int(g[0].size()); ++i) {
    397 		if (i == 0 || color[g[0][i]] != color[g[0][i - 1]]) {
    398 			ans.push_back(make_pair(0, g[0][i]));
    399 		}
    400 	}
    401 	D -= cnt;
    402 	for (int i = 1; i < int(g[0].size()); ++i) {
    403 		if (D == 0) break;
    404 		if (color[g[0][i]] == color[g[0][i - 1]]) {
    405 			ans.push_back(make_pair(0, g[0][i]));
    406 			--D;
    407 		}
    408 	}
    409 	
    410 	g = vector<vector<int>>(n);
    411 	for (auto it : ans) {
    412 		g[it.first].push_back(it.second);
    413 		g[it.second].push_back(it.first);
    414 	}
    415 	ans.clear();
    416 	p = color = vector<int>(n, -1);
    417 	cnt = 0;
    418 	bfs(0, -1);
    419 	
    420 	shuffle(ans.begin(), ans.end(), rnd);
    421 	cout << "YES" << endl;
    422 	for (auto it : ans) {
    423 		cout << it.first + 1 << " " << it.second + 1 << endl;
    424 	}
    425 	
    426 	return 0;
    427 }
    428 ```