Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
long long a, b, c;
cin >> a >> b >> c;
cout << (a + b + c) / 2 << endl;
}
return 0;
}
Idea: vovuh
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int n, k;
cin >> n >> k;
vector<int> a(n);
int cntodd = 0;
for (int j = 0; j < n; ++j) {
cin >> a[j];
cntodd += a[j] % 2;
}
if (cntodd < k || cntodd % 2 != k % 2) {
cout << "NO" << endl;
continue;
}
cout << "YES" << endl;
for (int j = 0; j < n; ++j) {
if (k == 1) break;
if (a[j] % 2 == 1) {
cout << j + 1 << " ";
--k;
}
}
cout << n << endl;
}
return 0;
}
Idea: MikeMirzayanov and vovuh
Tutorial
Tutorial is loading...
Solution
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXC = 1e5;
int main() {
int q;
cin >> q;
while (q--) {
int n;
cin >> n;
int mnx = -MAXC, mxx = MAXC;
int mny = -MAXC, mxy = MAXC;
while (n--) {
int x, y, f1, f2, f3, f4;
cin >> x >> y >> f1 >> f2 >> f3 >> f4;
if (!f1) mnx = max(mnx, x);
if (!f2) mxy = min(mxy, y);
if (!f3) mxx = min(mxx, x);
if (!f4) mny = max(mny, y);
}
if (mnx <= mxx && mny <= mxy)
cout << "1 " << mnx << " " << mny << "\n";
else
cout << "0\n";
}
return 0;
}
1196D1 - RGB Substring (easy version)
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
const string t = "RGB";
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int n, k;
string s;
cin >> n >> k >> s;
int ans = 1e9;
for (int j = 0; j < n - k + 1; ++j) {
for (int offset = 0; offset < 3; ++offset) {
int cur = 0;
for (int pos = 0; pos < k; ++pos) {
if (s[j + pos] != t[(pos + offset) % 3]) {
++cur;
}
}
ans = min(ans, cur);
}
}
cout << ans << endl;
}
return 0;
}
1196D2 - RGB Substring (hard version)
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
const string t = "RGB";
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int n, k;
string s;
cin >> n >> k >> s;
int ans = 1e9;
for (int offset = 0; offset < 3; ++offset) {
vector<int> res(n);
int cur = 0;
for (int j = 0; j < n; ++j) {
res[j] = (s[j] != t[(j + offset) % 3]);
cur += res[j];
if (j >= k) cur -= res[j - k];
if (j >= k - 1) ans = min(ans, cur);
}
}
cout << ans << endl;
}
return 0;
}
1196E - Connected Component on a Chessboard
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int b, w;
cin >> b >> w;
vector<pair<int, int>> res;
bool need = b < w;
if (need) swap(w, b);
int x = 2, y = 2;
while (w > 0) {
if ((x + y) % 2 == 1) {
res.push_back({x, y});
--b;
} else {
res.push_back({x, y});
--w;
}
++y;
}
int cx = 1, cy = 2;
while (b > 0 && cy <= y) {
res.push_back({cx, cy});
--b;
cy += 2;
}
cx = 3, cy = 2;
while (b > 0 && cy <= y) {
res.push_back({cx, cy});
--b;
cy += 2;
}
if (b > 0) {
res.push_back({2, 1});
--b;
}
if (b > 0) {
res.push_back({2, y});
--b;
}
if (b > 0) {
cout << "NO" << endl;
} else {
assert(w == 0);
cout << "YES" << endl;
for (auto it : res) cout << it.first << " " << it.second + need << endl;
}
}
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const long long INF64 = 1e18;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
vector<pair<int, pair<int, int>>> e;
for (int i = 0; i < m; ++i) {
int x, y, w;
scanf("%d %d %d", &x, &y, &w);
--x, --y;
e.push_back(make_pair(w, make_pair(x, y)));
}
sort(e.begin(), e.end());
vector<int> vert;
for (int i = 0; i < min(m, k); ++i) {
vert.push_back(e[i].second.first);
vert.push_back(e[i].second.second);
}
sort(vert.begin(), vert.end());
vert.resize(unique(vert.begin(), vert.end()) - vert.begin());
int cntv = vert.size();
vector<vector<long long>> dist(cntv, vector<long long>(cntv, INF64));
for (int i = 0; i < cntv; ++i) dist[i][i] = 0;
for (int i = 0; i < min(m, k); ++i) {
int x = lower_bound(vert.begin(), vert.end(), e[i].second.first) - vert.begin();
int y = lower_bound(vert.begin(), vert.end(), e[i].second.second) - vert.begin();
dist[x][y] = dist[y][x] = min(dist[x][y], (long long)e[i].first);
}
for (int z = 0; z < cntv; ++z) {
for (int x = 0; x < cntv; ++x) {
for (int y = 0; y < cntv; ++y) {
dist[x][y] = min(dist[x][y], dist[x][z] + dist[z][y]);
}
}
}
vector<long long> res;
for (int i = 0; i < cntv; ++i) {
for (int j = 0; j < i; ++j) {
res.push_back(dist[i][j]);
}
}
sort(res.begin(), res.end());
cout << res[k - 1] << endl;
return 0;
}