Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int h1, m1;
scanf("%d:%d", &h1, &m1);
int h2, m2;
scanf("%d:%d", &h2, &m2);
int t1 = h1 * 60 + m1;
int t2 = h2 * 60 + m2;
int t3 = (t1 + t2) / 2;
printf("%02d:%02d\n", t3 / 60, t3 % 60);
return 0;
}
1133B - Preparation for International Women's Day
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
cin >> n >> k;
vector<int> cnt(k);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
++cnt[x % k];
}
int ans = cnt[0] / 2;
if (k % 2 == 0) ans += cnt[k / 2] / 2;
for (int i = 1; i < (k + 1) / 2; ++i) {
int j = k - i;
ans += min(cnt[i], cnt[j]);
}
cout << ans * 2 << endl;
return 0;
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
int ans = 0;
int j = 0;
for (int i = 0; i < n; ++i) {
while (j < n && a[j] - a[i] <= 5) {
++j;
ans = max(ans, j - i);
}
}
cout << ans << endl;
return 0;
}
1133D - Zero Quantity Maximization
Идея: BledDest
Разбор
Tutorial is loading...
Решение
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 200043;
void norm(pair<int, int>& p)
{
if(p.x < 0)
{
p.x *= -1;
p.y *= -1;
}
else if (p.x == 0 && p.y < 0)
{
p.y *= -1;
}
int d = __gcd(abs(p.x), abs(p.y));
p.x /= d;
p.y /= d;
}
map<pair<int, int>, int> m;
int a[N];
int b[N];
int n;
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
for(int i = 0; i < n; i++)
scanf("%d", &b[i]);
int ans = 0;
int cnt0 = 0;
for(int i = 0; i < n; i++)
{
if(a[i] == 0)
{
if(b[i] == 0)
cnt0++;
}
else
{
pair<int, int> p = make_pair(-b[i], a[i]);
norm(p);
m[p]++;
ans = max(ans, m[p]);
}
}
cout << cnt0 + ans << endl;
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
vector<int> cnt(n);
for (int i = 0; i < n; ++i) {
while (i + cnt[i] < n && a[i + cnt[i]] - a[i] <= 5) {
++cnt[i];
}
}
vector<vector<int>> dp(n + 1, vector<int>(k + 1));
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= k; ++j) {
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
if (j + 1 <= k) {
dp[i + cnt[i]][j + 1] = max(dp[i + cnt[i]][j + 1], dp[i][j] + cnt[i]);
}
}
}
cout << dp[n][k] << endl;
return 0;
}
1133F1 - Spanning Tree with Maximum Degree
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> g;
vector<int> deg, used;
vector<pair<int, int>> ans;
mt19937 rnd(time(NULL));
void bfs(int s) {
used = vector<int>(n);
used[s] = 1;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto to : g[v]) {
if (used[to]) continue;
if (rnd() & 1) ans.push_back(make_pair(v, to));
else ans.push_back(make_pair(to, v));
used[to] = 1;
q.push(to);
}
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> m;
g = vector<vector<int>>(n);
deg = vector<int>(n);
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
g[y].push_back(x);
++deg[x];
++deg[y];
}
int pos = 0;
for (int i = 0; i < n; ++i) {
if (deg[pos] < deg[i]) {
pos = i;
}
}
bfs(pos);
shuffle(ans.begin(), ans.end(), rnd);
for (auto it : ans) cout << it.first + 1 << " " << it.second + 1 << endl;
return 0;
}
1133F2 - Spanning Tree with One Fixed Degree
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int n, m, D;
vector<vector<int>> g;
int cnt;
vector<int> p, color;
vector<pair<int, int>> ans;
mt19937 rnd(time(NULL));
void bfs(int s, int bad) {
queue<int> q;
q.push(s);
color[s] = cnt;
while (!q.empty()) {
int v = q.front();
q.pop();
if (p[v] != -1) {
if (rnd() & 1) ans.push_back(make_pair(p[v], v));
else ans.push_back(make_pair(v, p[v]));
}
for (auto to : g[v]) {
if (to == bad || color[to] != -1) continue;
p[to] = v;
color[to] = cnt;
q.push(to);
}
}
++cnt;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> m >> D;
g = vector<vector<int>>(n);
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
g[y].push_back(x);
}
p = color = vector<int>(n, -1);
cnt = 0;
for (int i = 1; i < n; ++i) {
if (color[i] == -1) {
bfs(i, 0);
}
}
if (cnt > D || D > int(g[0].size())) {
cout << "NO" << endl;
return 0;
}
sort(g[0].begin(), g[0].end(), [](int a, int b) {
return color[a] < color[b];
});
for (int i = 0; i < int(g[0].size()); ++i) {
if (i == 0 || color[g[0][i]] != color[g[0][i - 1]]) {
ans.push_back(make_pair(0, g[0][i]));
}
}
D -= cnt;
for (int i = 1; i < int(g[0].size()); ++i) {
if (D == 0) break;
if (color[g[0][i]] == color[g[0][i - 1]]) {
ans.push_back(make_pair(0, g[0][i]));
--D;
}
}
g = vector<vector<int>>(n);
for (auto it : ans) {
g[it.first].push_back(it.second);
g[it.second].push_back(it.first);
}
ans.clear();
p = color = vector<int>(n, -1);
cnt = 0;
bfs(0, -1);
shuffle(ans.begin(), ans.end(), rnd);
cout << "YES" << endl;
for (auto it : ans) {
cout << it.first + 1 << " " << it.second + 1 << endl;
}
return 0;
}