Codeforces Round #635 (Div. 2)

A. Ichihime and Triangle

time limit per test1 second memory limit per test256 megabytes

Ichihime is the current priestess of the Mahjong Soul Temple. She claims to be human, despite her cat ears.

These days the temple is holding a math contest. Usually, Ichihime lacks interest in these things, but this time the prize for the winner is her favorite — cookies. Ichihime decides to attend the contest. Now she is solving the following problem.

You are given four positive integers a, b, c, d, such that \(a \leq b \leq c \leq d\).

Your task is to find three integers x, y, z, satisfying the following conditions:

\(a \leq x \leq b\).
\(b \leq y \leq c).
\(c \leq z \leq d\).
There exists a triangle with a positive non-zero area and the lengths of its three sides are x, y, and z.

Ichihime desires to get the cookie, but the problem seems too hard for her. Can you help her?Input

The first line contains a single integer \(t (1 \leq t \leq 1000)\) — the number of test cases.

The next t lines describe test cases. Each test case is given as four space-separated integers a, b, c, d\( (1 \leq a \leq b \leq c \leq d \leq 10^9)\).Output

For each test case, print three integers x, y, z — the integers you found satisfying the conditions given in the statement.

It is guaranteed that the answer always exists. If there are multiple answers, print any.ExampleinputCopy

4
1 3 5 7
1 5 5 7
100000 200000 300000 400000
1 1 977539810 977539810

outputCopy

3 4 5
5 5 5
182690 214748 300999
1 977539810 977539810

Note

One of the possible solutions to the first test case:

One of the possible solutions to the second test case:

签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
void solve(){
	int a,b,c,d;cin>>a>>b>>c>>d;
	cout<<b<<" "<<c<<" "<<c<<"\n";
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int T;cin>>T;
	while(T--) solve();
}

B. Kana and Dragon Quest game

time limit per test1 second memory limit per test256 megabytes

Kana was just an ordinary high school girl before a talent scout discovered her. Then, she became an idol. But different from the stereotype, she is also a gameholic.

One day Kana gets interested in a new adventure game called Dragon Quest. In this game, her quest is to beat a dragon.

The dragon has a hit point of x initially. When its hit point goes to 0 or under 0, it will be defeated. In order to defeat the dragon, Kana can cast the two following types of spells.

Void AbsorptionAssume that the dragon's current hit point is h, after casting this spell its hit point will become \left\lfloor \frac{h}{2} \right\rfloor + 10. Here \left\lfloor \frac{h}{2} \right\rfloor denotes h divided by two, rounded down.
Lightning StrikeThis spell will decrease the dragon's hit point by 10. Assume that the dragon's current hit point is h, after casting this spell its hit point will be lowered to h-10.

Due to some reasons Kana can only cast no more than n Void Absorptions and m Lightning Strikes. She can cast the spells in any order and doesn't have to cast all the spells. Kana isn't good at math, so you are going to help her to find out whether it is possible to defeat the dragon.Input

The first line contains a single integer t\( (1 \leq t \leq 1000)\) — the number of test cases.

The next t lines describe test cases. For each test case the only line contains three integers x, n, m \((1\le x \le 10^5, 0\le n,m\le30) \) — the dragon's intitial hit point, the maximum number of Void Absorptions and Lightning Strikes Kana can cast respectively.Output

If it is possible to defeat the dragon, print "YES" (without quotes). Otherwise, print "NO" (without quotes).

You can print each letter in any case (upper or lower).ExampleinputCopy

outputCopy

YES
NO
NO
YES
YES
YES
YES

Note

One possible casting sequence of the first test case is shown below:

Void Absorption \left\lfloor \frac{100}{2} \right\rfloor + 10=60.
Lightning Strike 60-10=50.
Void Absorption \left\lfloor \frac{50}{2} \right\rfloor + 10=35.
Void Absorption \left\lfloor \frac{35}{2} \right\rfloor + 10=27.
Lightning Strike 27-10=17.
Lightning Strike 17-10=7.
Lightning Strike 7-10=-3.

签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
void solve(){
	int x,n,m;cin>>x>>n>>m;
	rep(i,1,n) if(x>20) x=x/2+10;
	x-=m*10;
	puts(x>0?"NO":"YES");
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int T;cin>>T;
	while(T--) solve();
}

A. Linova and Kingdom

time limit per test2 seconds memory limit per test256 megabytes

Writing light novels is the most important thing in Linova's life. Last night, Linova dreamed about a fantastic kingdom. She began to write a light novel for the kingdom as soon as she woke up, and of course, she is the queen of it.

There are n cities and n-1 two-way roads connecting pairs of cities in the kingdom. From any city, you can reach any other city by walking through some roads. The cities are numbered from 1 to n, and the city 1 is the capital of the kingdom. So, the kingdom has a tree structure.

As the queen, Linova plans to choose exactly k cities developing industry, while the other cities will develop tourism. The capital also can be either industrial or tourism city.

