All ideas belong to MikeMirzayanov.
1249A - Очередное разделение на команды
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;
cin >> n;
vector<int> a(n);
for (int j = 0; j < n; ++j) {
cin >> a[j];
}
bool ok = true;
for (int p1 = 0; p1 < n; ++p1) {
for (int p2 = 0; p2 < p1; ++p2) {
ok &= abs(a[p1] - a[p2]) != 1;
}
}
cout << 2 - ok << endl;
}
return 0;
}
1249B1 - Обмен книгами (простая версия)
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;
cin >> n;
vector<int> p(n);
for (int j = 0; j < n; ++j) {
cin >> p[j];
--p[j];
}
for (int j = 0; j < n; ++j) {
int cnt = 0;
int k = j;
do {
++cnt;
k = p[k];
} while (k != j);
cout << cnt << " ";
}
cout << endl;
}
return 0;
}
1249B2 - Обмен книгами (сложная версия)
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;
cin >> n;
vector<int> p(n);
for (int j = 0; j < n; ++j) {
cin >> p[j];
--p[j];
}
vector<int> used(n);
vector<int> ans(n);
for (int j = 0; j < n; ++j) {
if (!used[j]) {
vector<int> cur;
while (!used[j]) {
cur.push_back(j);
used[j] = true;
j = p[j];
}
for (auto el : cur) ans[el] = cur.size();
}
}
for (int j = 0; j < n; ++j) cout << ans[j] << " ";
cout << endl;
}
return 0;
}
1249C1 - Хорошие числа (простая версия)
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;
cin >> n;
while (true) {
bool ok = true;
int cur = n;
while (cur > 0) {
if (ok && cur % 3 == 2) ok = false;
cur /= 3;
}
if (ok) break;
++n;
}
cout << n << endl;
}
return 0;
}
1249C2 - Хорошие числа (сложная версия)
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 q;
cin >> q;
for (int i = 0; i < q; ++i) {
long long n;
cin >> n;
vector<int> vals;
int pos2 = -1;
while (n > 0) {
vals.push_back(n % 3);
if (vals.back() == 2) pos2 = int(vals.size()) - 1;
n /= 3;
}
vals.push_back(0);
if (pos2 != -1) {
int pos0 = find(vals.begin() + pos2, vals.end(), 0) - vals.begin();
vals[pos0] = 1;
for (int i = pos0 - 1; i >= 0; --i) {
vals[i] = 0;
}
}
long long ans = 0;
long long pw = 1;
for (int i = 0; i < int(vals.size()); ++i) {
ans += pw * vals[i];
pw *= 3;
}
if (vals.back() == 1) ans = pw / 3;
cout << ans << endl;
}
return 0;
}
1249D1 - Слишком много отрезков (простая версия)
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int N = 250;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
cin >> n >> k;
vector<pair<int, int>> segs(n);
vector<int> cnt(N);
for (int i = 0; i < n; ++i) {
cin >> segs[i].first >> segs[i].second;
++cnt[segs[i].first];
--cnt[segs[i].second + 1];
}
for (int i = 0; i + 1 < N; ++i) {
cnt[i + 1] += cnt[i];
}
vector<int> ans(n);
for (int i = 0; i < N; ++i) {
while (cnt[i] > k) {
int pos = -1;
for (int p = 0; p < n; ++p) {
if (!ans[p] && (segs[p].first <= i && i <= segs[p].second) && (pos == -1 || segs[p].second > segs[pos].second)) {
pos = p;
}
}
assert(pos != -1);
for (int j = segs[pos].first; j <= segs[pos].second; ++j) {
--cnt[j];
}
ans[pos] = 1;
}
}
cout << accumulate(ans.begin(), ans.end(), 0) << endl;
for (int i = 0; i < n; ++i) {
if (ans[i]) cout << i + 1 << " ";
}
cout << endl;
return 0;
}
1249D2 - Слишком много отрезков (сложная версия)
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int N = 200200;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
cin >> n >> k;
vector<pair<int, int>> segs(n);
vector<int> cnt(N);
vector<vector<int>> ev(N);
for (int i = 0; i < n; ++i) {
cin >> segs[i].first >> segs[i].second;
++cnt[segs[i].first];
--cnt[segs[i].second + 1];
ev[segs[i].first].push_back(i + 1);
ev[segs[i].second + 1].push_back(-i - 1);
}
for (int i = 0; i + 1 < N; ++i) {
cnt[i + 1] += cnt[i];
}
vector<int> ans(n), sub(N);
set<pair<int, int>> curSegs;
int curSub = 0;
for (int i = 0; i < N; ++i) {
curSub += sub[i];
for (auto it : ev[i]) {
if (it > 0) {
curSegs.insert(make_pair(segs[it - 1].second, it - 1));
} else {
auto iter = curSegs.find(make_pair(segs[-it - 1].second, -it - 1));
if (iter != curSegs.end()) curSegs.erase(iter);
}
}
while (cnt[i] - curSub > k) {
assert(!curSegs.empty());
int pos = curSegs.rbegin()->second;
curSegs.erase(prev(curSegs.end()));
++curSub;
--sub[segs[pos].second + 1];
ans[pos] = 1;
}
}
cout << accumulate(ans.begin(), ans.end(), 0) << endl;
for (int i = 0; i < n; ++i) {
if (ans[i]) cout << i + 1 << " ";
}
cout << endl;
return 0;
}
1249E - На лифте или по лестнице?
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, c;
cin >> n >> c;
vector<int> a(n - 1), b(n - 1);
for (int i = 0; i < n - 1; ++i) {
cin >> a[i];
}
for (int i = 0; i < n - 1; ++i) {
cin >> b[i];
}
vector<vector<int>> dp(n, vector<int>(2, INF));
dp[0][0] = 0, dp[0][1] = c;
for (int i = 0; i < n - 1; ++i) {
dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + a[i]);
dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + a[i]);
dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + b[i]);
dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + b[i] + c);
}
for (int i = 0; i < n; ++i) {
cout << min(dp[i][0], dp[i][1]) << " ";
}
cout << endl;
return 0;
}
1249F - Подмножество максимального веса
Tutorial
Tutorial is loading...
Solution (Vovuh, n^3)
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int n, k;
vector<int> a;
vector<vector<int>> g, dp;
void dfs(int v, int p) {
dp[v][0] = a[v];
for (auto to : g[v]) {
if (to != p) dfs(to, v);
}
for (int dep = 0; dep < N; ++dep) {
if (dep == 0) {
for (auto to : g[v]) {
if (to == p) continue;
dp[v][dep] += dp[to][max(0, k - dep - 1)];
}
} else {
for (auto to : g[v]) {
if (to == p) continue;
int cur = dp[to][dep - 1];
for (auto other : g[v]) {
if (other == p || other == to) continue;
cur += dp[other][max(dep - 1, k - dep - 1)];
}
dp[v][dep] = max(dp[v][dep], cur);
}
}
}
for (int dep = N - 1; dep > 0; --dep) {
dp[v][dep - 1] = max(dp[v][dep - 1], dp[v][dep]);
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> k;
++k;
a = vector<int>(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
g = vector<vector<int>>(n);
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
g[y].push_back(x);
}
dp = vector<vector<int>>(n, vector<int>(N));
dfs(0, -1);
cout << dp[0][0] << endl;
return 0;
}
Solution (PikMike, n^2)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int N = 200 + 13;
const int INF = 1e9;
int n, k;
int a[N];
vector<int> g[N];
int dp[N][N];
int d[N];
int tmp[N];
void dfs(int v, int p = -1){
d[v] = 1;
dp[v][0] = a[v];
for (auto u : g[v]) if (u != p){
dfs(u, v);
int nw = max(d[v], d[u] + 1);
forn(i, nw)
tmp[i] = -INF;
forn(i, d[v]) for (int j = max(0, k - i); j < d[u]; ++j)
tmp[min(i, j + 1)] = max(tmp[min(i, j + 1)], dp[v][i] + dp[u][j]);
forn(i, d[u])
tmp[i + 1] = max(tmp[i + 1], dp[u][i]);
forn(i, d[v])
dp[v][i] = max(dp[v][i], tmp[i]);
for (int i = d[v]; i < nw; ++i)
dp[v][i] = tmp[i];
d[v] = nw;
for (int i = d[v] - 1; i > 0; --i)
dp[v][i - 1] = max(dp[v][i - 1], dp[v][i]);
}
}
int main(){
scanf("%d%d", &n, &k);
forn(i, n)
scanf("%d", &a[i]);
forn(i, n - 1){
int v, u;
scanf("%d%d", &v, &u);
--v, --u;
g[v].push_back(u);
g[u].push_back(v);
}
dfs(0);
printf("%d\n", dp[0][0]);
}