Codeforces Round #555 (Div. 3)

A. Reachable Numbers

time limit per test1 second . memory limit per test256 megabytes

Let’s denote a function 𝑓(𝑥)f(x) in such a way: we add 11 to 𝑥x, then, while there is at least one trailing zero in the resulting number, we remove that zero. For example,

  • 𝑓(599)=6f(599)=6: 599+1=600→60→6599+1=600→60→6;
  • 𝑓(7)=8f(7)=8: 7+1=87+1=8;
  • 𝑓(9)=1f(9)=1: 9+1=10→19+1=10→1;
  • 𝑓(10099)=101f(10099)=101: 10099+1=10100→1010→10110099+1=10100→1010→101.

We say that some number 𝑦y is reachable from 𝑥x if we can apply function 𝑓f to 𝑥x some (possibly zero) times so that we get 𝑦y as a result. For example, 102102 is reachable from 1009810098 because 𝑓(𝑓(𝑓(10098)))=𝑓(𝑓(10099))=𝑓(101)=102f(f(f(10098)))=f(f(10099))=f(101)=102; and any number is reachable from itself.

You are given a number 𝑛n; your task is to count how many different numbers are reachable from 𝑛n.Input

The first line contains one integer 𝑛n (1≤𝑛≤1091≤n≤109).Output

Print one integer: the number of different numbers that are reachable from 𝑛n.
Examples
input

1098

output

20

input

10

output

19

Note

The numbers that are reachable from 10981098 are:

1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,1098,10991,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,1098,1099.

模拟题,签到;注意处理n本来就是10的倍数的情况

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=(int)1e5+100;
int main(){
	int n,ans=9;cin>>n;
	if(n%10==0) ans++,n++;
	while(n>=10){
		ans++,n++;
		while(n%10==0) n/=10;
	}
	cout<<ans<<endl;
}


B. Long Number

time limit per test2 seconds memory limit per test256 megabytes

You are given a long decimal number 𝑎a consisting of 𝑛n digits from 11 to 99. You also have a function 𝑓f that maps every digit from 11 to 99 to some (possibly the same) digit from 11 to 99.

You can perform the following operation no more than once: choose a non-empty contiguous subsegment of digits in 𝑎a, and replace each digit 𝑥x from this segment with 𝑓(𝑥)f(x). For example, if 𝑎=1337a=1337, 𝑓(1)=1f(1)=1, 𝑓(3)=5f(3)=5, 𝑓(7)=3f(7)=3, and you choose the segment consisting of three rightmost digits, you get 15531553 as the result.

What is the maximum possible number you can obtain applying this operation no more than once?Input

The first line contains one integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — the number of digits in 𝑎a.

The second line contains a string of 𝑛n characters, denoting the number 𝑎a. Each character is a decimal digit from 11 to 99.

The third line contains exactly 99 integers 𝑓(1)f(1), 𝑓(2)f(2), …, 𝑓(9)f(9) (1≤𝑓(𝑖)≤91≤f(i)≤9).Output

Print the maximum number you can get after applying the operation described in the statement no more than once.
Examples
input

4 
1337
1 2 5 4 6 6 3 1 9

output

1557

input

5 
11111
9 8 7 6 5 4 3 2 1

output

99999

input

2 
33
1 1 1 1 1 1 1 1 1

output

33

贪心模拟

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=(int)1e5+100;
int main(){
	int n;cin>>n;
	string s;cin>>s;
	int a[10];rep(i,1,9) cin>>a[i];
	int flag=0;
	for(int i=0;i<n;++i){
		int num=s[i]-'0';
		if(flag==0){
			if(a[num]>num){flag=1;s[i]=a[num]+'0';}
		}
		else{
			if(a[num]<num) break;
			else s[i]=a[num]+'0';
		}
	}
	cout<<s<<endl;
}


C1. Increasing Subsequence (easy version)

time limit per test2 seconds memory limit per test256 megabytes

The only difference between problems C1 and C2 is that all values in input of problem C1 are distinct (this condition may be false for problem C2).

You are given a sequence 𝑎a consisting of 𝑛n integers. All these integers are distinct, each value from 11 to 𝑛n appears in the sequence exactly once.