A meeting is held in the capital once a year. To attend the meeting, each industry city sends an envoy. All envoys will follow the shortest path from the departure city to the capital (which is unique).

Traveling in tourism cities is pleasant. For each envoy, his happiness is equal to the number of tourism cities on his path.

In order to be a queen loved by people, Linova wants to choose k cities which can maximize the sum of happinesses of all envoys. Can you calculate the maximum sum for her?Input

The first line contains two integers n and k \((2\le n\le 2 \cdot 10^5, 1\le k< n)\) — the number of cities and industry cities respectively.

Each of the next n-1 lines contains two integers u and v \((1\le u,v\le n)\), denoting there is a road connecting city u and city v.

It is guaranteed that from any city, you can reach any other city by the roads.Output

Print the only line containing a single integer — the maximum possible sum of happinesses of all envoys.ExamplesinputCopy

outputCopy

inputCopy

outputCopy

inputCopy

outputCopy

Note

In the first example, Linova can choose cities 2, 5, 6, 7 to develop industry, then the happiness of the envoy from city 2 is 1, the happiness of envoys from cities 5, 6, 7 is 2. The sum of happinesses is 7, and it can be proved to be the maximum one.

In the second example, choosing cities 3, 4 developing industry can reach a sum of 3, but remember that Linova plans to choose exactly k cities developing industry, then the maximum sum is 2.

每个点的贡献为深度减去他子树的点数；
反向考虑，如果一个点从旅游城市变为工业城市，那么他减少的贡献就为子树内点树减去深度；

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const ll maxn=(ll)1e6+100;
const ll mod=(ll)1e9+7;
ll n,k,ans,a,b,num[maxn],dep[maxn],p[maxn];
struct Edge{ll v,w,nex;}g[maxn<<1];
ll head[maxn],edge_tot;
void init(){rep(i,0,n) head[i]=0;edge_tot=1;}
void addedge(ll u,ll v,ll w){g[edge_tot]={v,w,head[u]};head[u]=edge_tot++;}
void dfs(ll u,ll fa){
    for(ll i=head[u];i;i=g[i].nex){
        ll v=g[i].v;
        if(v!=fa){dep[v]=dep[u]+1;dfs(v,u);num[u]+=num[v]+1;}
    }
}
int main(){
    scanf("%lld%lld",&n,&k);init();
    rep(i,1,n-1){
        ll u,v;scanf("%lld%lld",&u,&v);
        addedge(u,v,1);addedge(v,u,1);
    }dep[1]=0;dfs(1,0);
    rep(i,1,n) p[i]=dep[i]-num[i];
    sort(p+1,p+1+n,greater<int>());
    rep(i,1,k) ans+=p[i];
    printf("%lld\n",ans);
}

B. Xenia and Colorful Gems

time limit per test3 seconds memory limit per test256 megabytes

Xenia is a girl being born a noble. Due to the inflexibility and harshness of her family, Xenia has to find some ways to amuse herself.

Recently Xenia has bought n_r red gems, n_g green gems and n_b blue gems. Each of the gems has a weight.

Now, she is going to pick three gems.

Xenia loves colorful things, so she will pick exactly one gem of each color.

Xenia loves balance, so she will try to pick gems with little difference in weight.

Specifically, supposing the weights of the picked gems are x, y and z, Xenia wants to find the minimum value of \((x-y)^2+(y-z)^2+(z-x)^2\). As her dear friend, can you help her?Input

The first line contains a single integer \(t (1\le t \le 100) \) — the number of test cases. Then t test cases follow.

The first line of each test case contains three integers \(n_r,n_g,n_b (1\le n_r,n_g,n_b\le 10^5) \) — the number of red gems, green gems and blue gems respectively.

The second line of each test case contains n_r integers\( r_1,r_2,\ldots,r_{n_r} (1\le r_i \le 10^9)\) — r_i is the weight of the i-th red gem.

The third line of each test case contains n_g integers \(g_1,g_2,\ldots,g_{n_g} (1\le g_i \le 10^9)\) — g_i is the weight of the i-th green gem.

The fourth line of each test case contains n_b integers \(b_1,b_2,\ldots,b_{n_b} (1\le b_i \le 10^9)) — b_i is the weight of the i-th blue gem.

It is guaranteed that\( \sum n_r \le 10^5, \sum n_g \le 10^5, \sum n_b \le 10^5\) (the sum for all test cases).Output

For each test case, print a line contains one integer — the minimum value which Xenia wants to find.ExampleinputCopy

outputCopy

14
1999999996000000002
24
24
14

Note

In the first test case, Xenia has the following gems:

If she picks the red gem with weight 7, the green gem with weight 6, and the blue gem with weight 4, she will achieve the most balanced selection with \((x-y)^2+(y-z)^2+(z-x)^2=(7-6)^2+(6-4)^2+(4-7)^2=14\).

