Codeforces Round #570 (Div. 3)

A. Nearest Interesting Number

time limit per test1 second memory limit per test256 megabytes

Polycarp knows that if the sum of the digits of a number is divisible by 33, then the number itself is divisible by 33. He assumes that the numbers, the sum of the digits of which is divisible by 44, are also somewhat interesting. Thus, he considers a positive integer nn interesting if its sum of digits is divisible by 44.

Help Polycarp find the nearest larger or equal interesting number for the given number aa. That is, find the interesting number nn such that n≥an≥a and nn is minimal.Input

The only line in the input contains an integer aa (1≤a≤10001≤a≤1000).Output

Print the nearest greater or equal interesting number for the given number aa. In other words, print the interesting number nn such that n≥an≥a and nn is minimal.
Examplesinput

432

output

435

input

99

output

103

input

237

output

237

input

42

output

44

签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,a[maxn];
int work(int x){
	int sum=0;
	while(x){
		sum+=x%10;
		x/=10;
	}
	return sum;
}
int main(){
	int a;cin>>a;
	rep(i,a,5000) if(work(i)%4==0) return printf("%d\n",i),0;
}


B. Equalize Prices

time limit per test1 second memory limit per test256 megabytes

There are nn products in the shop. The price of the ii-th product is aiai. The owner of the shop wants to equalize the prices of all products. However, he wants to change prices smoothly.

In fact, the owner of the shop can change the price of some product ii in such a way that the difference between the old price of this product aiai and the new price bibi is at most kk. In other words, the condition |ai−bi|≤k|ai−bi|≤k should be satisfied (|x||x| is the absolute value of xx).

He can change the price for each product not more than once. Note that he can leave the old prices for some products. The new price bibiof each product ii should be positive (i.e. bi>0bi>0 should be satisfied for all ii from 11 to nn).

Your task is to find out the maximum possible equal price BB of all productts with the restriction that for all products the condiion |ai−B|≤k|ai−B|≤k should be satisfied (where aiai is the old price of the product and BB is the same new price of all products) or report that it is impossible to find such price BB.

Note that the chosen price BB should be integer.

You should answer qq independent queries.Input

The first line of the input contains one integer qq (1≤q≤1001≤q≤100) — the number of queries. Each query is presented by two lines.

The first line of the query contains two integers nn and kk (1≤n≤100,1≤k≤1081≤n≤100,1≤k≤108) — the number of products and the value kk. The second line of the query contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1081≤ai≤108), where aiai is the price of the ii-th product.Output

Print qq integers, where the ii-th integer is the answer BB on the ii-th query.

If it is impossible to equalize prices of all given products with restriction that for all products the condition |ai−B|≤k|ai−B|≤k should be satisfied (where aiai is the old price of the product and BB is the new equal price of all products), print -1. Otherwise print the maximum possible equal price of all products.
Exampleinput

4
5 1
1 1 2 3 1
4 2
6 4 8 5
2 2
1 6
3 5
5 2 5

output

2
6
-1
7

Note

In the first example query you can choose the price B=2B=2. It is easy to see that the difference between each old price and each new price B=2B=2 is no more than 11.

In the second example query you can choose the price B=6B=6 and then all the differences between old and new price B=6B=6 will be no more than 22.

In the third example query you cannot choose any suitable price BB. For any value BB at least one condition out of two will be violated: |1−B|≤2|1−B|≤2, |6−B|≤2|6−B|≤2.

In the fourth example query all values BB between 11 and 77 are valid. But the maximum is 77, so it’s the answer.

签到,最优解肯定是最小的数+k,然后判断一下最大的数有没有超范围就好了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,k,a[110];
int main(){
	int q;cin>>q;
	while(q--){
		cin>>n>>k;
		int minx=0x7fffffff;
		int maxx=0;
		rep(i,1,n){
			int x;scanf("%d",&x);
			minx=min(minx,x);
			maxx=max(maxx,x);
		}
		int ans=k+minx;
		if(abs(ans-maxx)<=k) printf("%d\n",ans);
		else puts("-1");
	}
}


C. Computer Game

time limit per test3 seconds memory limit per test256 megabytes

Vova is playing a computer game. There are in total nn turns in the game and Vova really wants to play all of them. The initial charge of his laptop battery (i.e. the charge before the start of the game) is kk.

