Codeforces Round #552 (Div. 3)

A. Restoring Three Numbers

time limit per test1 second . memory limit per test256 megabytes

Polycarp has guessed three positive integers 𝑎a, 𝑏b and 𝑐c. He keeps these numbers in secret, but he writes down four numbers on a board in arbitrary order — their pairwise sums (three numbers) and sum of all three numbers (one number). So, there are four numbers on a board in random order: 𝑎+𝑏a+b, 𝑎+𝑐a+c, 𝑏+𝑐b+c and 𝑎+𝑏+𝑐a+b+c.

You have to guess three numbers 𝑎a, 𝑏b and 𝑐c using given numbers. Print three guessed integers in any order.

Pay attention that some given numbers 𝑎a, 𝑏b and 𝑐c can be equal (it is also possible that 𝑎=𝑏=𝑐a=b=c).Input

The only line of the input contains four positive integers 𝑥1,𝑥2,𝑥3,𝑥4×1,x2,x3,x4 (2≤𝑥𝑖≤1092≤xi≤109) — numbers written on a board in random order. It is guaranteed that the answer exists for the given number 𝑥1,𝑥2,𝑥3,𝑥4×1,x2,x3,x4.Output

Print such positive integers 𝑎a, 𝑏b and 𝑐c that four numbers written on a board are values 𝑎+𝑏a+b, 𝑎+𝑐a+c, 𝑏+𝑐b+c and 𝑎+𝑏+𝑐a+b+c written in some order. Print 𝑎a, 𝑏b and 𝑐c in any order. If there are several answers, you can print any. It is guaranteed that the answer exists.
Examples
input

3 6 5 4

output

2 1 3

input

40 40 40 60

output

20 20 20

input

201 101 101 200

output

1 100 100

签到题就不写题解了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
const int maxn=(int)2e5+100;
int main(){
	ll a[5];cin>>a[1]>>a[2]>>a[3]>>a[4];
	ll sum=(a[1]+a[2]+a[3]+a[4])/3;
	int fr=1;
	for(int i=1;i<5;++i){
		if(sum-a[i]){
			if(fr){fr=0;cout<<sum-a[i];}
			else cout<<" "<<sum-a[i];
		}
	}
}


B. Make Them Equal

time limit per test2 seconds memory limit per test256 megabytes

You are given a sequence 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an consisting of 𝑛n integers.

You can choose any non-negative integer 𝐷D (i.e. 𝐷≥0D≥0), and for each 𝑎𝑖ai you can:

  • add 𝐷D (only once), i. e. perform 𝑎𝑖:=𝑎𝑖+𝐷ai:=ai+D, or
  • subtract 𝐷D (only once), i. e. perform 𝑎𝑖:=𝑎𝑖−𝐷ai:=ai−D, or
  • leave the value of 𝑎𝑖ai unchanged.

It is possible that after an operation the value 𝑎𝑖ai becomes negative.

Your goal is to choose such minimum non-negative integer 𝐷D and perform changes in such a way, that all 𝑎𝑖ai are equal (i.e. 𝑎1=𝑎2=⋯=𝑎𝑛a1=a2=⋯=an).

Print the required 𝐷D or, if it is impossible to choose such value 𝐷D, print -1.

For example, for array [2,8][2,8] the value 𝐷=3D=3 is minimum possible because you can obtain the array [5,5][5,5] if you will add 𝐷D to 22 and subtract 𝐷D from 88. And for array [1,4,7,7][1,4,7,7] the value 𝐷=3D=3 is also minimum possible. You can add it to 11 and subtract it from 77 and obtain the array [4,4,4,4][4,4,4,4].Input

The first line of the input contains one integer 𝑛n (1≤𝑛≤1001≤n≤100) — the number of elements in 𝑎a.

The second line of the input contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤1001≤ai≤100) — the sequence 𝑎a.Output

Print one integer — the minimum non-negative integer value 𝐷D such that if you add this value to some 𝑎𝑖ai, subtract this value from some 𝑎𝑖ai and leave some 𝑎𝑖ai without changes, all obtained values become equal.

If it is impossible to choose such value 𝐷D, print -1.
Examples
input

6 
1 4 4 7 4 1

output

3

input

5 
2 2 5 2 5

output

3

input

4 
1 3 3 7

output

-1

input

2 
2 8

output

3