You are making a sequence of moves. During each move you must take either the leftmost element of the sequence or the rightmost element of the sequence, write it down and remove it from the sequence. Your task is to write down a strictly increasing sequence, and among all such sequences you should take the longest (the length of the sequence is the number of elements in it).

For example, for the sequence [2,1,5,4,3][2,1,5,4,3] the answer is 44 (you take 22 and the sequence becomes [1,5,4,3][1,5,4,3], then you take the rightmost element 33 and the sequence becomes [1,5,4][1,5,4], then you take 44 and the sequence becomes [1,5][1,5] and then you take 55 and the sequence becomes [1][1], the obtained increasing sequence is [2,3,4,5][2,3,4,5]).Input

The first line of the input contains one integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — the number of elements in 𝑎a.

The second line of the input contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤𝑛1≤ai≤n), where 𝑎𝑖ai is the 𝑖i-th element of 𝑎a. All these integers are pairwise distinct.Output

In the first line of the output print 𝑘k — the maximum number of elements in a strictly increasing sequence you can obtain.

In the second line print a string 𝑠s of length 𝑘k, where the 𝑗j-th character of this string 𝑠𝑗sj should be ‘L’ if you take the leftmost element during the 𝑗j-th move and ‘R’ otherwise. If there are multiple answers, you can print any.
Examples
input

5 
2 1 5 4 3

output

4
LRRR

input

7 
1 3 5 6 7 4 2

output

7
LRLRLLL

input

3 
1 2 3

output

3
LLL

input

4 
1 2 4 3

output

4
LLRL

Note

The first example is described in the problem statement.

C2. Increasing Subsequence (hard version)

time limit per test2 seconds memory limit per test256 megabytes

The only difference between problems C1 and C2 is that all values in input of problem C1 are distinct (this condition may be false for problem C2).

You are given a sequence 𝑎a consisting of 𝑛n integers.

You are making a sequence of moves. During each move you must take either the leftmost element of the sequence or the rightmost element of the sequence, write it down and remove it from the sequence. Your task is to write down a strictly increasing sequence, and among all such sequences you should take the longest (the length of the sequence is the number of elements in it).

For example, for the sequence [1,2,4,3,2][1,2,4,3,2] the answer is 44 (you take 11 and the sequence becomes [2,4,3,2][2,4,3,2], then you take the rightmost element 22 and the sequence becomes [2,4,3][2,4,3], then you take 33 and the sequence becomes [2,4][2,4] and then you take 44 and the sequence becomes [2][2], the obtained increasing sequence is [1,2,3,4][1,2,3,4]).Input

The first line of the input contains one integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — the number of elements in 𝑎a.

The second line of the input contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤2⋅1051≤ai≤2⋅105), where 𝑎𝑖ai is the 𝑖i-th element of 𝑎a.Output

In the first line of the output print 𝑘k — the maximum number of elements in a strictly increasing sequence you can obtain.

In the second line print a string 𝑠s of length 𝑘k, where the 𝑗j-th character of this string 𝑠𝑗sj should be ‘L’ if you take the leftmost element during the 𝑗j-th move and ‘R’ otherwise. If there are multiple answers, you can print any.
Examples
input

5 
1 2 4 3 2

output

4
LRRR

input

7 
1 3 5 6 5 4 2

output

6
LRLRRR

input

3 
2 2 2

output

1
R

input

4 
1 2 4 3

output

4
LLRR

Note

The first example is described in the problem statement.

贪心的想,每次取走两边可以取的最小的那个数,然后如果两边数字一样的话,那么选择一边之后另外一边必定不能再走了,所以此时只要判断哪边能走的最长就可以了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=(int)2e5+100;
int a[maxn];
int main(){
	int n;cin>>n; rep(i,1,n) scanf("%d",&a[i]);
	vector<char> ans;ans.clear();
	int l=1,r=n,pre=-1;
	while(1){
		if(l==r){if(a[l]>pre) ans.pb('L');break;}
		if(a[l]<a[r]){
			if(pre==-1){ans.pb('L');pre=a[l];l++;continue;}
			if(a[r]<=pre) break;
			else if(a[l]<=pre){ans.pb('R');pre=a[r];r--;}
			else {ans.pb('L');pre=a[l];l++;}
		}
		else if(a[l]>a[r]){
			if(pre==-1){ans.pb('R');pre=a[r];r--;continue;}
			if(a[l]<=pre) break;
			else if(a[r]<=pre){ans.pb('L');pre=a[l];l++;}
			else {ans.pb('R');pre=a[r];r--;}
		}
		else{
			if(a[l]<=pre) break;
			int st1=1,st2=1,pre1=a[l],pre2=a[r];
			int lt=l+1,rt=r-1;
			while(a[lt]>pre1&&lt<=n){pre1=a[lt];lt++;st1++;}
			while(a[rt]>pre2&&rt>=1){pre2=a[rt];rt--;st2++;}
			if(st1>=st2) rep(i,1,st1) ans.pb('L');
			else rep(i,1,st2) ans.pb('R');
			break;
		}
	}
	cout<<ans.size()<<endl;
	for(int i=0;i<ans.size();++i) printf("%c",ans[i]);
}


