1282A - Абонент временно недоступен
Идея: MikeMirzayanov Разработка: MikeMirzayanov
Разбор
Tutorial is loading...
Решение (MikeMirzayanov)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int a, b, c, r;
cin >> a >> b >> c >> r;
int L = max(min(a, b), c - r);
int R = min(max(a, b), c + r);
cout << max(a, b) - min(a, b) - max(0, R - L) << endl;
}
}
1282B1 - K по цене одного (простая версия), 1282B2 - K по цене одного (усложнённая версия)
Идея: MikeMirzayanov, unreal.eugene Разработка: Supermagzzz
Разбор
Tutorial is loading...
Решение (Supermagzzz)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
int main() {
int cntTest;
cin >> cntTest;
for (int test = 0; test < cntTest; test++) {
int n, p, k;
cin >> n >> p >> k;
int pref = 0;
int ans = 0;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
for (int i = 0; i <= k; i++) {
int sum = pref;
if (sum > p) break;
int cnt = i;
for (int j = i + k - 1; j < n; j += k) {
if (sum + a[j] <= p) {
cnt += k;
sum += a[j];
} else {
break;
}
}
pref += a[i];
ans = max(ans, cnt);
}
cout << ans << "\n";
}
}
Идея: AdvancerMan Разработка: Supermagzzz
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
int main() {
int cntTest;
cin >> cntTest;
for (int test = 0; test < cntTest; test++) {
ll n, t, a, b;
cin >> n >> t >> a >> b;
vector<pair<ll, ll>> v;
vector<int> hard(n);
int cntA = 0, cntB = 0;
for (int i = 0; i < n; i++) {
cin >> hard[i];
if (hard[i]) {
cntB++;
} else {
cntA++;
}
}
for (int i = 0; i < n; i++) {
ll time;
cin >> time;
v.push_back({time, hard[i]});
}
v.push_back({t + 1, 0});
sort(v.begin(), v.end());
ll cnt1 = 0, cnt2 = 0;
ll ans = 0;
for (int i = 0; i <= n; i++) {
ll need = cnt1 * a + cnt2 * b;
ll has = v[i].first - 1 - need;
if (has >= 0) {
ll canA = min((cntA - cnt1), has / a);
has -= canA * a;
ll canB = min((cntB - cnt2), has / b);
ans = max(ans, cnt1 + cnt2 + canA + canB);
}
int l = i;
while (l < v.size() && v[l].first == v[i].first) {
if (v[l].second) {
cnt2++;
} else {
cnt1++;
}
l++;
}
i = l - 1;
}
cout << ans << "\n";
}
}
1282D - Заколдованный артефакт
Идея: unreal.eugene Разработка: unreal.eugene
Разбор
Tutorial is loading...
Решение от Darui99
#include <bits/stdc++.h>
using namespace std;
int f(string s) {
cout << s << endl;
int w;
cin >> w;
if (w == 0)
exit(0);
return w;
}
int main() {
const int N = 300;
int st = f(string(N, 'a'));
int n = 2 * N - (st + f(string(N, 'b')));
string t(n, 'a');
int A = N - st, B = n - A;
st = B;
for (int i = 0; i < n - 1; i++) {
t[i] = 'b';
if (f(t) > st)
t[i] = 'a';
else
st--;
}
if (st)
t.back() = 'b';
f(t);
}
Идея: MikeMirzayanov, AdvancerMan Разработка: AdvancerMan
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
void dfs_order(int u, int p, vector<vector<int>> const& g, vector<int> &order) {
for (auto v : g[u]) {
if (v != p) {
dfs_order(v, u, g, order);
}
}
order.push_back(u);
}
void get_order(map<pair<int, int>, vector<int>> const& in, int n, vector<int> &order) {
vector<vector<int>> g(n);
for (auto e : in) {
auto vs = e.second;
if (vs.size() == 2) {
g[vs[0]].push_back(vs[1]);
g[vs[1]].push_back(vs[0]);
}
}
dfs_order(0, -1, g, order);
}
void dfs_polygon(int u, vector<vector<int>> const& g, vector<bool> &used, vector<int> &res) {
if (used[u]) {
return;
}
used[u] = true;
res.push_back(u);
for (auto e : g[u]) {
dfs_polygon(e, g, used, res);
}
}
void get_polygon(map<pair<int, int>, vector<int>> const& in, int n, vector<int> &polygon) {
vector<vector<int>> g(n);
for (auto e : in) {
if (e.second.size() == 1) {
auto edge = e.first;
g[edge.first].push_back(edge.second);
g[edge.second].push_back(edge.first);
}
}
vector<bool> used(n);
dfs_polygon(0, g, used, polygon);
}
void get_polygon(vector<vector<int>> const& in, int n, vector<int> const& order, vector<int> &polygon) {
vector<pair<int, int>> listp(n, {-1, -1});
auto last = in[order.back()];
for (int i = 0; i < 3; i++) {
listp[last[i]] = {last[(i + 1) % 3], last[(i + 2) % 3]};
}
for (int i = (int) order.size() - 2; i >= 0; i--) {
auto x = in[order[i]];
int j = 0;
while (listp[x[j]] != pair<int, int>{-1, -1}) {
j++;
}
int x1 = x[j], x2 = x[(j + 1) % 3], x3 = x[(j + 2) % 3];
if (listp[x2].second != x3) {
swap(x2, x3);
}
listp[x1] = {x2, x3};
listp[x2].second = x1;
listp[x3].first = x1;
}
polygon.push_back(0);
int now = listp[0].second;
while (now != 0) {
polygon.push_back(now);
now = listp[now].second;
}
}
void out(vector<int> const& v) {
for (auto e : v) {
cout << e + 1 << ' ';
}
cout << endl;
}
void solve() {
int n;
cin >> n;
vector<vector<int>> in(n - 2, vector<int>(3));
for (int i = 0; i < n - 2; i++) {
for (int j = 0; j < 3; j++) {
cin >> in[i][j];
in[i][j]--;
}
sort(in[i].begin(), in[i].end());
}
map<pair<int, int>, vector<int>> mp;
for (int i = 0; i < n - 2; i++) {
auto tri = in[i];
for (int j = 0; j < 2; j++) {
for (int k = j + 1; k < 3; k++) {
mp[{tri[j], tri[k]}].push_back(i);
}
}
}
vector<int> order;
get_order(mp, n, order);
vector<int> polygon;
get_polygon(in, n, order, polygon);
// get_polygon(mp, n, polygon); // another solution
out(polygon);
out(order);
}
int main() {
int t;
cin >> t;
for (int t_num = 1; t_num <= t; t_num++) {
solve();
}
return 0;
}