分类讨论,出现数的个数分为1,2,3,>3几种

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define INF 0x3f3f3f3f
#define pb push_back
const int maxn=(int)2e5+100;
const ull mod=(int)1e9+7;
int num[110];
int main(){
	int n;cin>>n;
	set<int> s;
	for(int i=0;i<n;++i){
		int x;cin>>x;
		s.insert(x);
	}
	if(s.size()==1){
		cout<<"0\n";
	}
	else if(s.size()==2){
		if((*s.begin()+*(--s.end()))&1){
			cout<<*(--s.end())-*s.begin()<<endl;
		}
		else cout<<(*(--s.end())-(*s.begin()))/2<<endl;
	}
	else if(s.size()>3){
		cout<<"-1\n";
	}
	else{
		if((*(--s.end()))+(*s.begin())==2*(*(++s.begin())))
			cout<<*(--s.end())-*(++s.begin())<<endl;
		else cout<<"-1\n";
	}
}


C. Gourmet Cat

time limit per test1 second memory limit per test256 megabytes

Polycarp has a cat and his cat is a real gourmet! Dependent on a day of the week he eats certain type of food:

  • on Mondays, Thursdays and Sundays he eats fish food;
  • on Tuesdays and Saturdays he eats rabbit stew;
  • on other days of week he eats chicken stake.

Polycarp plans to go on a trip and already packed his backpack. His backpack contains:

  • 𝑎a daily rations of fish food;
  • 𝑏b daily rations of rabbit stew;
  • 𝑐c daily rations of chicken stakes.

Polycarp has to choose such day of the week to start his trip that his cat can eat without additional food purchases as long as possible. Print the maximum number of days the cat can eat in a trip without additional food purchases, if Polycarp chooses the day of the week to start his trip optimally.Input

The first line of the input contains three positive integers 𝑎a, 𝑏b and 𝑐c (1≤𝑎,𝑏,𝑐≤7⋅1081≤a,b,c≤7⋅108) — the number of daily rations of fish foodrabbit stew and chicken stakes in Polycarps backpack correspondingly.Output

Print the maximum number of days the cat can eat in a trip without additional food purchases, if Polycarp chooses the day of the week to start his trip optimally.
Examples
input

2 1 1

output

4

input

3 2 2

output

7

input

1 100 1

output

3

input

30 20 10

output

39

Note

In the first example the best day for start of the trip is Sunday. In this case, during Sunday and Monday the cat will eat fish food, during Tuesday — rabbit stew and during Wednesday — chicken stake. So, after four days of the trip all food will be eaten.

In the second example Polycarp can start his trip in any day of the week. In any case there are food supplies only for one week in Polycarps backpack.

In the third example Polycarp can start his trip in any day, excluding Wednesday, Saturday and Sunday. In this case, the cat will eat three different dishes in three days. Nevertheless that after three days of a trip there will be 9999portions of rabbit stew in a backpack, can cannot eat anything in fourth day of a trip.

首先处理出完整星期的数量,然后对于剩下的暴力判断一下就好了,反正数据只有7天

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define INF 0x3f3f3f3f
#define pb push_back
const int maxn=(int)2e5+100;
const ull mod=(int)1e9+7;
int main(){
	int a,b,c;cin>>a>>b>>c;
	int k=min(min(a/3,b/2),c/2);
	ll ans=k*7;
	a-=k*3;b-=k*2;c-=k*2;
	int maxx=0;
	for(int i=1;i<=7;++i){
		int tot=0;
		int aa=a,bb=b,cc=c;
		for(int j=i;;++j){
			if(j%7==1||j%7==4||j%7==0){
				if(aa){aa--;tot++;}
				else break;
			}
			if(j%7==2||j%7==6){
				if(bb){bb--;tot++;}
				else break;
			}
			if(j%7==3||j%7==5){
				if(cc){cc--;tot++;}
				else break;
			}
		}
		maxx=max(maxx,tot);
	}
	cout<<maxx+ans<<endl;
}


D. Walking Robot

time limit per test2 seconds memory limit per test256 megabytes

There is a robot staying at 𝑋=0X=0 on the 𝑂𝑥Ox axis. He has to walk to 𝑋=𝑛X=n. You are controlling this robot and controlling how he goes. The robot has a battery and an accumulator with a solar panel.

The 𝑖i-th segment of the path (from 𝑋=𝑖−1X=i−1 to 𝑋=𝑖X=i) can be exposed to sunlight or not. The array 𝑠s denotes which segments are exposed to sunlight: if segment 𝑖i is exposed, then 𝑠𝑖=1si=1, otherwise 𝑠𝑖=0si=0.

