Thank you for participating! I hope you enjoyed the problems.
Idea: Galina_Basalova
Tutorial
Tutorial is loading...
Solution (Galina_Basalova)
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << n * 2 << "\n";
}
return 0;
}
2086B - Large Array and Segments
Idea: FelixArg
Tutorial
Tutorial is loading...
Solution (FelixArg)
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n, k, x;
cin >> n >> k >> x;
vector<int> a(n);
for (int i = 0; i < n; i++){
cin >> a[i];
}
if (accumulate(a.begin(), a.end(), 0ll) * k < x){
cout << 0 << '\n';
return;
}
int l = 1, r = n * k;
while(l <= r){
int m = l + (r - l) / 2;
int cnt_a = (n * k - m + 1) / n;
int suff = (n * k - m + 1) % n;
int sum = cnt_a * accumulate(a.begin(), a.end(), 0ll);
for (int i = n - suff; i < n; i++){
sum += a[i];
}
if (sum < x){
r = m - 1;
}
else{
l = m + 1;
}
}
cout << r << '\n';
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
solve();
}
}
2086C - Disappearing Permutation
Idea: FelixArg
Tutorial
Tutorial is loading...
Solution (FelixArg)
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n;
cin >> n;
vector<int> p(n);
for (int i = 0; i < n; i++){
cin >> p[i];
p[i]--;
}
set<int> X;
for (int i = 0; i < n; i++){
int d;
cin >> d;
d--;
while(!X.contains(d)){
X.insert(d);
d = p[d];
}
cout << X.size() << ' ';
}
cout << endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
solve();
}
}
Idea: FelixArg
Tutorial
Tutorial is loading...
Solution (FelixArg)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998'244'353;
int bpow(int x, int p){
int res = 1;
while(p){
if (p % 2){
res = (res * x) % MOD;
}
p >>= 1;
x = (x * x) % MOD;
}
return res;
}
int fact(int x){
int res = 1;
for (int i = 1; i <= x; i++){
res = (res * i) % MOD;
}
return res;
}
void solve(){
vector<int> c(26);
for (int i = 0; i < 26; i++){
cin >> c[i];
}
int s = accumulate(c.begin(), c.end(), 0ll);
vector<int> dp(s + 1);
dp[0] = 1;
for (int i = 0; i < 26; i++){
if (c[i] == 0){
continue;
}
for (int j = s; j >= 0; j--){
if (j + c[i] <= s){
dp[j + c[i]] = (dp[j + c[i]] + dp[j]) % MOD;
}
}
}
int ans = dp[s / 2] * fact(s / 2) % MOD * fact((s + 1) / 2) % MOD;
for (int i = 0; i < 26; i++){
ans = (ans * bpow(fact(c[i]), MOD - 2)) % MOD;
}
cout << ans << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
solve();
}
}
Idea: FelixArg
Tutorial
Tutorial is loading...
Solution (FelixArg)
#include<bits/stdc++.h>
using namespace std;
long long dp[40][120][2][2];
void count(vector<int>& num){
int m = num.size();
memset(dp, 0, sizeof(dp));
dp[0][0][1][0] = 1;
for (int i = 0; i < m; i++){
for (int j = 0; j < 3 * m + 2; j++){
for (int k = 0; k < 4; k++){
if (j + k >= 3 * m + 2){
break;
}
if (num[i] == k){
dp[i + 1][j + k][1][0] += dp[i][j][1][0];
dp[i + 1][j + k][0][0] += dp[i][j][0][0];
if (k == 0){
dp[i + 1][j + k][1][1] += dp[i][j][1][1];
dp[i + 1][j + k][0][1] += dp[i][j][0][1];
}
}
else if (num[i] > k){
dp[i + 1][j + k][0][0] += dp[i][j][0][0];
dp[i + 1][j + k][0][0] += dp[i][j][1][0];
if (k == 0){
dp[i + 1][j + k][0][1] += dp[i][j][0][1];
dp[i + 1][j + k][0][1] += dp[i][j][1][1];
}
}
else{
dp[i + 1][j + k][0][0] += dp[i][j][0][0];
if (k == 0){
dp[i + 1][j + k][0][1] += dp[i][j][0][1];
}
}
}
if (j + 4 < 3 * m + 2){
if (num[i] == 4){
dp[i + 1][j + 4][1][1] += dp[i][j][1][0];
dp[i + 1][j + 4][0][1] += dp[i][j][0][0];
}
else{
dp[i + 1][j + 4][0][1] += dp[i][j][0][0];
}
}
}
}
}
void solve(){
long long l, r, k;
cin >> l >> r >> k;
l--;
if (k >= 90){
cout << 0 << '\n';
return;
}
vector<long long> zeb;
long long cur = 0;
for (int i = 0; i < 60; i += 2){
cur ^= (1ll << i);
zeb.emplace_back(cur);
}
int m = zeb.size();
vector<int> num_l;
for (int i = m - 1; i >= 0; i--){
int cnt = 0;
while(l >= zeb[i]){
cnt++;
l -= zeb[i];
}
num_l.emplace_back(cnt);
}
vector<int> num_r;
for (int i = m - 1; i >= 0; i--){
int cnt = 0;
while(r >= zeb[i]){
cnt++;
r -= zeb[i];
}
num_r.emplace_back(cnt);
}
count(num_r);
long long ans = dp[m][k][0][0] + dp[m][k][0][1] + dp[m][k][1][0] + dp[m][k][1][1];
count(num_l);
ans -= dp[m][k][0][0] + dp[m][k][0][1] + dp[m][k][1][0] + dp[m][k][1][1];
cout << ans << '\n';
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
solve();
}
}
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
vector<long long> z;
void precalc()
{
z = {1ll};
while(z.back() < 1e18)
z.push_back(4 * z.back() + 1);
}
map<pair<long long, long long>, long long> dp;
long long get(long long r, long long x)
{
if(dp.count(make_pair(r, x))) return dp[make_pair(r, x)];
long long& d = dp[make_pair(r, x)];
if(x > 4 * z.size()) return d = 0;
if(x < 0) return d = 0;
if(r == 0) return d = 0;
if(r == 1)
{
if(x == 0) return d = 1;
return d = 0;
}
auto it = lower_bound(z.begin(), z.end(), r);
--it;
long long y = *it;
return d = get(y, x) + get(r - y, x - 1);
}
int main()
{
precalc();
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
long long l, r, x;
cin >> l >> r >> x;
cout << get(r + 1, x) - get(l, x) << endl;
}
}
Idea: Valentin_E
Tutorial
Tutorial is loading...
Solution (FelixArg)
#include<bits/stdc++.h>
using namespace std;
#define int long long
bool is_palindrom(const string& s){
int n = s.size();
for (int i = 0; i < n / 2; i++){
if (s[i] != s[n - i - 1]){
return false;
}
}
return true;
}
bool check_pattern(const string& s){
int n = s.size();
char a = 'a', b = 'b';
int cnt_a = 0, cnt_b = 0;
for (int i = 0; i < n; i++){
if (s[i] == a){
cnt_a++;
}
else{
cnt_b++;
}
}
if (cnt_a % 2 == 1){
swap(cnt_a, cnt_b);
swap(a, b);
}
if (s[n / 2] != b){
return false;
}
if (!is_palindrom(s)){
return false;
}
cnt_b--;
cnt_a /= 2;
cnt_b /= 2;
if (cnt_a > cnt_b){
swap(cnt_a, cnt_b);
swap(a, b);
}
if (s[0] == a){
cnt_a--;
}
else{
cnt_b--;
}
for (int i = 1; i < n / 2; i++){
if (s[i] == s[i - 1]){
if (cnt_a == 0){
return true;
}
return false;
}
if (s[i] == a){
cnt_a--;
}
else{
cnt_b--;
}
}
return true;
}
pair<int, int> find_valid_move_odd(string s){
int n = s.size();
for (int i = 0; i < n; i++){
for (int j = i; j < n; j++){
swap(s[i], s[j]);
if (check_pattern(s)){
return {i, j};
}
swap(s[i], s[j]);
}
}
return {-1, -1};
}
pair<int, int> find_valid_move_even(string s){
int n = s.size();
for (int i = n - 1; i >= 0; i--){
for (int j = 0; j <= i; j++){
if (s[i] == s[j] && i != j){
continue;
}
if (i == j && i != n - 1){
continue;
}
swap(s[i], s[j]);
int cnt = 0;
s += 'a';
for (int k = n; k >= 0; k--){
for (int l = 0; l <= k; l++){
if (s[k] == s[l] && k != l){
continue;
}
if (k == l && k != n){
continue;
}
swap(s[k], s[l]);
if (s[k] == s[n - k] && s[l] == s[n - l] && s[i] == s[n - i] && s[j] == s[n - j] && check_pattern(s)){
cnt++;
swap(s[k], s[l]);
break;
}
swap(s[k], s[l]);
}
if (cnt == 1){
break;
}
}
s.pop_back();
if (cnt == 1){
s += 'b';
for (int k = n; k >= 0; k--){
for (int l = 0; l <= k; l++){
if (s[k] == s[l] && k != l){
continue;
}
if (k == l && k != n){
continue;
}
swap(s[k], s[l]);
if (s[k] == s[n - k] && s[l] == s[n - l] && s[i] == s[n - i] && s[j] == s[n - j] && check_pattern(s)){
return {i, j};
}
swap(s[k], s[l]);
}
}
s.pop_back();
}
swap(s[i], s[j]);
}
}
return {-1, -1};
}
void solve(){
string t = "";
while(1){
char ch;
cin >> ch;
if (ch == '0'){
break;
}
t += ch;
if (t.size() % 2 == 1){
auto [l, r] = find_valid_move_odd(t);
swap(t[l], t[r]);
cout << l + 1 << ' ' << r + 1 << endl;
}
else{
auto [l, r] = find_valid_move_even(t);
swap(t[l], t[r]);
cout << l + 1 << ' ' << r + 1 << endl;
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
}
Solution (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
const int N = 100;
bool dp[N][N];
pair<int, int> nxt[N][N][2];
bitset<N> cur;
bitset<N> form[N][N];
int main(){
forn(i, N) forn(j, N) dp[i][j] = (i + j) % 2;
for (int len = 1; len < N; len += 2){
forn(x, len + 1){
int y = len - x;
int nx = x, ny = y;
int i = 0;
while (nx > 1 || ny > 1){
if (nx > 1){
nx -= 2;
++i;
}
if (ny > 1){
form[x][y][i] = form[x][y][len - i - 1] = 1;
ny -= 2;
++i;
}
}
if (ny > 0){
form[x][y][i] = 1;
}
}
}
for (int len = N - 3; len >= 1; len -= 2){
forn(x, len + 1){
int y = len - x;
cur = form[x][y];
forn(c, 2){
cur[len] = c;
bool found = false;
forn(l, len + 1){
forn(r, l + 1){
if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip();
bool ok = true;
forn(d, 2){
cur[len + 1] = d;
int nx = x + (c == 0) + (d == 0);
int ny = y + (c == 1) + (d == 1);
if ((cur ^ form[nx][ny]).count() > 2){
ok = false;
break;
}
}
if (ok){
found = true;
nxt[x][y][c] = {l, r};
}
if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip();
if (found) break;
}
if (found) break;
}
if (!found){
dp[x][y] = false;
break;
}
}
}
}
string s;
cur.reset();
for (int i = 0;; ++i){
cin >> s;
if (s == "0") break;
int c = s[0] - 'a';
int py = cur.count(), px = i - py;
cur[i] = c;
int nx = px + (c == 0), ny = py + (c == 1);
int l = -1, r = -1;
if (i % 2 == 1){
auto res = nxt[px][py][c];
if (res.first != res.second){
l = res.first;
r = res.second;
}
}
else{
assert(dp[nx][ny]);
bitset<N> dif = cur ^ form[nx][ny];
assert(dif.count() <= 2);
if (dif.count() == 2){
l = dif._Find_first();
r = dif._Find_next(l);
}
}
if (l == -1){
cout << 0 << " " << 0 << endl;
}
else{
cout << l + 1 << " " << r + 1 << endl;
if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip();
}
}
}