二分乱搞

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int num[10],pro[10];
ll a[10][maxn],ans;
ll fun(ll x,ll y,ll z) {return (x-y)*(x-y)+(x-z)*(x-z)+(y-z)*(y-z);}
void check(){
    rep(i,0,num[pro[0]]-1){
        int r=a[pro[0]][i];
        int j=upper_bound(a[pro[1]],a[pro[1]]+num[pro[1]],r)-a[pro[1]]-1;
        if(j>=0){
            int k=lower_bound(a[pro[2]],a[pro[2]]+num[pro[2]],r)-a[pro[2]];
            if(k-num[pro[2]]+1>0) return;
            ll tmp=fun(a[pro[0]][i],a[pro[1]][j],a[pro[2]][k]);
            ans=min(ans,tmp);
        }
    }
}
void solve(){
    rep(i,0,2) scanf("%d",&num[i]),pro[i]=i;
    rep(i,0,2) rep(j,0,num[i]-1) scanf("%lld",&a[i][j]);
    rep(i,0,2) sort(a[i],a[i]+num[i]),num[i]=unique(a[i],a[i]+num[i])-a[i];
    ans=(ll)4e18;
    do{check();}while(next_permutation(pro+0,pro+3));
    printf("%lld\n",ans);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

C. Kaavi and Magic Spell

time limit per test2 seconds memory limit per test512 megabytes

Kaavi, the mysterious fortune teller, deeply believes that one's fate is inevitable and unavoidable. Of course, she makes her living by predicting others' future. While doing divination, Kaavi believes that magic spells can provide great power for her to see the future.

Kaavi has a string T of length m and all the strings with the prefix T are magic spells. Kaavi also has a string S of length n and an empty string A.

During the divination, Kaavi needs to perform a sequence of operations. There are two different operations:

Delete the first character of S and add it at the front of A.
Delete the first character of S and add it at the back of A.

Kaavi can perform no more than n operations. To finish the divination, she wants to know the number of different operation sequences to make A a magic spell (i.e. with the prefix T). As her assistant, can you help her? The answer might be huge, so Kaavi only needs to know the answer modulo 998\,244\,353.

Two operation sequences are considered different if they are different in length or there exists an i that their i-th operation is different.

A substring is a contiguous sequence of characters within a string. A prefix of a string S is a substring of S that occurs at the beginning of S.Input

The first line contains a string S of length n \((1 \leq n \leq 3000)\).

The second line contains a string T of length \(m (1 \leq m \leq n)\).

Both strings contain only lowercase Latin letters.Output

The output contains only one integer — the answer modulo 998\,244\,353.ExamplesinputCopy

abab
ba

outputCopy

inputCopy

defineintlonglong
signedmain

outputCopy

inputCopy

rotator
rotator

outputCopy

inputCopy

cacdcdbbbb
bdcaccdbbb

outputCopy

Note

The first test:

The red ones are the magic spells. In the first operation, Kaavi can either add the first character "a" at the front or the back of A, although the results are the same, they are considered as different operations. So the answer is \(6\times2=12\).

区间DP裸题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=998244353;
char s[maxn],t[maxn];
int n,m;
ll dp[3030][3030],ans=0;
int main(){
	scanf("%s%s",s+1,t+1);
	n=strlen(s+1);m=strlen(t+1);
	rep(i,1,n) if(i>m||s[1]==t[i]) dp[i][i]=1;
	rep(i,2,n) rep(l,1,n-i+2){
		int r=l+i-2;
		if(l>1&&((l-1<=m&&s[i]==t[l-1])||l-1>m)) dp[l-1][r]=(dp[l-1][r]+dp[l][r])%mod;
		if(r+1<=n&&((r+1<=m&&s[i]==t[r+1])||r+1>m)) dp[l][r+1]=(dp[l][r+1]+dp[l][r])%mod;
	} rep(i,m,n) ans=(ans+2*dp[1][i]%mod)%mod;
	printf("%lld\n",ans);
}

Edwiv

永远年轻，永远热泪盈眶

Codeforces Round #635 (Div. 2)

A. Ichihime and Triangle

签到

B. Kana and Dragon Quest game

签到

A. Linova and Kingdom

每个点的贡献为深度减去他子树的点数；
反向考虑，如果一个点从旅游城市变为工业城市，那么他减少的贡献就为子树内点树减去深度；

B. Xenia and Colorful Gems

二分乱搞

C. Kaavi and Magic Spell

区间DP裸题

A. Ichihime and Triangle

签到

B. Kana and Dragon Quest game

签到

A. Linova and Kingdom

每个点的贡献为深度减去他子树的点数；反向考虑，如果一个点从旅游城市变为工业城市，那么他减少的贡献就为子树内点树减去深度；

B. Xenia and Colorful Gems

二分乱搞

C. Kaavi and Magic Spell

区间DP裸题

每个点的贡献为深度减去他子树的点数；
反向考虑，如果一个点从旅游城市变为工业城市，那么他减少的贡献就为子树内点树减去深度；