D. N Problems During K Days

time limit per test1 second memory limit per test256 megabytes

Polycarp has to solve exactly 𝑛n problems to improve his programming skill before an important programming competition. But this competition will be held very soon, most precisely, it will start in 𝑘k days. It means that Polycarp has exactly 𝑘k days for training!

Polycarp doesn’t want to procrastinate, so he wants to solve at least one problem during each of 𝑘k days. He also doesn’t want to overwork, so if he solves 𝑥x problems during some day, he should solve no more than 2𝑥2x problems during the next day. And, at last, he wants to improve his skill, so if he solves 𝑥x problems during some day, he should solve at least 𝑥+1x+1 problem during the next day.

More formally: let [𝑎1,𝑎2,…,𝑎𝑘][a1,a2,…,ak] be the array of numbers of problems solved by Polycarp. The 𝑖i-th element of this array is the number of problems Polycarp solves during the 𝑖i-th day of his training. Then the following conditions must be satisfied:

  • sum of all 𝑎𝑖ai for 𝑖i from 11 to 𝑘k should be 𝑛n;
  • 𝑎𝑖ai should be greater than zero for each 𝑖i from 11 to 𝑘k;
  • the condition 𝑎𝑖<𝑎𝑖+1≤2𝑎𝑖ai<ai+1≤2ai should be satisfied for each 𝑖i from 11 to 𝑘−1k−1.

Your problem is to find any array 𝑎a of length 𝑘k satisfying the conditions above or say that it is impossible to do it.Input

The first line of the input contains two integers 𝑛n and 𝑘k (1≤𝑛≤109,1≤𝑘≤1051≤n≤109,1≤k≤105) — the number of problems Polycarp wants to solve and the number of days Polycarp wants to train.Output

If it is impossible to find any array 𝑎a of length 𝑘k satisfying Polycarp’s rules of training, print “NO” in the first line.

Otherwise print “YES” in the first line, then print 𝑘k integers 𝑎1,𝑎2,…,𝑎𝑘a1,a2,…,ak in the second line, where 𝑎𝑖ai should be the number of problems Polycarp should solve during the 𝑖i-th day. If there are multiple answers, you can print any.
Examples
input

26 6

output

YES 
1 2 4 5 6 8

input

8 3

output

NO

input

1 1

output

YES 
1

input

9 4

output

NO

首先特判一下NO的情况,发现只有在题目数比等差数列和还小或者n=8&&k=3||n=4&&k=2的情况才是NO,其他情况都可以
之后只要构造一个等差数列然后不断从后往前填数就可以了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=(int)1e5+100;
int main(){
	ll n,k,a[maxn];cin>>n>>k;
	if(k==1){cout<<"YES\n"<<n<<endl;exit(0);}
	rep(i,1,k) {a[i]=i;n-=i;}
    if(n<0||(n==2&&k==3)||(n==1&&k==2)){cout<<"NO\n";exit(0);}
    ll t=n/k;n-=t*k; rep(i,1,k) a[i]+=t;
	while(n){
		for(int i=k;i>=1;--i){
			if(i==1||a[i]+1<=a[i-1]*2) a[i]++,n--;
			else break;
			if(n==0) break;
		}
	}
	cout<<"YES\n";
	for(int i=1;i<=k;++i) printf(i==1?"%lld":" %lld",a[i]);
	
}


E. Minimum Array