The robot has one battery of capacity 𝑏b and one accumulator of capacity 𝑎a. For each segment, you should choose which type of energy storage robot will use to go to the next point (it can be either battery or accumulator). If the robot goes using the battery, the current charge of the battery is decreased by one (the robot can’t use the battery if its charge is zero). And if the robot goes using the accumulator, the current charge of the accumulator is decreased by one (and the robot also can’t use the accumulator if its charge is zero).

If the current segment is exposed to sunlight and the robot goes through it using the battery, the charge of the accumulator increases by one (of course, its charge can’t become higher than it’s maximum capacity).

If accumulator is used to pass some segment, its charge decreases by 1 no matter if the segment is exposed or not.

You understand that it is not always possible to walk to 𝑋=𝑛X=n. You want your robot to go as far as possible. Find the maximum number of segments of distance the robot can pass if you control him optimally.Input

The first line of the input contains three integers 𝑛,𝑏,𝑎n,b,a (1≤𝑛,𝑏,𝑎≤2⋅1051≤n,b,a≤2⋅105) — the robot’s destination point, the battery capacity and the accumulator capacity, respectively.

The second line of the input contains 𝑛n integers 𝑠1,𝑠2,…,𝑠𝑛s1,s2,…,sn (0≤𝑠𝑖≤10≤si≤1), where 𝑠𝑖si is 11 if the 𝑖i-th segment of distance is exposed to sunlight, and 00 otherwise.Output

Print one integer — the maximum number of segments the robot can pass if you control him optimally.
Examples
input

5 2 1 
0 1 0 1 0

output

5

input

6 2 1 
1 0 0 1 0 1

output

3

Note

In the first example the robot can go through the first segment using the accumulator, and charge levels become 𝑏=2b=2 and 𝑎=0a=0. The second segment can be passed using the battery, and charge levels become 𝑏=1b=1 and 𝑎=1a=1. The third segment can be passed using the accumulator, and charge levels become 𝑏=1b=1 and 𝑎=0a=0. The fourth segment can be passed using the battery, and charge levels become 𝑏=0b=0 and 𝑎=1a=1. And the fifth segment can be passed using the accumulator.

In the second example the robot can go through the maximum number of segments using battery two times and accumulator one time in any order.

贪心,暴力模拟,如果有蓄电池就用蓄电池,迫不得已才用电池

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define INF 0x3f3f3f3f
#define pb push_back
const int maxn=(int)2e5+100;
const ull mod=(int)1e9+7;
int s[maxn];
int main(){
	int n,a,b;scanf("%d%d%d",&n,&b,&a);
	int cb=b,ca=a;
	for(int i=0;i<n;++i){
		int x;scanf("%d",&x);
		if(x){
			if(ca==a){ca--;}
			else{
				if(cb){cb--;ca++;}
				else ca--;
			}
		}
		else{
			if(ca) ca--;
			else{
				if(cb) cb--;
			}
		}
		if(ca==0&&cb==0){
			printf("%d\n",i+1);
			return 0;
		}
	}
	printf("%d\n",n);
}


E. Two Teams

time limit per test2 seconds memory limit per test256 megabytes

There are 𝑛n students standing in a row. Two coaches are forming two teams — the first coach chooses the first team and the second coach chooses the second team.

The 𝑖i-th student has integer programming skill 𝑎𝑖ai. All programming skills are distinct and between 11 and 𝑛n, inclusive.

Firstly, the first coach will choose the student with maximum programming skill among all students not taken into any team, and 𝑘k closest students to the left of him and 𝑘k closest students to the right of him (if there are less than 𝑘k students to the left or to the right, all of them will be chosen). All students that are chosen leave the row and join the first team. Secondly, the second coach will make the same move (but all students chosen by him join the second team). Then again the first coach will make such move, and so on. This repeats until the row becomes empty (i. e. the process ends when each student becomes to some team).

Your problem is to determine which students will be taken into the first team and which students will be taken into the second team.Input

The first line of the input contains two integers 𝑛n and 𝑘k (1≤𝑘≤𝑛≤2⋅1051≤k≤n≤2⋅105) — the number of students and the value determining the range of chosen students during each move, respectively.

The second line of the input contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤𝑛1≤ai≤n), where 𝑎𝑖ai is the programming skill of the 𝑖i-th student. It is guaranteed that all programming skills are distinct.Output

Print a string of 𝑛n characters; 𝑖i-th character should be 1 if 𝑖i-th student joins the first team, or 2 otherwise.
Examples
input