During each turn Vova can choose what to do:

  • If the current charge of his laptop battery is strictly greater than aa, Vova can just play, and then the charge of his laptop battery will decrease by aa;
  • if the current charge of his laptop battery is strictly greater than bb (b<ab<a), Vova can play and charge his laptop, and then the charge of his laptop battery will decrease by bb;
  • if the current charge of his laptop battery is less than or equal to aa and bb at the same time then Vova cannot do anything and loses the game.

Regardless of Vova’s turns the charge of the laptop battery is always decreases.

Vova wants to complete the game (Vova can complete the game if after each of nn turns the charge of the laptop battery is strictly greater than 00). Vova has to play exactly nn turns. Among all possible ways to complete the game, Vova wants to choose the one where the number of turns when he just plays (first type turn) is the maximum possible. It is possible that Vova cannot complete the game at all.

Your task is to find out the maximum possible number of turns Vova can just play (make the first type turn) or report that Vova cannot complete the game.

You have to answer qq independent queries.Input

The first line of the input contains one integer qq (1≤q≤1051≤q≤105) — the number of queries. Each query is presented by a single line.

The only line of the query contains four integers k,n,ak,n,a and bb (1≤k,n≤109,1≤b<a≤1091≤k,n≤109,1≤b<a≤109) — the initial charge of Vova’s laptop battery, the number of turns in the game and values aa and bb, correspondingly.Output

For each query print one integer: -1 if Vova cannot complete the game or the maximum number of turns Vova can just play (make the first type turn) otherwise.
Exampleinput

6
15 5 3 2
15 5 4 3
15 5 2 1
15 5 5 1
16 7 5 2
20 5 7 3

output

4
-1
5
2
0
1

Note

In the first example query Vova can just play 44 turns and spend 1212 units of charge and then one turn play and charge and spend 22 more units. So the remaining charge of the battery will be 11.

In the second example query Vova cannot complete the game because even if he will play and charge the battery during each turn then the charge of the laptop battery will be 00 after the last turn.

签到题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,a[maxn];
int main(){
	int T;cin>>T;
	while(T--){
		ll k,n,a,b;scanf("%lld%lld%lld%lld",&k,&n,&a,&b);
		ll re=k-n*b,c=a-b;
		if(re<=0) puts("-1");
		else{
			ll ans=re/c;
			if(re%c==0) ans--;
			printf("%lld\n",max(0ll,min(n,ans)));
		}
	}
}


D. Candy Box (easy version)

time limit per test3 seconds memory limit per test256 megabytes

This problem is actually a subproblem of problem G from the same contest.

There are nn candies in a candy box. The type of the ii-th candy is aiai (1≤ai≤n1≤ai≤n).

You have to prepare a gift using some of these candies with the following restriction: the numbers of candies of each type presented in a gift should be all distinct (i. e. for example, a gift having two candies of type 11 and two candies of type 22 is bad).

It is possible that multiple types of candies are completely absent from the gift. It is also possible that not all candies of some types will be taken to a gift.

Your task is to find out the maximum possible size of the single gift you can prepare using the candies you have.

You have to answer qq independent queries.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.Input

The first line of the input contains one integer qq (1≤q≤2⋅1051≤q≤2⋅105) — the number of queries. Each query is represented by two lines.

The first line of each query contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of candies.

The second line of each query contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n), where aiai is the type of the ii-th candy in the box.

It is guaranteed that the sum of nn over all queries does not exceed 2⋅1052⋅105.Output

For each query print one integer — the maximum possible size of the single gift you can compose using candies you got in this query with the restriction described in the problem statement.
Exampleinput

3
8
1 4 8 4 5 6 3 8
16
2 1 3 3 4 3 4 4 1 3 2 2 2 4 1 1
9
2 2 4 4 4 7 7 7 7

output

3
10
9

Note

In the first query, you can prepare a gift with two candies of type 88 and one candy of type 55, totalling to 33 candies.

Note that this is not the only possible solution — taking two candies of type 44 and one candy of type 66 is also valid.