time limit per test2 seconds memory limit per test256 megabytes

You are given two arrays 𝑎a and 𝑏b, both of length 𝑛n. All elements of both arrays are from 00 to 𝑛−1n−1.

You can reorder elements of the array 𝑏b (if you want, you may leave the order of elements as it is). After that, let array 𝑐c be the array of length 𝑛n, the 𝑖i-th element of this array is 𝑐𝑖=(𝑎𝑖+𝑏𝑖)%𝑛ci=(ai+bi)%n, where 𝑥%𝑦x%y is 𝑥x modulo 𝑦y.

Your task is to reorder elements of the array 𝑏b to obtain the lexicographically minimum possible array 𝑐c.

Array 𝑥x of length 𝑛n is lexicographically less than array 𝑦y of length 𝑛n, if there exists such 𝑖i (1≤𝑖≤𝑛1≤i≤n), that 𝑥𝑖<𝑦𝑖xi<yi, and for any 𝑗j (1≤𝑗<𝑖1≤j<i) 𝑥𝑗=𝑦𝑗xj=yj.Input

The first line of the input contains one integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — the number of elements in 𝑎a, 𝑏b and 𝑐c.

The second line of the input contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (0≤𝑎𝑖<𝑛0≤ai<n), where 𝑎𝑖ai is the 𝑖i-th element of 𝑎a.

The third line of the input contains 𝑛n integers 𝑏1,𝑏2,…,𝑏𝑛b1,b2,…,bn (0≤𝑏𝑖<𝑛0≤bi<n), where 𝑏𝑖bi is the 𝑖i-th element of 𝑏b.Output

Print the lexicographically minimum possible array 𝑐c. Recall that your task is to reorder elements of the array 𝑏b and obtain the lexicographically minimum possible array 𝑐c, where the 𝑖i-th element of 𝑐c is 𝑐𝑖=(𝑎𝑖+𝑏𝑖)%𝑛ci=(ai+bi)%n.
Examples
input

4 
0 1 2 1
3 2 1 1

output

1 0 0 2 

input

7 
2 5 1 5 3 4 3
2 4 3 5 6 5 1

output

0 0 0 1 0 2 4 

其实就是可以很简单的二分题,但是场上脑子抽了写了个线段树二分,没来得及交,赛后30行就解决了

线段树二分

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define delf int m=(l+r)>>1
const int maxn=(int)2e5+100;
int n,a[maxn],b[maxn],c[maxn],num[maxn];
int sum[maxn<<2],lazy[maxn<<2];
void pushup(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
void build(int l,int r,int rt){
	if(l==r){sum[rt]=0;return;}
	delf;
	build(lson);build(rson);pushup(rt);
}
void add(int L,int c,int l,int r,int rt){
	if(l==r){sum[rt]+=c;return;}
	delf;
	if(L<=m) add(L,c,lson);
	else add(L,c,rson);
	pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
	if(L<=l&&r<=R) return sum[rt];
	delf;int ans=0;
	if(L<=m) ans+=query(L,R,lson);
	if(R>m) ans+=query(L,R,rson);
	return ans;
}
int dq(int L,int R,int l,int r,int rt){
	if(L==R) return R;
	int mid=L+R>>1;
	if(query(L,mid,1,n,1)) return dq(L,mid,1,n,1);
	else return dq(mid+1,R,1,n,1);
}
int main(){
	cin>>n;
	rep(i,1,n) scanf("%d",&a[i]);
	rep(i,1,n){
		int x;
		scanf("%d",&x);
		num[x]++;
	}
	build(1,n,1);
	rep(i,0,n-1) if(num[i]) add(i+1,num[i],1,n,1);
	rep(i,1,n){
		int ans=(n-a[i])%n,res;
		if(query(ans+1,n,1,n,1)){
			res=dq(ans+1,n,1,n,1);
			num[res-1]--;add(res,-1,1,n,1);
			printf("%d ",(res-1+a[i])%n);
		}
		else{
			res=dq(1,ans,1,n,1);
			num[res-1]--;add(res,-1,1,n,1);
			printf("%d ",(res-1+a[i])%n);
		}
	}
}

multiset

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=(int)2e5+100;
int a[maxn];
multiset<int> s;
int main(){
	int n;cin>>n;
	rep(i,1,n) scanf("%d",&a[i]);
	for(int i=1,x;i<=n;++i){scanf("%d",&x);s.insert(x);}
	rep(i,1,n){
		int ans=(n-a[i])%n;
		auto num=s.lower_bound(ans)!=s.end()?s.lower_bound(ans):s.begin();
		printf(i==1?"%d":" %d",(a[i]+*num)%n);
		s.erase(num);
	}
}


F. Maximum Balanced Circle

time limit per test2 seconds memory limit per test256 megabytes

There are 𝑛n people in a row. The height of the 𝑖i-th person is 𝑎𝑖ai. You can choose any subset of these people and try to arrange them into a balanced circle.

balanced circle is such an order of people that the difference between heights of any adjacent people is no more than 11. For example, let heights of chosen people be [𝑎𝑖1,𝑎𝑖2,…,𝑎𝑖𝑘][ai1,ai2,…,aik], where 𝑘k is the number of people you choose. Then the condition |𝑎𝑖𝑗−𝑎𝑖𝑗+1|≤1|aij−aij+1|≤1 should be satisfied for all 𝑗j from 11 to 𝑘−1k−1 and the condition |𝑎𝑖1−𝑎𝑖𝑘|≤1|ai1−aik|≤1 should be also satisfied. |𝑥||x| means the absolute value of 𝑥x. It is obvious that the circle consisting of one person is balanced.

Your task is to choose the maximum number of people and construct a balanced circle consisting of all chosen people. It is obvious that the circle consisting of one person is balanced so the answer always exists.Input

The first line of the input contains one integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — the number of people.

The second line of the input contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤2⋅1051≤ai≤2⋅105), where 𝑎𝑖ai is the height of the 𝑖i-th person.Output

