Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int solveSingle(int best, int other1, int other2)
{
return max(0, max(other1, other2) + 1 - best);
}
int main()
{
int t;
cin >> t;
while (t--)
{
int a, b, c;
cin >> a >> b >> c;
cout << solveSingle(a, b, c) << ' ' << solveSingle(b, a, c) << ' ' << solveSingle(c, a, b) << '\n';
}
return 0;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const string subseqs[] = { "00", "25", "50", "75" };
const int INF = 100;
int solve(string& s, string& t)
{
int sptr = s.length() - 1;
int ans = 0;
while (sptr >= 0 && s[sptr] != t[1])
{
sptr--;
ans++;
}
if (sptr < 0) return INF;
sptr--;
while (sptr >= 0 && s[sptr] != t[0])
{
sptr--;
ans++;
}
return sptr < 0 ? INF : ans;
}
int main()
{
int t;
cin >> t;
while (t--)
{
string n;
cin >> n;
int ans = INF;
for (auto e : subseqs)
ans = min(ans, solve(n, e));
cout << ans << '\n';
}
return 0;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
vector<int> x(k);
for (int i = 0; i < k; i++) cin >> x[i];
sort(x.rbegin(), x.rend());
int cnt = 0;
long long sum = 0;
while (cnt < x.size() && sum + n - x[cnt] < n)
{
sum += n - x[cnt++];
}
cout << cnt << '\n';
}
return 0;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
bool inf = true;
int minval = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] != a[0])
{
inf = false;
break;
}
minval = min(minval, a[i]);
}
if (inf)
{
cout << "-1\n";
continue;
}
sort(a.begin(), a.end());
int ans = 0;
for (int i = 0; i < n; i++)
ans = gcd(ans, a[i] - minval);
cout << ans << '\n';
}
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++)
set<int> divs(int n) {
set<int> d;
for (int dd = 1; dd * dd <= n; dd++)
if (n % dd == 0) {
d.insert(n / dd);
d.insert(dd);
}
return d;
}
int main() {
int t;
cin >> t;
forn(tt, t) {
int n;
cin >> n;
vector<int> a(n);
forn(i, n)
cin >> a[i];
int k = -1;
forn(i, n) {
int minv = a[i];
int same = 0;
vector<int> d;
forn(j, n) {
if (a[j] == minv)
same++;
else if (a[j] > minv)
d.push_back(a[j] - minv);
}
if (same >= n / 2) {
k = INT_MAX;
continue;
}
map<int,int> div_counts;
for (int di: d)
for (int dd: divs(di))
div_counts[dd]++;
for (auto p: div_counts)
if (p.second >= n / 2 - same)
k = max(k, p.first);
}
cout << (k == INT_MAX ? -1 : k) << endl;
}
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
vector<vector<int>> g(n, vector<int>());
vector<int> rem(n, 0);
vector<int> layer(n, 0);
for (int i = 1; i < n; i++)
{
int x, y;
cin >> x >> y;
x--;
y--;
g[x].push_back(y);
g[y].push_back(x);
rem[x]++;
rem[y]++;
}
queue<int> q;
for (int i = 0; i < n; i++)
if (rem[i] == 1)
{
q.push(i);
layer[i] = 1;
}
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v : g[u])
{
if (rem[v] != 1)
{
rem[v]--;
if (rem[v] == 1)
{
layer[v] = layer[u] + 1;
q.push(v);
}
}
}
}
int ans = 0;
for (int i = 0; i < n; i++)
if (layer[i] > k)
ans++;
cout << ans << '\n';
}
return 0;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 64;
bool dp[MAX_N][MAX_N][MAX_N][MAX_N]; // (taken, red, mod A, mod B) -> may be
pair<bool, int> sert[MAX_N][MAX_N][MAX_N][MAX_N]; // the same -> (true (red) | false(black), prev red/black)
int main()
{
int t;
cin >> t;
while (t--)
{
int n, a, b;
string x;
cin >> n >> a >> b >> x;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
for (int k = 0; k < a; k++)
for (int l = 0; l < b; l++)
dp[i][j][k][l] = false;
dp[0][0][0][0] = true;
for(int taken = 0; taken < n; taken++)
for(int red = 0; red <= taken; red++)
for(int remA = 0; remA < a; remA++)
for(int remB = 0; remB < b; remB++)
if (dp[taken][red][remA][remB])
{
// red transition
dp[taken + 1][red + 1][(remA * 10 + (x[taken] - '0')) % a][remB] = true;
sert[taken + 1][red + 1][(remA * 10 + (x[taken] - '0')) % a][remB] = { true, remA };
// black transition
dp[taken + 1][red][remA][(remB * 10 + (x[taken] - '0')) % b] = true;
sert[taken + 1][red][remA][(remB * 10 + (x[taken] - '0')) % b] = { false, remB };
}
int bestRed = 0;
for (int red = 1; red < n; red++)
if (dp[n][red][0][0] && abs(red - (n - red)) < abs(bestRed - (n - bestRed)))
bestRed = red;
if (bestRed == 0)
{
cout << "-1\n";
}
else
{
int taken = n;
int red = bestRed;
int remA = 0;
int remB = 0;
string ans = "";
while (taken > 0)
{
auto way = sert[taken][red][remA][remB];
if (way.first)
{
red--;
remA = way.second;
ans.push_back('R');
}
else
{
remB = way.second;
ans.push_back('B');
}
taken--;
}
reverse(ans.begin(), ans.end());
cout << ans << '\n';
}
}
return 0;
}
Idea: [user:nastya ka]
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1'000'000;
int psumOdd[MAX_N + 1];
int psumEven[MAX_N + 1];
void solve()
{
string s;
int q;
cin >> s >> q;
int n = s.length();
psumOdd[0] = psumEven[0] = 0;
for (int i = 0; i < n; i++)
{
psumOdd[i + 1] = psumOdd[i];
psumEven[i + 1] = psumEven[i];
if (s[i] == '[' || s[i] == ']')
{
if (i & 1)
psumOdd[i + 1]++;
else
psumEven[i + 1]++;
}
}
while (q--)
{
int l, r;
cin >> l >> r;
l--;
int odd = psumOdd[r] - psumOdd[l];
int even = psumEven[r] - psumEven[l];
cout << abs(odd - even) << '\n';
}
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}