Я сильно сожалею, что задача D оказалась намного сложнее, чем я ожидал, и образовалась пропасть в сложности между задачами C и D. Надеюсь, в следующих раундах такого не повторится.
UPD: Хочу сказать отдельное спасибо kevinsogo за огромную помощь с разборами и с подготовкой раунда в целом.
Разбор
Tutorial is loading...
Решение (Vovuh)
#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];
int ans = 0;
while (!a.empty() && a.back() <= k) {
++ans;
a.pop_back();
}
reverse(a.begin(), a.end());
while (!a.empty() && a.back() <= k) {
++ans;
a.pop_back();
}
cout << ans << endl;
return 0;
}
999B - Переворотное шифрование
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
string s;
cin >> n >> s;
for (int i = 1; i <= n; ++i) {
if (n % i == 0) {
reverse(s.begin(), s.begin() + i);
}
}
cout << s << endl;
return 0;
}
Разбор
Tutorial is loading...
Решение 1 (Vovuh)
#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;
vector<int> cnt(26);
for (auto c : s) ++cnt[c - 'a'];
int pos = 26;
for (int i = 0; i < 26; ++i) {
if (k >= cnt[i]) {
k -= cnt[i];
} else {
pos = i;
break;
}
}
string ans;
int rem = k;
for (auto c : s) {
int cur = c - 'a';
if (cur > pos || (cur == pos && rem == 0)) {
ans += c;
} else if (cur == pos) {
--rem;
}
}
cout << ans << endl;
return 0;
}
Решение 2 (Vovuh)
#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;
vector<pair<char, int>> c(n);
for (int i = 0; i < n; ++i)
c[i] = make_pair(s[i], i);
sort(c.begin(), c.end());
sort(c.begin() + k, c.end(), [&] (const pair<char, int> &a, const pair<char, int> &b) {
return a.second < b.second;
});
for (int i = k; i < n; ++i)
cout << c[i].first;
cout << endl;
return 0;
}
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, m;
cin >> n >> m;
int k = n / m;
vector<int> a(n);
vector<vector<int>> val(m);
for (int i = 0; i < n; ++i) {
cin >> a[i];
val[a[i] % m].push_back(i);
}
long long ans = 0;
vector<pair<int, int>> fre;
for (int i = 0; i < 2 * m; ++i) {
int cur = i % m;
while (int(val[cur].size()) > k) {
int elem = val[cur].back();
val[cur].pop_back();
fre.push_back(make_pair(elem, i));
}
while (int(val[cur].size()) < k && !fre.empty()) {
int elem = fre.back().first;
int mmod = fre.back().second;
fre.pop_back();
val[cur].push_back(elem);
a[elem] += i - mmod;
ans += i - mmod;
}
}
cout << ans << endl;
for (int i = 0; i < n; ++i)
cout << a[i] << " ";
cout << endl;
return 0;
}
999E - Достижимость из столицы
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int n, m, s;
vector<int> g[N];
bool used[N];
bool ok[N];
int cnt;
void dfs1(int v) {
ok[v] = true;
for (auto to : g[v])
if (!ok[to])
dfs1(to);
}
void dfs2(int v) {
used[v] = true;
++cnt;
for (auto to : g[v])
if (!used[to] && !ok[to])
dfs2(to);
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> m >> s;
--s;
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
}
dfs1(s);
vector<pair<int, int>> val;
for (int i = 0; i < n; ++i) {
if (!ok[i]) {
cnt = 0;
memset(used, false, sizeof(used));
dfs2(i);
val.push_back(make_pair(cnt, i));
}
}
sort(val.begin(), val.end());
reverse(val.begin(), val.end());
int ans = 0;
for (auto it : val) {
if (!ok[it.second]) {
++ans;
dfs1(it.second);
}
}
cout << ans << endl;
return 0;
}
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
const int N = 520;
const int K = 12;
const int C = 100 * 1000 + 11;
int n, k;
int c[C];
int f[C];
vector<int> h;
int dp[N][K * N];
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> k;
h = vector<int>(k + 1);
for (int i = 0; i < n * k; ++i) {
int x;
cin >> x;
++c[x];
}
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
++f[x];
}
for (int i = 1; i <= k; ++i)
cin >> h[i];
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= n * k; ++j) {
for (int cur = 0; cur <= k; ++cur) {
dp[i + 1][j + cur] = max(dp[i + 1][j + cur], dp[i][j] + h[cur]);
}
}
}
int ans = 0;
for (int i = 0; i < C; ++i) {
if (f[i] != 0) ans += dp[f[i]][c[i]];
}
cout << ans << endl;
return 0;
}