Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int x, y;
cin >> x >> y;
int d = x * x + y * y;
int r = 0;
while (r * r < d) ++r;
int ans = 2;
if (r * r == d) ans = 1;
if (x == 0 && y == 0) ans = 0;
cout << ans << '\n';
}
}
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val (n, B, x, y) = readLine()!!.split(' ').map { it.toInt() }
var cur = 0L
var ans = 0L
for (i in 1..n) {
cur += if (cur + x <= B) x else -y
ans += cur
}
println(ans)
}
}
1657C - Bracket Sequence Deletion
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (vovuh)
#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 = 0;
int cnt = 0;
while (l + 1 < n) {
if (s[l] == '(' || (s[l] == ')' && s[l + 1] == ')')) {
l += 2;
} else {
int r = l + 1;
while (r < n && s[r] != ')') {
++r;
}
if (r == n) {
break;
}
l = r + 1;
}
++cnt;
}
cout << cnt << ' ' << n - l << '\n';
}
return 0;
}
1657D - For Gamers. By Gamers.
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
int main(){
int n, C;
scanf("%d%d", &n, &C);
vector<long long> bst(C + 1);
forn(i, n){
int c, d, h;
scanf("%d%d%d", &c, &d, &h);
bst[c] = max(bst[c], d * 1ll * h);
}
for (int c = 1; c <= C; ++c) for (int xc = c; xc <= C; xc += c)
bst[xc] = max(bst[xc], bst[c] * (xc / c));
forn(c, C)
bst[c + 1] = max(bst[c + 1], bst[c]);
int m;
scanf("%d", &m);
forn(j, m){
int D;
long long H;
scanf("%d%lld", &D, &H);
int mn = upper_bound(bst.begin(), bst.end(), D * H) - bst.begin();
if (mn > C) mn = -1;
printf("%d ", mn);
}
puts("");
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int MOD = 998244353;
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
return a;
}
int mul(int a, int b){
return a * 1ll * b % MOD;
}
int binpow(int a, int b){
int res = 1;
while (b){
if (b & 1)
res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
int main(){
int n, k;
scanf("%d%d", &n, &k);
--n;
vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
vector<vector<int>> C(n + 1);
forn(i, n + 1){
C[i].resize(i + 1);
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; ++j)
C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
}
dp[0][0] = 1;
forn(i, k) forn(t, n + 1) {
int pw = binpow(k - i, t * (t - 1) / 2);
int step = binpow(k - i, t);
forn(j, n - t + 1){
dp[i + 1][j + t] = add(dp[i + 1][j + t], mul(dp[i][j], mul(C[n - j][t], pw)));
pw = mul(pw, step);
}
}
printf("%d\n", dp[k][n]);
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
vector<vector<int>> t;
vector<int> p, h;
void init(int v){
for (int u : t[v]) if (u != p[v]){
p[u] = v;
h[u] = h[v] + 1;
init(u);
}
}
vector<int> get_path(int v, int u){
vector<int> l, r;
while (v != u){
if (h[v] > h[u]){
l.push_back(v);
v = p[v];
}
else{
r.push_back(u);
u = p[u];
}
}
l.push_back(v);
while (!r.empty()){
l.push_back(r.back());
r.pop_back();
}
return l;
}
vector<vector<int>> g, tg;
void add_edge(int v, bool vx, int u, bool vy){
// (val[v] == vx) -> (val[u] == vy)
g[v * 2 + vx].push_back(u * 2 + vy);
tg[u * 2 + vy].push_back(v * 2 + vx);
g[u * 2 + !vy].push_back(v * 2 + !vx);
tg[v * 2 + !vx].push_back(u * 2 + !vy);
}
vector<int> ord;
vector<char> used;
void ts(int v){
used[v] = true;
for (int u : g[v]) if (!used[u])
ts(u);
ord.push_back(v);
}
vector<int> clr;
int k;
void dfs(int v){
clr[v] = k;
for (int u : tg[v]) if (clr[u] == -1)
dfs(u);
}
int main(){
cin.tie(0);
iostream::sync_with_stdio(false);
int n, m;
cin >> n >> m;
t.resize(n);
p.resize(n);
h.resize(n);
p[0] = -1;
forn(i, n - 1){
int v, u;
cin >> v >> u;
--v, --u;
t[v].push_back(u);
t[u].push_back(v);
}
init(0);
vector<vector<int>> paths(m);
vector<string> s(m);
vector<pair<char, char>> opts(n, make_pair(-1, -1));
forn(i, m){
int v, u;
cin >> v >> u >> s[i];
--v, --u;
paths[i] = get_path(v, u);
int k = s[i].size();
assert(int(paths[i].size()) == k);
forn(j, k) opts[paths[i][j]] = {s[i][j], s[i][k - j - 1]};
}
int nm = (n + m) * 2;
g.resize(nm);
tg.resize(nm);
forn(i, m){
int k = s[i].size();
forn(j, k){
int v = paths[i][j];
char c = s[i][j], rc = s[i][k - j - 1];
char d = opts[v].first, rd = opts[v].second;
if (d != c) add_edge(v, false, n + i, true);
if (d != rc) add_edge(v, false, n + i, false);
if (rd != c) add_edge(v, true, n + i, true);
if (rd != rc) add_edge(v, true, n + i, false);
}
}
used.resize(nm);
forn(i, nm) if (!used[i]) ts(i);
clr.resize(nm, -1);
reverse(ord.begin(), ord.end());
for (int v : ord) if (clr[v] == -1){
dfs(v);
++k;
}
forn(i, nm) if (clr[i] == clr[i ^ 1]){
cout << "NO\n";
return 0;
}
cout << "YES\n";
for (int i = 0; i < 2 * n; i += 2){
if (opts[i / 2].first == -1)
cout << 'a';
else if (clr[i] > clr[i ^ 1])
cout << opts[i / 2].first;
else
cout << opts[i / 2].second;
}
cout << "\n";
}