5 2 
2 4 5 3 1

output

11111

input

5 1 
2 1 3 5 4

output

22111

input

7 1 
7 2 1 3 5 4 6

output

1121122

input

5 1 
2 4 5 3 1

output

21112

Note

In the first example the first coach chooses the student on a position 33, and the row becomes empty (all students join the first team).

In the second example the first coach chooses the student on position 44, and the row becomes [2,1][2,1] (students with programming skills [3,4,5][3,4,5] join the first team). Then the second coach chooses the student on position 11, and the row becomes empty (and students with programming skills [1,2][1,2] join the second team).

In the third example the first coach chooses the student on position 11, and the row becomes [1,3,5,4,6][1,3,5,4,6](students with programming skills [2,7][2,7] join the first team). Then the second coach chooses the student on position 55, and the row becomes [1,3,5][1,3,5] (students with programming skills [4,6][4,6] join the second team). Then the first coach chooses the student on position 33, and the row becomes [1][1] (students with programming skills [3,5][3,5]join the first team). And then the second coach chooses the remaining student (and the student with programming skill 11 joins the second team).

In the fourth example the first coach chooses the student on position 33, and the row becomes [2,1][2,1] (students with programming skills [3,4,5][3,4,5] join the first team). Then the second coach chooses the student on position 11, and the row becomes empty (and students with programming skills [1,2][1,2] join the second team).

用数组模拟一个链表搞一搞就可以了

#include<bits/stdc++.h>
using namespace std;
const int maxn=(int)2e5+100;
int a[maxn],ans[maxn];
int main(){
	int n,k;scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	int pre[maxn],suf[maxn];
	for(int i=1;i<=n;++i){
		if(i==1) pre[a[i]]=-1; else pre[a[i]]=a[i-1];
		if(i==n) suf[a[i]]=-1; else suf[a[i]]=a[i+1];
	}
	int op=2,pos=n;
	while(pos){
		if(op==1) op=2;else op=1;
		int kk=k,curl=pos; ans[pos]=op;
		while(kk&&pre[curl]!=-1){curl=pre[curl];ans[curl]=op;kk--;}
		curl=pre[curl];
		int curr=pos;kk=k;
		while(kk&&suf[curr]!=-1){curr=suf[curr];ans[curr]=op;kk--;}
		curr=suf[curr];
		if(curl!=-1&&curr!=-1){suf[curl]=curr;pre[curr]=curl;}
		else if(curl==-1&&curr!=-1){pre[curr]=-1;suf[curl]=curr;}
		else if(curl!=-1&&curr==-1){pre[curr]=curl;suf[curl]=-1;}
		while(ans[pos-1]&&pos-1>=1) pos--;
		pos--;
	}
	for(int i=1;i<=n;++i) printf("%d",ans[a[i]]);
}


F. Shovels Shop

time limit per test2 seconds memory limit per test256 megabytes

There are 𝑛n shovels in the nearby shop. The 𝑖i-th shovel costs 𝑎𝑖ai bourles.

Misha has to buy exactly 𝑘k shovels. Each shovel can be bought no more than once.

Misha can buy shovels by several purchases. During one purchase he can choose any subset of remaining (non-bought) shovels and buy this subset.

There are also 𝑚m special offers in the shop. The 𝑗j-th of them is given as a pair (𝑥𝑗,𝑦𝑗)(xj,yj), and it means that if Misha buys exactly 𝑥𝑗xj shovels during one purchase then 𝑦𝑗yj most cheapest of them are for free (i.e. he will not pay for 𝑦𝑗yj most cheapest shovels during the current purchase).

Misha can use any offer any (possibly, zero) number of times, but he cannot use more than one offer during one purchase (but he can buy shovels without using any offers).

Your task is to calculate the minimum cost of buying 𝑘k shovels, if Misha buys them optimally.Input

The first line of the input contains three integers 𝑛,𝑚n,m and 𝑘k (1≤𝑛,𝑚≤2⋅105,1≤𝑘≤𝑚𝑖𝑛(𝑛,2000)1≤n,m≤2⋅105,1≤k≤min(n,2000)) — the number of shovels in the shop, the number of special offers and the number of shovels Misha has to buy, correspondingly.

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

The next 𝑚m lines contain special offers. The 𝑗j-th of them is given as a pair of integers (𝑥𝑖,𝑦𝑖)(xi,yi) (1≤𝑦𝑖≤𝑥𝑖≤𝑛1≤yi≤xi≤n) and means that if Misha buys exactly 𝑥𝑖xi shovels during some purchase, then he can take 𝑦𝑖yi most cheapest of them for free.Output

