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,?4x1,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,?4x1,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);
}

 

Subscribe
提醒
0 评论
Inline Feedbacks
View all comments