In the first line of the output print 𝑘k — the number of people in the maximum balanced circle.

In the second line print 𝑘k integers 𝑟𝑒𝑠1,𝑟𝑒𝑠2,…,𝑟𝑒𝑠𝑘res1,res2,…,resk, where 𝑟𝑒𝑠𝑗resj is the height of the 𝑗j-th person in the maximum balanced circle. The condition |𝑟𝑒𝑠𝑗−𝑟𝑒𝑠𝑗+1|≤1|resj−resj+1|≤1 should be satisfied for all 𝑗j from 11 to 𝑘−1k−1 and the condition |𝑟𝑒𝑠1−𝑟𝑒𝑠𝑘|≤1|res1−resk|≤1 should be also satisfied.
Examples
input

7 
4 3 5 1 2 2 1

output

5 
2 1 1 2 3

input

5 
3 7 5 1 5

output

2 
5 5

input

3 
5 1 4

output

2 
4 5

input

7 
2 2 3 2 1 2 2

output

7 
1 2 2 2 2 3 2

可以发现,题目中描述的环,拆成序列之后应该满足 al,al+1,…,ar,ar−1,…,al+1al,al+1,…,ar,ar−1,…,al+1 的形态,即:除了 al,aral,ar 之外的其他所有值应该都有至少两个,因此扫一遍就可以得到答案

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)2e5+100;
int num[maxn],odd[maxn];
set<int> s;
int main(){
	int n;cin>>n;
	for(int i=0,x;i<n;++i){scanf("%d",&x);num[x]++;s.insert(x);}
	int l=*s.begin(),tot=num[l],r,maxx=num[l],pre=l,ansl=l,ansr=l;
	for(auto it=++s.begin();it!=s.end();++it){
		int cnt=*it;
		if(cnt>pre+1){
			if(tot>maxx){maxx=tot;ansl=l;ansr=pre;}
			pre=cnt;l=cnt;tot=num[cnt];
		}
		else if(num[cnt]==1||cnt==*(--s.end())){
			tot+=num[cnt];
			if(tot>maxx){maxx=tot;ansl=l;ansr=cnt;}
			pre=cnt;l=cnt;tot=num[cnt];
		}
		else if(cnt<=pre+1){tot+=num[cnt];pre=cnt;}
	}
	printf("%d\n",maxx);
	rep(i,ansl,ansr) {printf("%d ",i);num[i]--;}
	dep(i,ansr,ansl) {while(num[i]--) printf("%d ",i);}
}

 

发表评论,支持MarkDown语法