Спасибо за участие! Надеюсь задачи вам понравились.
Идея: Galina_Basalova
Разбор
Tutorial is loading...
Решение(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
Идея: FelixArg
Разбор
Tutorial is loading...
Решение(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
Идея: FelixArg
Разбор
Tutorial is loading...
Решение(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();
}
}
Идея: FelixArg
Разбор
Tutorial is loading...
Решение(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();
}
}
Идея: FelixArg
Разбор
Tutorial is loading...
Решение(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();
}
}
Решение(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;
}
}
Идея: Valentin_E
Разбор
Tutorial is loading...