Print one integer — the minimum cost of buying 𝑘k shovels if Misha buys them optimally.
Examples
input

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

output

7

input

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

output

17

input

5 1 4 
2 5 7 4 6
5 4

output

17

Note

In the first example Misha can buy shovels on positions 11 and 44 (both with costs 22) during the first purchase and get one of them for free using the first or the third special offer. And then he can buy shovels on positions 33 and 66(with costs 44 and 33) during the second purchase and get the second one for free using the first or the third special offer. Then he can buy the shovel on a position 77 with cost 11. So the total cost is 4+2+1=74+2+1=7.

In the second example Misha can buy shovels on positions 11, 22, 33, 44 and 88 (costs are 66, 88, 55, 11 and 22) and get three cheapest (with costs 55, 11 and 22) for free. And then he can buy shovels on positions 66, 77 and 99 (all with costs 11) without using any special offers. So the total cost is 6+8+1+1+1=176+8+1+1+1=17.

In the third example Misha can buy four cheapest shovels without using any special offers and get the total cost 1717.

多重背包,dp[i]表示买了i个铲子时节省的最大的钱数

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=(int)2e5+100;
ll sa[maxn],pr[maxn],dp[maxn];
int main(){
	ll n,m,k;cin>>n>>m>>k;
	for(int i=1;i<=n;++i) scanf("%lld",&pr[i]); sort(pr+1,pr+n+1);
	ll sum[maxn];sum[1]=pr[1]; for(int i=2;i<=n;++i) sum[i]=sum[i-1]+pr[i];
	for(int i=0;i<m;++i){ll a,b;scanf("%lld%lld",&a,&b);sa[a]=max(sa[a],b);}
	for(int i=1;i<=k;++i)
		for(int j=0;j<=i;++j) dp[i]=max(dp[i],dp[j]+sum[j+sa[i-j]]-sum[j]);
	printf("%lld\n",sum[k]-dp[k]);
}


G. Minimum Possible LCM

time limit per test4 seconds memory limit per test1024 megabytes

You are given an array 𝑎a consisting of 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an.

Your problem is to find such pair of indices 𝑖,𝑗i,j (1≤𝑖<𝑗≤𝑛1≤i<j≤n) that 𝑙𝑐𝑚(𝑎𝑖,𝑎𝑗)lcm(ai,aj) is minimum possible.

𝑙𝑐𝑚(𝑥,𝑦)lcm(x,y) is the least common multiple of 𝑥x and 𝑦y (minimum positive number such that both 𝑥x and 𝑦y are divisors of this number).Input

The first line of the input contains one integer 𝑛n (2≤𝑛≤1062≤n≤106) — the number of elements in 𝑎a.

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

Print two integers 𝑖i and 𝑗j (1≤𝑖<𝑗≤𝑛1≤i<j≤n) such that the value of 𝑙𝑐𝑚(𝑎𝑖,𝑎𝑗)lcm(ai,aj) is minimum among all valid pairs 𝑖,𝑗i,j. If there are multiple answers, you can print any.
Examples
input

5 
2 4 8 3 6

output

1 2

input

5 
5 2 11 3 7

output

2 4

input

6 
2 5 10 1 10 2

output

1 4

暴力枚举每个因子,真的很暴力

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=(int)1e7+100;
int countt[maxn],pos[maxn][3],num[maxn];
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;++i){
		int x;scanf("%d",&x); num[x]++;
		if(countt[x]<2) pos[x][++countt[x]]=i;
	}
	ll maxx=1e18;int tmp[maxn],c,ans1,ans2;
	for(int i=1;i<maxn;++i){
		for(int j=1;j*i<maxn;++j){
			while(num[i*j]&&c<2) num[i*j]--,tmp[++c]=j;
			if(c==2) break;
		}
		if(c==2&&maxx>(ll)tmp[1]*tmp[2]*i){
			maxx=(ll)tmp[1]*tmp[2]*i;
			ans1=tmp[1]*i;ans2=tmp[2]*i;
		}
		while(c) {num[i*tmp[c--]]++;}
	}
	if(ans1==ans2){ans1=pos[ans1][1];ans2=pos[ans2][2];}
	else {ans1=pos[ans1][1];ans2=pos[ans2][1];}
	if(ans1>ans2) swap(ans1,ans2);
	printf("%d %d\n",ans1,ans2);
}

 

发表评论,支持MarkDown语法