显然,最优解一定是从大到小逐个减1直到不能减,排个序就好啦

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,a[maxn];
void work(){
	scanf("%d",&n);
	rep(i,1,n) a[i]=0;
	rep(i,1,n){
		int x;scanf("%d",&x);
		a[x]++;
	}
	vector<int> vec;
	rep(i,1,n) if(a[i]) vec.pb(a[i]);
	sort(vec.begin(),vec.end(),greater<int>());
	//for(auto u:vec) cout<<u<<endl;
	int pre=0x7fffffff,ans=0;
	for(auto u:vec){
		if(u<=pre){
			ans+=u;
			pre=u-1;
		}
		else ans+=pre--;
		if(!pre) break;
	}
	printf("%d\n",ans);
}
int main(){
	int T;cin>>T;
	while(T--) work();
}


E. Subsequences (easy version)

time limit per test2 seconds memory limit per test256 megabytes

The only difference between the easy and the hard versions is constraints.

A subsequence is a string that can be derived from another string by deleting some or no symbols without changing the order of the remaining symbols. Characters to be deleted are not required to go successively, there can be any gaps between them. For example, for the string “abaca” the following strings are subsequences: “abaca”, “aba”, “aaa”, “a” and “” (empty string). But the following strings are not subsequences: “aabaca”, “cb” and “bcaa”.

You are given a string ss consisting of nn lowercase Latin letters.

In one move you can take any subsequence tt of the given string and add it to the set SS. The set SS can’t contain duplicates. This move costs n−|t|n−|t|, where |t||t| is the length of the added subsequence (i.e. the price equals to the number of the deleted characters).

Your task is to find out the minimum possible total cost to obtain a set SS of size kk or report that it is impossible to do so.Input

The first line of the input contains two integers nn and kk (1≤n,k≤1001≤n,k≤100) — the length of the string and the size of the set, correspondingly.

The second line of the input contains a string ss consisting of nn lowercase Latin letters.Output

Print one integer — if it is impossible to obtain the set SS of size kk, print -1. Otherwise, print the minimum possible total cost to do it.
Examplesinput

4 5
asdf

output

4

input

5 6
aaaaa

output

15

input

5 7
aaaaa

output

-1

input

10 100
ajihiushda

output

233

Note

In the first example we can generate SS = { “asdf”, “asd”, “adf”, “asf”, “sdf” }. The cost of the first element in SS is 00 and the cost of the others is 11. So the total cost of SS is 44.

考虑到k只有100暴力

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,k;
string s;
set<string> st;
queue<string> q;
int main(){
	cin>>n>>k>>s;
	q.push(s); st.insert(s);
	int ans=0;
	while(!q.empty()&&(int)st.size()<k){
		string t=q.front(); q.pop();
		rep(i,0,(int)t.length()-1){
			string tt=t;
			tt.erase(i,1);
			if((!st.count(tt))&&(int)st.size()<k){
				st.insert(tt);
				q.push(tt);
				ans+=n-tt.length();
			}
		}
	}
	if((int)st.size()<k) puts("-1");
	else printf("%d\n",ans);
}


F. Topforces Strikes Back

time limit per test3 seconds memory limit per test256 megabytes

One important contest will take place on the most famous programming platform (Topforces) very soon!

The authors have a pool of nn problems and should choose at most three of them into this contest. The prettiness of the ii-th problem is aiai. The authors have to compose the most pretty contest (in other words, the cumulative prettinesses of chosen problems should be maximum possible).

But there is one important thing in the contest preparation: because of some superstitions of authors, the prettinesses of problems cannot divide each other. In other words, if the prettinesses of chosen problems are x,y,zx,y,z, then xx should be divisible by neither yy, nor zz, yy should be divisible by neither xx, nor zz and zz should be divisible by neither xx, nor yy. If the prettinesses of chosen problems are xx and yy then neither xx should be divisible by yy nor yy should be divisible by xx. Any contest composed from one problem is considered good.

Your task is to find out the maximum possible total prettiness of the contest composed of at most three problems from the given pool.

You have to answer qq independent queries.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.Input

The first line of the input contains one integer qq (1≤q≤2⋅1051≤q≤2⋅105) — the number of queries.

The first line of the query contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of problems.

The second line of the query contains nn integers a1,a2,…,ana1,a2,…,an (2≤ai≤2⋅1052≤ai≤2⋅105), where aiai is the prettiness of the ii-th problem.

