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 t;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
if (a % b == 0) cout << 0 << endl;
else cout << b - a % b << endl;
}
return 0;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#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 n, k;
cin >> n >> k;
string s(n, 'a');
for (int i = n - 2; i >= 0; i--) {
if (k <= (n - i - 1)) {
s[i] = 'b';
s[n - k] = 'b';
cout << s << endl;
break;
}
k -= (n - i - 1);
}
}
}
Idea: vovuh
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 t;
cin >> t;
while (t--) {
int n;
string x;
cin >> n >> x;
string a(n, '0'), b(n, '0');
for (int i = 0; i < n; ++i) {
if (x[i] == '1') {
a[i] = '1';
b[i] = '0';
for (int j = i + 1; j < n; ++j) {
b[j] = x[j];
}
break;
} else {
a[i] = b[i] = '0' + (x[i] - '0') / 2;
}
}
cout << a << endl << b << endl;
}
return 0;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
if (count(a.begin(), a.end(), a[0]) == n) {
cout << 1 << endl;
for (int i = 0; i < n; ++i) {
cout << 1 << " ";
}
cout << endl;
return 0;
}
if (n % 2 == 0) {
cout << 2 << endl;
for (int i = 0; i < n; ++i) {
cout << i % 2 + 1 << " ";
}
cout << endl;
return 0;
}
for (int i = 0; i < n; ++i) {
if (a[i] == a[(i + 1) % n]) {
vector<int> ans(n);
for (int j = 0, pos = i + 1; pos < n; ++pos, j ^= 1) {
ans[pos] = j + 1;
}
for (int j = 0, pos = i; pos >= 0; --pos, j ^= 1) {
ans[pos] = j + 1;
}
cout << 2 << endl;
for (int pos = 0; pos < n; ++pos) {
cout << ans[pos] << " ";
}
cout << endl;
return 0;
}
}
cout << 3 << endl;
for (int i = 0; i < n - 1; ++i) {
cout << i % 2 + 1 << " ";
}
cout << 3 << endl;
return 0;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int qq = 0; qq < q; qq++) {
solve();
}
return 0;
}
Idea: MikeMirzayanov and vovuh
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int T;
vector<int> p, d;
vector<int> tin, tout;
vector<vector<int>> g;
void dfs(int v, int par = -1, int dep = 0) {
p[v] = par;
d[v] = dep;
tin[v] = T++;
for (auto to : g[v]) {
if (to == par) continue;
dfs(to, v, dep + 1);
}
tout[v] = T++;
}
bool isAnc(int v, int u) {
return tin[v] <= tin[u] && tout[u] <= tout[v];
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, m;
cin >> n >> m;
T = 0;
p = d = vector<int>(n);
tin = tout = vector<int>(n);
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);
}
dfs(0);
for (int i = 0; i < m; ++i) {
int k;
cin >> k;
vector<int> v(k);
for (auto &it : v) {
cin >> it;
--it;
}
int u = v[0];
for (auto it : v) if (d[u] < d[it]) u = it;
for (auto &it : v) {
if (it == u) continue;
if (p[it] != -1) it = p[it];
}
bool ok = true;
for (auto it : v) ok &= isAnc(it, u);
if (ok) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
Idea: MikeMirzayanov
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 n, k;
cin >> n >> k;
vector<int> a(n);
for (auto &it : a) cin >> it;
sort(a.begin(), a.end());
vector<pair<int, int>> cnt;
for (auto it : a) {
if (cnt.empty() || cnt.back().first != it) {
cnt.push_back({it, 1});
} else {
++cnt.back().second;
}
}
vector<long long> prefsum, sufsum;
vector<int> prefcnt, sufcnt;
for (int i = 0; i < int(cnt.size()); ++i) {
long long cursum = cnt[i].first * 1ll * cnt[i].second;
int curcnt = cnt[i].second;
if (prefsum.empty()) {
prefsum.push_back(cursum);
prefcnt.push_back(curcnt);
} else {
prefsum.push_back(prefsum.back() + cursum);
prefcnt.push_back(prefcnt.back() + curcnt);
}
}
for (int i = int(cnt.size()) - 1; i >= 0; --i) {
long long cursum = cnt[i].first * 1ll * cnt[i].second;
int curcnt = cnt[i].second;
if (sufsum.empty()) {
sufsum.push_back(cursum);
sufcnt.push_back(curcnt);
} else {
sufsum.push_back(sufsum.back() + cursum);
sufcnt.push_back(sufcnt.back() + curcnt);
}
}
reverse(sufsum.begin(), sufsum.end());
reverse(sufcnt.begin(), sufcnt.end());
long long ans = INF64;
for (int i = 0; i < int(cnt.size()); ++i) {
int cur = max(0, k - cnt[i].second);
int needl = 0;
if (i > 0) needl = min(cur, prefcnt[i - 1]);
int needr = max(0, cur - needl);
long long res = 0;
if (i > 0 && needl > 0) {
res += prefcnt[i - 1] * 1ll * (cnt[i].first - 1) - prefsum[i - 1];
res += needl;
}
if (i + 1 < int(cnt.size()) && needr > 0) {
res += sufsum[i + 1] - sufcnt[i + 1] * 1ll * (cnt[i].first + 1);
res += needr;
}
ans = min(ans, res);
needr = 0;
if (i + 1 < int(cnt.size())) needr = min(cur, sufcnt[i + 1]);
needl = max(0, cur - needr);
res = 0;
if (i > 0 && needl > 0) {
res += prefcnt[i - 1] * 1ll * (cnt[i].first - 1) - prefsum[i - 1];
res += needl;
}
if (i + 1 < int(cnt.size()) && needr > 0) {
res += sufsum[i + 1] - sufcnt[i + 1] * 1ll * (cnt[i].first + 1);
res += needr;
}
ans = min(ans, res);
}
cout << ans << endl;
return 0;
}