1154A - Restoring Three Numbers
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
vector<int> a(4);
for (int i = 0; i < 4; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
cout << a[3] - a[0] << " " << a[3] - a[1] << " " << a[3] - a[2] << endl;
return 0;
}
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 n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
a.resize(unique(a.begin(), a.end()) - a.begin());
if (a.size() > 3) {
cout << -1 << endl;
} else {
if (a.size() == 1) {
cout << 0 << endl;
} else if (a.size() == 2) {
if ((a[1] - a[0]) % 2 == 0) {
cout << (a[1] - a[0]) / 2 << endl;
} else {
cout << a[1] - a[0] << endl;
}
} else {
if (a[1] - a[0] != a[2] - a[1]) {
cout << -1 << endl;
} else {
cout << a[1] - a[0] << endl;
}
}
}
return 0;
}
Idea: le.mur
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
vector<int> a(3);
cin >> a[0] >> a[1] >> a[2];
vector<int> idx({0, 1, 2, 0, 2, 1, 0});
int full = min({a[0] / 3, a[1] / 2, a[2] / 2});
a[0] -= full * 3;
a[1] -= full * 2;
a[2] -= full * 2;
int ans = 0;
for (int start = 0; start < 7; ++start) {
int day = start;
vector<int> b = a;
int cur = 0;
while (b[idx[day]] > 0) {
--b[idx[day]];
day = (day + 1) % 7;
++cur;
}
ans = max(ans, full * 7 + cur);
}
cout << ans << endl;
return 0;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
int a, b, maxa;
void use_battery(int s)
{
if(s == 1) a = min(a + 1, maxa);
--b;
}
void use_accum()
{
--a;
}
int main()
{
int ans = 0;
int n;
cin >> n >> b >> a;
maxa = a;
vector<int> s(n);
for(int i = 0; i < n; i++) cin >> s[i];
for(int i = 0; i < n; i++)
{
if(a == 0 && b == 0)
break;
else if(a == 0)
use_battery(s[i]);
else if(b == 0)
use_accum();
else if(s[i] == 1 && a < maxa)
use_battery(s[i]);
else use_accum();
ans++;
}
cout << ans << endl;
}
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 n, k;
cin >> n >> k;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i].first;
a[i].second = i;
}
sort(a.rbegin(), a.rend());
queue<int> q;
for (int i = 0; i < n; ++i) {
q.push(a[i].second);
}
set<int> idx;
for (int i = 0; i < n; ++i) {
idx.insert(i);
}
string ans(n, '0');
int who = 0;
while (!idx.empty()) {
while (!idx.count(q.front())) {
q.pop();
}
int pos = q.front();
q.pop();
vector<int> add;
auto it = idx.find(pos);
for (int i = 0; i <= k; ++i) {
add.push_back(*it);
if (it == idx.begin()) break;
--it;
}
it = next(idx.find(pos));
for (int i = 0; i < k; ++i) {
if (it == idx.end()) break;
add.push_back(*it);
++it;
}
for (auto it : add) {
idx.erase(it);
ans[it] = '1' + who;
}
who ^= 1;
}
cout << ans << endl;
return 0;
}
Idea: MikeMirzayanov
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, m, k;
cin >> n >> m >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
a.resize(k);
reverse(a.begin(), a.end());
vector<int> offers(k + 1);
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
if (x <= k) {
offers[x] = max(offers[x], y);
}
}
vector<int> pref(k + 1);
for (int i = 0; i < k; ++i) {
pref[i + 1] = pref[i] + a[i];
}
vector<int> dp(k + 1, INF);
dp[0] = 0;
for (int i = 0; i < k; ++i) {
dp[i + 1] = min(dp[i + 1], dp[i] + a[i]);
for (int j = 1; j <= k; ++j) {
if (offers[j] == 0) continue;
if (i + j > k) break;
dp[i + j] = min(dp[i + j], dp[i] + pref[i + j - offers[j]] - pref[i]);
}
}
cout << dp[k] << endl;
return 0;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int N = 10 * 1000 * 1000 + 11;
int n;
vector<int> a;
int mind[N];
pair<int, int> mins[N];
vector<pair<int, int>> divs;
void build_sieve() {
vector<int> pr;
mind[0] = mind[1] = 1;
for (int i = 2; i < N; ++i) {
if (mind[i] == 0) {
pr.push_back(i);
mind[i] = i;
}
for (int j = 0; j < int(pr.size()) && pr[j] <= mind[i] && i * pr[j] < N; ++j) {
mind[i * pr[j]] = pr[j];
}
}
}
void add_to_mins(int curd, int idx) {
if(mins[curd].first == -1)
mins[curd].first = idx;
else if(mins[curd].second == -1)
mins[curd].second = idx;
}
void rec(int pos, int curd, int idx) {
if (pos == int(divs.size())) {
add_to_mins(curd, idx);
return;
}
int curm = 1;
for (int i = 0; i <= divs[pos].second; ++i) {
rec(pos + 1, curd * curm, idx);
curm *= divs[pos].first;
}
}
void add(int idx) {
int value = a[idx];
divs.clear();
while (value > 1) {
int d = mind[value];
if (!divs.empty() && divs.back().first == d) {
++divs.back().second;
} else {
divs.push_back(make_pair(d, 1));
}
value /= d;
}
rec(0, 1, idx);
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n;
a.resize(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for(int i = 0; i < N; i++)
mins[i] = make_pair(-1, -1);
build_sieve();
vector<pair<int, int> > vals;
for(int i = 0; i < n; i++)
vals.push_back(make_pair(a[i], i));
sort(vals.begin(), vals.end());
for (int i = 0; i < n; ++i) {
if(i > 1 && vals[i].first == vals[i - 2].first) continue;
add(vals[i].second);
}
long long l = INF * 1ll * INF;
int ansi = -1, ansj = -1;
for (int i = 1; i < N; ++i) {
pair<int, int> idxs = mins[i];
if (idxs.second == -1) continue;
long long curl = a[idxs.first] * 1ll * a[idxs.second] / i;
if (l > curl) {
l = curl;
ansi = min(idxs.first, idxs.second);
ansj = max(idxs.first, idxs.second);
}
}
cout << ansi + 1 << " " << ansj + 1 << endl;
return 0;
}