It is guaranteed that the sum of nn over all queries does not exceed 2⋅1052⋅105.Output

For each query print one integer — the maximum possible cumulative prettiness of the contest composed of at most three problems from the given pool of problems in the query.
Exampleinput

3
4
5 6 15 30
4
10 6 30 15
3
3 4 6

output

30
31
10

暴力枚举最大的三个互不整除的数,大部分情况下这就是答案;
但是有一种情况就是如果说只能挑出一个最大的数,并且最大的数可以被2,3,5整除且原数组中有mx/2,mx/3,mx/5,那这三个数加起来就比原来的mx更大。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n;
int main(){
	int T;cin>>T;
	while(T--){
		scanf("%d",&n);
		set<int,greater<int> > st;
		rep(i,1,n){
			int x;scanf("%d",&x);st.insert(x);
		}
		int ans=0;
		int mx=*st.begin();
		if(mx%2==0&&mx%3==0&&mx%5==0&&st.count(mx/2)&&st.count(mx/3)&&st.count(mx/5))
			ans=mx/2+mx/3+mx/5;	
		vector<int> res;
		while(!st.empty()&&(int)res.size()<3){
			int x=*st.begin();
			st.erase(st.begin());
			int flag=1;
			for(auto u:res) flag&=(u%x!=0);
			if(flag) res.pb(x);
		}
		ans=max(ans,accumulate(res.begin(),res.end(),0));
		printf("%d\n",ans);
	}
}

 


G. Candy Box (hard version)

time limit per test2 seconds memory limit per test256 megabytes

This problem is a version of problem D from the same contest with some additional constraints and tasks.

There are nn candies in a candy box. The type of the ii-th candy is aiai (1≤ai≤n1≤ai≤n).

You have to prepare a gift using some of these candies with the following restriction: the numbers of candies of each type presented in a gift should be all distinct (i. e. for example, a gift having two candies of type 11 and two candies of type 22 is bad).

It is possible that multiple types of candies are completely absent from the gift. It is also possible that not all candies of some types will be taken to a gift.

You really like some of the candies and don’t want to include them into the gift, but you want to eat them yourself instead. For each candy, a number fifi is given, which is equal to 00 if you really want to keep ii-th candy for yourself, or 11 if you don’t mind including it into your gift. It is possible that two candies of the same type have different values of fifi.

You want your gift to be as large as possible, but you don’t want to include too many of the candies you want to eat into the gift. So, you want to calculate the maximum possible number of candies that can be included into a gift, and among all ways to choose maximum number of candies, you want to maximize the number of candies having fi=1fi=1 in your gift.

You have to answer qq independent queries.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.Input

The first line of the input contains one integer qq (1≤q≤2⋅1051≤q≤2⋅105) — the number of queries.

The first line of each query contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of candies.

Then nn lines follow, each containing two integers aiai and fifi (1≤ai≤n1≤ai≤n, 0≤fi≤10≤fi≤1), where aiai is the type of the ii-th candy, and fifidenotes whether you want to keep the ii-th candy for yourself (00 if you want to keep it, 11 if you don’t mind giving it away).

It is guaranteed that the sum of nn over all queries does not exceed 2⋅1052⋅105.Output

For each query print two integers:

  • the maximum number of candies in a gift you can compose, according to the constraints in the statement;
  • the maximum number of candies having fi=1fi=1 in a gift you can compose that contains the maximum possible number of candies.

Exampleinput

3
8
1 0
4 1
2 0
4 1
5 1
6 1
3 0
2 0
4
1 1
1 1
2 1
2 1
9
2 0
2 0
4 1
4 1
4 1
7 0
7 1
7 0
7 1

output

3 3
3 3
9 5

Note

In the first query, you can include two candies of type 44 and one candy of type 55. All of them have fi=1fi=1 and you don’t mind giving them away as part of the gift.

