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;
cin >> n;
int sum = 0;
bool odd = false, even = false;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
sum += x;
odd |= x % 2 != 0;
even |= x % 2 == 0;
}
if (sum % 2 != 0 || (odd && even)) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
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 s;
cin >> s;
int ans = 0;
int pw = 1000 * 1000 * 1000;
while (s > 0) {
while (s < pw) pw /= 10;
ans += pw;
s -= pw - pw / 10;
}
cout << ans << endl;
}
return 0;
}
1296C - Yet Another Walking Robot
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 n;
string s;
cin >> n >> s;
int l = -1, r = n;
map<pair<int, int>, int> vis;
pair<int, int> cur = {0, 0};
vis[cur] = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == 'L') --cur.first;
if (s[i] == 'R') ++cur.first;
if (s[i] == 'U') ++cur.second;
if (s[i] == 'D') --cur.second;
if (vis.count(cur)) {
if (i - vis[cur] + 1 < r - l + 1) {
l = vis[cur];
r = i;
}
}
vis[cur] = i + 1;
}
if (l == -1) {
cout << -1 << endl;
} else {
cout << l + 1 << " " << r + 1 << endl;
}
}
return 0;
}
Inspiration: 300iq, 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 n, a, b, k;
cin >> n >> a >> b >> k;
vector<int> h(n);
for (int i = 0; i < n; ++i) {
cin >> h[i];
h[i] %= a + b;
if (h[i] == 0) h[i] += a + b;
h[i] = ((h[i] + a - 1) / a) - 1;
}
sort(h.begin(), h.end());
int ans = 0;
for (int i = 0; i < n; ++i) {
if (k - h[i] < 0) break;
++ans;
k -= h[i];
}
cout << ans << endl;
return 0;
}
1296E1 - String Coloring (easy version)
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution (dp)
#include <bits/stdc++.h>
using namespace std;
const int N = 222;
const int AL = 26;
bool dp[N][AL][AL];
pair<pair<int, int>, int> p[N][AL][AL];
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
string s;
cin >> n >> s;
dp[0][0][0] = 1;
for (int i = 0; i < n; ++i) {
int c = s[i] - 'a';
for (int c1 = 0; c1 < AL; ++c1) {
for (int c2 = 0; c2 < AL; ++c2) {
if (!dp[i][c1][c2]) continue;
if (c >= c1) {
dp[i + 1][c][c2] = 1;
p[i + 1][c][c2] = make_pair(make_pair(c1, c2), 0);
}
if (c >= c2) {
dp[i + 1][c1][c] = 1;
p[i + 1][c1][c] = make_pair(make_pair(c1, c2), 1);
}
}
}
}
int x = -1, y = -1;
for (int c1 = 0; c1 < AL; ++c1) {
for (int c2 = 0; c2 < AL; ++c2) {
if (dp[n][c1][c2]) {
x = c1, y = c2;
}
}
}
if (x == -1) {
cout << "NO" << endl;
return 0;
}
string res;
for (int i = n; i > 0; --i) {
int prvx = p[i][x][y].first.first;
int prvy = p[i][x][y].first.second;
if (p[i][x][y].second) res += '1';
else res += '0';
x = prvx;
y = prvy;
}
reverse(res.begin(), res.end());
cout << "YES" << endl << res << endl;
return 0;
}
Solution (greedy)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
string s;
cin >> n >> s;
string res;
char lst0 = 'a', lst1 = 'a';
for (int i = 0; i < n; ++i) {
if (s[i] >= lst0) {
res += '0';
lst0 = s[i];
} else if (s[i] >= lst1) {
res += '1';
lst1 = s[i];
} else {
cout << "NO" << endl;
return 0;
}
}
cout << "YES" << endl << res << endl;
return 0;
}
1296E2 - String Coloring (hard version)
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;
string s;
cin >> n >> s;
vector<int> maxdp(26);
vector<int> dp(n, 1);
for (int i = 0; i < n; ++i) {
for (int c = 25; c > s[i] - 'a'; --c) {
dp[i] = max(dp[i], maxdp[c] + 1);
}
maxdp[s[i] - 'a'] = max(maxdp[s[i] - 'a'], dp[i]);
}
cout << *max_element(maxdp.begin(), maxdp.end()) << endl;
for (int i = 0; i < n; ++i) cout << dp[i] << " ";
cout << endl;
return 0;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> val;
vector<vector<pair<int, int>>> g;
void dfs(int v, int pv, int pe, vector<pair<int, int>> &p) {
p[v] = make_pair(pv, pe);
for (auto it : g[v]) {
int to = it.first;
int idx = it.second;
if (to == pv) continue;
dfs(to, v, idx, p);
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n;
g = vector<vector<pair<int, int>>>(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(make_pair(v, i));
g[v].push_back(make_pair(u, i));
}
vector<vector<pair<int, int>>> p(n, vector<pair<int, int>>(n));
for (int i = 0; i < n; ++i) {
dfs(i, -1, -1, p[i]);
}
val = vector<int>(n - 1, 1000000);
cin >> m;
vector<pair<pair<int, int>, int>> q(m);
for (int i = 0; i < m; ++i) {
cin >> q[i].first.first >> q[i].first.second >> q[i].second;
--q[i].first.first;
--q[i].first.second;
}
sort(q.begin(), q.end(), [&](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
return a.second < b.second;
});
for (int i = 0; i < m; ++i) {
int u = q[i].first.first;
int v = q[i].first.second;
while (v != u) {
int pv = p[u][v].first;
int pe = p[u][v].second;
val[pe] = q[i].second;
v = pv;
}
}
for (int i = 0; i < m; ++i) {
int u = q[i].first.first;
int v = q[i].first.second;
int mx = 1000000;
while (v != u) {
int pv = p[u][v].first;
int pe = p[u][v].second;
mx = min(mx, val[pe]);
v = pv;
}
if (mx != q[i].second) {
cout << -1 << endl;
return 0;
}
}
for (int i = 0; i < n - 1; ++i) {
cout << val[i] << " ";
}
cout << endl;
return 0;
}