Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
void solve()
{
string s;
cin >> s;
int n = s.size();
int idx = -1;
for(int i = 0; i + 1 < n; i++)
if(s[i] == s[i + 1])
idx = i;
if(idx == -1)
{
if(s.back() == 'a') cout << (s + "b") << endl;
else cout << (s + "a") << endl;
}
else
{
string t = "a";
if(s[idx] == 'a') t = "b";
cout << s.substr(0, idx + 1) + t + s.substr(idx + 1) << endl;
}
}
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
solve();
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<string> s(2);
for (auto& x : s) cin >> x;
int ans = 0;
for (int i = 1; i < n - 1; ++i) {
bool ok = true;
ok &= (s[0][i] == '.' && s[1][i] == '.');
ok &= (s[0][i - 1] != s[1][i - 1]);
ok &= (s[0][i + 1] != s[1][i + 1]);
ok &= (s[0][i - 1] == s[0][i + 1]);
ans += ok;
}
cout << ans << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (adedalic)
import java.util.LinkedList
fun main() {
repeat(readln().toInt()) {
val n = readln().toInt()
val s = readln()
var ans = 0L
val bracketPositions = LinkedList<Int>()
for (i in s.indices) {
var c = s[i]
if (c == '_') {
c = if (bracketPositions.isEmpty()) '(' else ')'
}
if (c == ')') {
ans += i - bracketPositions.pollLast()
}
else
bracketPositions.addLast(i)
}
println(ans)
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a) cin >> x;
vector<vector<int>> g(n);
for (int i = 1; i < n; ++i) {
int p;
cin >> p;
g[p - 1].push_back(i);
}
auto check = [&](auto&& self, int v, int x) -> bool {
if (x > INF) return false;
bool isLeaf = true;
if (v) x += max(0, x - a[v]);
for (auto u : g[v]) {
isLeaf = false;
if (!self(self, u, x)) return false;
}
return (!isLeaf || x <= a[v]);
};
int l = 1, r = INF;
while (l <= r) {
int mid = (l + r) / 2;
if (check(check, 0, mid)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << a[0] + l - 1 << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение 1 (awoo)
#include <bits/stdc++.h>
#include "ext/pb_ds/assoc_container.hpp"
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace __gnu_pbds;
using namespace std;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct query{
int i, j;
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<int> a(n);
forn(i, n) cin >> a[i];
vector<vector<query>> q(n + 1);
forn(j, m){
int i, x;
cin >> i >> x;
--i;
q[x].push_back({i, j});
}
forn(i, n + 1){
sort(q[i].begin(), q[i].end(), [](const query &a, const query &b){
return a.i > b.i;
});
}
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j){
return a[i] > a[j];
});
vector<int> cur(n + 1);
vector<char> ans(m);
ordered_set<int> alive(ord.begin(), ord.end());
for (int lvl = 1; lvl <= n; ++lvl){
for (int k = 1; k <= n; ++k){
if (cur[k] >= n) break;
int x = alive.order_of_key(cur[k]);
int nxt = x + k - 1 >= int(alive.size()) ? n : *alive.find_by_order(x + k - 1);
while (!q[k].empty() && q[k].back().i <= nxt){
ans[q[k].back().j] = (a[q[k].back().i] >= lvl);
q[k].pop_back();
}
cur[k] = nxt + 1;
}
while (!ord.empty() && a[ord.back()] == lvl){
alive.erase(ord.back());
ord.pop_back();
}
}
for (auto x : ans) cout << (x ? "YES" : "NO") << '\n';
return 0;
}
Решение 2 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
struct query{
int i, j;
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<int> a(n);
forn(i, n) cin >> a[i];
vector<vector<query>> q(n + 1);
forn(j, m){
int i, x;
cin >> i >> x;
--i;
q[x].push_back({i, j});
}
forn(i, n + 1) sort(q[i].begin(), q[i].end(), [](const query &a, const query &b){
return a.i > b.i;
});
int P = min(1000, n + 1);
vector<char> ans(m);
for (int k = 1; k < P; ++k){
int cur = 1;
int cnt = 0;
forn(i, n){
bool fl = false;
if (a[i] >= cur){
++cnt;
fl = true;
if (cnt == k){
++cur;
cnt = 0;
}
}
while (!q[k].empty() && q[k].back().i == i){
ans[q[k].back().j] = fl;
q[k].pop_back();
}
}
}
vector<int> sum1(n), sum2(n);
int p2 = ceil(sqrt(n + 2));
auto add = [&](int i){
int bl = i / p2;
for (int j = bl + 1; j * p2 < n; ++j)
++sum1[j];
for (int j = i; j < (bl + 1) * p2 && j < n; ++j)
++sum2[j];
};
int mx = n / P + 5;
vector<vector<int>> pos(mx);
forn(i, n){
if (a[i] < mx)
pos[a[i]].push_back(i);
else
add(i);
}
for (auto &it : pos) reverse(it.begin(), it.end());
for (int k = P; k <= n; ++k){
while (true){
int mn = n;
int who = -1;
forn(lvl, mx) if (!pos[lvl].empty()){
int i = pos[lvl].back();
if (mn < i) continue;
int cnt = sum1[i / p2] + sum2[i];
if (a[i] >= cnt / k + 1){
mn = i;
who = lvl;
}
}
if (who == -1) break;
add(mn);
pos[who].pop_back();
}
for (auto it : q[k]){
int lvl = a[it.i];
ans[it.j] = (lvl >= mx || pos[lvl].empty() || pos[lvl].back() > it.i);
}
}
for (auto x : ans) cout << (x ? "YES" : "NO") << '\n';
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int main()
{
int n, x, m;
cin >> n >> x >> m;
vector<int> fib = {0, 1};
for(int i = 2; i <= 30; i++)
fib.push_back(fib[i - 1] + fib[i - 2]);
int max_sum = fib[x] * n;
vector<vector<int>> dp(max_sum + 1, vector<int>(n + 1));
dp[0][0] = 1;
for(int i = 1; i <= x; i++)
for(int j = 0; j < max_sum; j++)
for(int k = 0; k < n; k++)
{
if(j + fib[i] <= max_sum)
dp[j + fib[i]][k + 1] = add(dp[j + fib[i]][k + 1], dp[j][k]);
}
vector<int> cost(max_sum + 1, 1e9);
cost[0] = 0;
for(int j = 1; j <= max_sum; j++)
for(int i = 1; i <= 30; i++)
if(j >= fib[i])
cost[j] = min(cost[j], cost[j - fib[i]] + 1);
int ans = 0;
for(int i = 0; i <= max_sum; i++)
if(cost[i] == m)
ans = add(ans, dp[i][n]);
cout << ans << endl;
}