加了个f的条件,其实显然对于f我们也是可以记录一下每个数量的糖果有几个f然后暴力判的

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n;
void work(){
	scanf("%d",&n);
	vector<int> cnt(n+1),cnt_f(n+1);
	rep(i,1,n){
		int x,f;scanf("%d%d",&x,&f);
		cnt[x]++;
		if(f) cnt_f[x]++;
	}
	vector<vector<int> > type(n+1);
	rep(i,1,n) type[cnt[i]].pb(cnt_f[i]);
	int ans1=0,ans2=0;
	multiset<int> s;
	dep(i,n,1){
		for(auto u:type[i]) s.insert(u);
		if(!s.empty()){
			int z=*s.rbegin();
			ans1+=i;
			ans2+=min(i,z);
			s.erase(s.find(z));
		}
	}
	printf("%d %d\n",ans1,ans2);
}
int main(){
	int T;cin>>T;
	while(T--) work();
}


H. Subsequences (hard version)

time limit per test2 seconds memory limit per test256 megabytes

The only difference between the easy and the hard versions is constraints.

A subsequence is a string that can be derived from another string by deleting some or no symbols without changing the order of the remaining symbols. Characters to be deleted are not required to go successively, there can be any gaps between them. For example, for the string “abaca” the following strings are subsequences: “abaca”, “aba”, “aaa”, “a” and “” (empty string). But the following strings are not subsequences: “aabaca”, “cb” and “bcaa”.

You are given a string ss consisting of nn lowercase Latin letters.

In one move you can take any subsequence tt of the given string and add it to the set SS. The set SS can’t contain duplicates. This move costs n−|t|n−|t|, where |t||t| is the length of the added subsequence (i.e. the price equals to the number of the deleted characters).

Your task is to find out the minimum possible total cost to obtain a set SS of size kk or report that it is impossible to do so.Input

The first line of the input contains two integers nn and kk (1≤n≤100,1≤k≤10121≤n≤100,1≤k≤1012) — the length of the string and the size of the set, correspondingly.

The second line of the input contains a string ss consisting of nn lowercase Latin letters.Output

Print one integer — if it is impossible to obtain the set SS of size kk, print -1. Otherwise, print the minimum possible total cost to do it.
Examplesinput

4 5
asdf

output

4

input

5 6
aaaaa

output

15

input

5 7
aaaaa

output

-1

input

10 100
ajihiushda

output

233

Note

In the first example we can generate SS = { “asdf”, “asd”, “adf”, “asf”, “sdf” }. The cost of the first element in SS is 00 and the cost of the others is 11. So the total cost of SS is 44.

经典的一道字符串dp的题;很好想到,如果我们知道了每个长度的不重复子串的数量,那么这道题就很好做了。

那么既然要不重复,有一个经典的想法是维护一个二维数组 dp[pos][len] 表示 长为len且以下标pos为结尾的子串数量
如何保证不重复呢, 我们在转移的时候就需要用到一点技巧。因为在 dp[pos][len] 中,str[pos]这个字符是必须填上的,直接加 dp[pos-1][len-1]会有重复,那如果我们枚举len-1这一位中a-z每个字母,那么也就是累加 dp[pos[a-z]][len-1]就可以了。

现在要做的就是考虑如何O(1)转移,很容易想到维护一个二维数组 last[i][j],记录的是 1-i这个前缀中字母j(a-z)最后出现的下标

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const ll INF=(int)1e12;
int n;;
ll k,dp[110][110],ans;
int last[110][26];
char str[110];
int main(){
	cin>>n>>k; scanf("%s",str+1);
	k--; //整个s都放进去
	memset(last,-1,sizeof(last)); //1-i中字母j最后出现的下标
	rep(i,1,n){
		rep(j,0,25) if(i>1) last[i][j]=last[i-1][j];
		last[i][str[i]-'a']=i;
	}
	rep(i,1,n) dp[i][1]=1; //长为j且以下标i为结尾的str的子串数量
	rep(len,2,n-1) rep(pos,2,n) rep(j,0,25) if(last[pos-1][j]!=-1)
		dp[pos][len]=dp[pos][len]+dp[last[pos-1][j]][len-1];
	dep(len,n-1,1){
		ll cnt=0;
		rep(j,0,25) if(last[n][j]!=-1) cnt+=dp[last[n][j]][len];
		if(cnt>=k){
			ans+=k*(n-len);
			k=0;
			break;
		}
		else{
			k-=cnt;
			ans+=cnt*(n-len);
		}
	}
	if(k==1) k--,ans+=n;
	if(k) puts("-1");
	else printf("%lld\n",ans);
}

发表评论,支持MarkDown语法