Все идеи, кроме задачи C, принадлежат MikeMirzayanov. Автор задачи C — Rox.
Отдельное спасибо _overrated_ за неоценимую помощь в подготовке раунда!
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int calc(int a, int b, int c) {
return abs(a - b) + abs(a - c) + abs(b - c);
}
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 a, b, c;
cin >> a >> b >> c;
int ans = calc(a, b, c);
for (int da = -1; da <= 1; ++da) {
for (int db = -1; db <= 1; ++db) {
for (int dc = -1; dc <= 1; ++dc) {
int na = a + da;
int nb = b + db;
int nc = c + dc;
ans = min(ans, calc(na, nb, nc));
}
}
}
cout << ans << endl;
}
return 0;
}
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
const string MOVES = "LRUD";
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) {
string s;
cin >> s;
map<char, int> cnt;
for (auto c : MOVES) cnt[c] = 0;
for (auto c : s) ++cnt[c];
int v = min(cnt['U'], cnt['D']);
int h = min(cnt['L'], cnt['R']);
if (min(v, h) == 0) {
if (v == 0) {
h = min(h, 1);
cout << 2 * h << endl << string(h, 'L') + string(h, 'R') << endl;
} else {
v = min(v, 1);
cout << 2 * v << endl << string(v, 'U') + string(v, 'D') << endl;
}
} else {
string res;
res += string(h, 'L');
res += string(v, 'U');
res += string(h, 'R');
res += string(v, 'D');
cout << res.size() << endl << res << endl;
}
}
return 0;
}
1272C - Yet Another Broken Keyboard
Разбор
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;
string s;
cin >> s;
set<char> st;
for (int i = 0; i < k; ++i) {
char c;
cin >> c;
st.insert(c);
}
long long ans = 0;
for (int i = 0; i < n; ++i) {
int j = i;
while (j < n && st.count(s[j])) ++j;
int len = j - i;
ans += len * 1ll * (len + 1) / 2;
i = j;
}
cout << ans << endl;
return 0;
}
Разбор
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];
}
int ans = 1;
vector<int> rg(n, 1);
for (int i = n - 2; i >= 0; --i) {
if (a[i + 1] > a[i]) rg[i] = rg[i + 1] + 1;
ans = max(ans, rg[i]);
}
vector<int> lf(n, 1);
for (int i = 1; i < n; ++i) {
if (a[i - 1] < a[i]) lf[i] = lf[i - 1] + 1;
ans = max(ans, lf[i]);
}
for (int i = 0; i < n - 2; ++i) {
if (a[i] < a[i + 2]) ans = max(ans, lf[i] + rg[i + 2]);
}
cout << ans << endl;
return 0;
}
1272E - Nearest Opposite Parity
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n;
vector<int> a;
vector<int> ans;
vector<vector<int>> g;
void bfs(const vector<int> &start, const vector<int> &end) {
vector<int> d(n, INF);
queue<int> q;
for (auto v : start) {
d[v] = 0;
q.push(v);
}
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto to : g[v]) {
if (d[to] == INF) {
d[to] = d[v] + 1;
q.push(to);
}
}
}
for (auto v : end) {
if (d[v] != INF) {
ans[v] = d[v];
}
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n;
a = vector<int>(n);
g = vector<vector<int>>(n);
vector<int> even, odd;
for (int i = 0; i < n; ++i) {
cin >> a[i];
if (a[i] & 1) odd.push_back(i);
else even.push_back(i);
}
for (int i = 0; i < n; ++i) {
int lf = i - a[i];
int rg = i + a[i];
if (0 <= lf) g[lf].push_back(i);
if (rg < n) g[rg].push_back(i);
}
ans = vector<int>(n, -1);
bfs(odd, even);
bfs(even, odd);
for (auto it : ans) cout << it << " ";
cout << endl;
return 0;
}
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
const int N = 202;
const int INF = 1e9;
int dp[N][N][2 * N];
pair<pair<int, int>, pair<int, char>> p[N][N][2 * N];
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int bal = 0; bal < 2 * N; ++bal) {
dp[i][j][bal] = INF;
}
}
}
dp[0][0][0] = 0;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int bal = 0; bal < 2 * N; ++bal) {
if (dp[i][j][bal] == INF) continue;
int nxti = i + (i < n && s[i] == '(');
int nxtj = j + (j < m && t[j] == '(');
if (bal + 1 < 2 * N && dp[nxti][nxtj][bal + 1] > dp[i][j][bal] + 1) {
dp[nxti][nxtj][bal + 1] = dp[i][j][bal] + 1;
p[nxti][nxtj][bal + 1] = make_pair(make_pair(i, j), make_pair(bal, '('));
}
nxti = i + (i < n && s[i] == ')');
nxtj = j + (j < m && t[j] == ')');
if (bal > 0 && dp[nxti][nxtj][bal - 1] > dp[i][j][bal] + 1) {
dp[nxti][nxtj][bal - 1] = dp[i][j][bal] + 1;
p[nxti][nxtj][bal - 1] = make_pair(make_pair(i, j), make_pair(bal, ')'));
}
}
}
}
int ci = n, cj = m, cbal = 0;
for (int bal = 0; bal < 2 * N; ++bal) {
if (dp[n][m][bal] + bal < dp[n][m][cbal] + cbal) {
cbal = bal;
}
}
string res = string(cbal, ')');
while (ci > 0 || cj > 0 || cbal != 0) {
int nci = p[ci][cj][cbal].first.first;
int ncj = p[ci][cj][cbal].first.second;
int ncbal = p[ci][cj][cbal].second.first;
res += p[ci][cj][cbal].second.second;
ci = nci;
cj = ncj;
cbal = ncbal;
}
reverse(res.begin(), res.end());
cout << res << endl;
return 0;
}