A. Pens and Pencils
time limit per test1 second memory limit per test256 megabytes
Tomorrow is a difficult day for Polycarp: he has to attend a lectures and b practical classes at the university! Since Polycarp is a diligent student, he is going to attend all of them.
While preparing for the university, Polycarp wonders whether he can take enough writing implements to write all of the lectures and draw everything he has to during all of the practical classes. Polycarp writes lectures using a pen (he can't use a pencil to write lectures!); he can write down c lectures using one pen, and after that it runs out of ink. During practical classes Polycarp draws blueprints with a pencil (he can't use a pen to draw blueprints!); one pencil is enough to draw all blueprints during d practical classes, after which it is unusable.
Polycarp's pencilcase can hold no more than k writing implements, so if Polycarp wants to take x pens and y pencils, they will fit in the pencilcase if and only if \(x + y \le k\).
Now Polycarp wants to know how many pens and pencils should he take. Help him to determine it, or tell that his pencilcase doesn't have enough room for all the implements he needs tomorrow!
Note that you don't have to minimize the number of writing implements (though their total number must not exceed k).Input
The first line of the input contains one integer \(t (1 \le t \le 100)\) — the number of test cases in the input. Then the test cases follow.
Each test case is described by one line containing five integers a, b, c, d and k, separated by spaces \((1 \le a, b, c, d, k \le 100)\) — the number of lectures Polycarp has to attend, the number of practical classes Polycarp has to attend, the number of lectures which can be written down using one pen, the number of practical classes for which one pencil is enough, and the number of writing implements that can fit into Polycarp's pencilcase, respectively.
In hacks it is allowed to use only one test case in the input, so \(t = 1\) should be satisfied.
Output
For each test case, print the answer as follows:
If the pencilcase can't hold enough writing implements to use them during all lectures and practical classes, print one integer -1. Otherwise, print two non-negative integers x and y — the number of pens and pencils Polycarp should put in his pencilcase. If there are multiple answers, print any of them. Note that you don't have to minimize the number of writing implements (though their total number must not exceed k).
Exampleinput
3 7 5 4 5 8 7 5 4 5 2 20 53 45 26 4
output
7 1 -1 1 3
Note
There are many different answers for the first test case; \(x = 7, y = 1\) is only one of them. For example, \(x = 3, y = 1\) is also correct.
\(x = 1, y = 3\) is the only correct answer for the third test case.
签到
#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 int mod=(int)1e9+7;
void solve(){
int a,b,c,d,k;scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
int x=a/c,y=b/d;
if(a%c) x++;
if(b%d) y++;
if(x+y<=k) printf("%d %d\n",x,y);
else puts("-1");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
B. Rooms and Staircases
time limit per test1 second memory limit per test256 megabytes
Nikolay lives in a two-storied house. There are n rooms on each floor, arranged in a row and numbered from one from left to right. So each room can be represented by the number of the floor and the number of the room on this floor (room number is an integer between 1 and n).
If Nikolay is currently in some room, he can move to any of the neighbouring rooms (if they exist). Rooms with numbers i and i+1 on each floor are neighbouring, for all \(1 \leq i \leq n - 1\). There may also be staircases that connect two rooms from different floors having the same numbers. If there is a staircase connecting the room x on the first floor and the room x on the second floor, then Nikolay can use it to move from one room to another.
The picture illustrates a house with \(n = 4.\) There is a staircase between the room 2 on the first floor and the room 2 on the second floor, and another staircase between the room 4 on the first floor and the room 4 on the second floor. The arrows denote possible directions in which Nikolay can move. The picture corresponds to the string "0101" in the input.
Nikolay wants to move through some rooms in his house. To do this, he firstly chooses any room where he starts. Then Nikolay moves between rooms according to the aforementioned rules. Nikolay never visits the same room twice (he won't enter a room where he has already been).
Calculate the maximum number of rooms Nikolay can visit during his tour, if:
- he can start in any room on any floor of his choice,
- and he won't visit the same room twice.
Input
The first line of the input contains one integer \(t (1 \le t \le 100)\) — the number of test cases in the input. Then test cases follow. Each test case consists of two lines.
The first line contains one integer \(n (1 \le n \le 1\,000)\) — the number of rooms on each floor.
The second line contains one string consisting of n characters, each character is either a '0' or a '1'. If the i-th character is a '1', then there is a staircase between the room i on the first floor and the room i on the second floor. If the i-th character is a '0', then there is no staircase between the room i on the first floor and the room i on the second floor.
In hacks it is allowed to use only one test case in the input, so t = 1 should be satisfied.
Output
For each test case print one integer — the maximum number of rooms Nikolay can visit during his tour, if he can start in any room on any floor, and he won't visit the same room twice.
Exampleinput
4 5 00100 8 00000000 5 11111 3 110
output
6 8 10 6
Note
In the first test case Nikolay may start in the first room of the first floor. Then he moves to the second room on the first floor, and then — to the third room on the first floor. Then he uses a staircase to get to the third room on the second floor. Then he goes to the fourth room on the second floor, and then — to the fifth room on the second floor. So, Nikolay visits 6 rooms.
There are no staircases in the second test case, so Nikolay can only visit all rooms on the same floor (if he starts in the leftmost or in the rightmost room).
In the third test case it is possible to visit all rooms: first floor, first room\( \rightarrow\) second floor, first room \(\rightarrow\) second floor, second room \(\rightarrow\) first floor, second room \(\rightarrow\) first floor, third room \(\rightarrow\) second floor, third room \(\rightarrow\) second floor, fourth room \(\rightarrow\) first floor, fourth room \(\rightarrow\) first floor, fifth room \(\rightarrow\) second floor, fifth room.
In the fourth test case it is also possible to visit all rooms: second floor, third room \(\rightarrow\) second floor, second room \(\rightarrow\) second floor, first room \(\rightarrow\) first floor, first room \(\rightarrow\) first floor, second room \(\rightarrow\) first floor, third room.
贪心，签到
#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 int mod=(int)1e9+7;
int n;
char s[1010];
void solve(){
scanf("%d%s",&n,s+1);
int ans=0,num=0;
rep(i,1,n) if(s[i]=='1') ans=max(ans,i*2),num++;
dep(i,n,1) if(s[i]=='1') ans=max(ans,(n-i+1)*2);
ans=max(ans,n+num);
printf("%d\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
C. The Football Season
time limit per test1 second memory limit per test256 megabytes
The football season has just ended in Berland. According to the rules of Berland football, each match is played between two teams. The result of each match is either a draw, or a victory of one of the playing teams. If a team wins the match, it gets w points, and the opposing team gets 0 points. If the game results in a draw, both teams get d points.
The manager of the Berland capital team wants to summarize the results of the season, but, unfortunately, all information about the results of each match is lost. The manager only knows that the team has played n games and got p points for them.
You have to determine three integers x, y and z — the number of wins, draws and loses of the team. If there are multiple answers, print any of them. If there is no suitable triple \((x, y, z)\), report about it.Input
The first line contains four integers n, p, w and d \((1 \le n \le 10^{12}, 0 \le p \le 10^{17}, 1 \le d < w \le 10^{5})\) — the number of games, the number of points the team got, the number of points awarded for winning a match, and the number of points awarded for a draw, respectively. Note that w > d, so the number of points awarded for winning is strictly greater than the number of points awarded for draw.
Output
If there is no answer, print -1.
Otherwise print three non-negative integers x, y and z — the number of wins, draws and losses of the team. If there are multiple possible triples (x, y, z), print any of them. The numbers should meet the following conditions:
- \(x \cdot w + y \cdot d = p\),
- \(x + y + z = n\).
Examplesinput
30 60 3 1
output
17 9 4
input
10 51 5 4
output
-1
input
20 0 15 5
output
0 0 20
Note
One of the possible answers in the first example — 17 wins, 9 draws and 4 losses. Then the team got \(17 \cdot 3 + 9 \cdot 1 = 60\) points in \(17 + 9 + 4 = 30\) games.
In the second example the maximum possible score is \(10 \cdot 5 = 50\). Since p = 51, there is no answer.
In the third example the team got 0 points, so all 20 games were lost.
考虑第一个式子：\(x \cdot w + y \cdot d = p\)
因为w>d，显然要求x尽可能大，那么我们想从0开始枚举y，验证x的可行性，此时如果枚举上届是n的话显然会Tle；
考虑如何验证x的可行性，显然就是判断\((p - y \cdot d) \ % w\)是否为0，显然枚举到\(y>w\)的时候之后就没有意义了
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
ll n,p,d,w;
int main(){
scanf("%lld%lld%lld%lld",&n,&p,&w,&d);
if(n*w<p) return puts("-1"),0;
rep(i,0,w){
if((p-i*d)%w==0){
ll x=(p-1ll*i*d)/w,y=i;
if(x+y>n) return puts("-1"),0;
return printf("%lld %lld %lld",x,y,n-x-y),0;
}
if(i*d>p) break;
}
return puts("-1"),0;
}
D. Paint the Tree
time limit per test3 seconds memory limit per test256 megabytes
You are given a tree consisting of n vertices. A tree is an undirected connected acyclic graph.
Example of a tree.
You have to paint each vertex into one of three colors. For each vertex, you know the cost of painting it in every color.
You have to paint the vertices so that any path consisting of exactly three distinct vertices does not contain any vertices with equal colors. In other words, let's consider all triples (x, y, z) such that \(x \neq y, y \neq z, x \neq z\), x is connected by an edge with y, and y is connected by an edge with z. The colours of x, y and z should be pairwise distinct. Let's call a painting which meets this condition good.
You have to calculate the minimum cost of a good painting and find one of the optimal paintings. If there is no good painting, report about it.
Input
The first line contains one integer \(n (3 \le n \le 100\,000)\) — the number of vertices.
The second line contains a sequence of integers \(c_{1, 1}, c_{1, 2}, \dots, c_{1, n} (1 \le c_{1, i} \le 10^{9})\), where \(c_{1, i}\) is the cost of painting the i-th vertex into the first color.
The third line contains a sequence of integers \(c_{2, 1}, c_{2, 2}, \dots, c_{2, n} (1 \le c_{2, i} \le 10^{9})\), where \(c_{2, i}\) is the cost of painting the i-th vertex into the second color.
The fourth line contains a sequence of integers \(c_{3, 1}, c_{3, 2}, \dots, c_{3, n} (1 \le c_{3, i} \le 10^{9})\), where \(c_{3, i}\) is the cost of painting the i-th vertex into the third color.
Then (n - 1) lines follow, each containing two integers \(u_j\) and \(v_j (1 \le u_j, v_j \le n, u_j \neq v_j)\) — the numbers of vertices connected by the j-th undirected edge. It is guaranteed that these edges denote a tree.Output
If there is no good painting, print -1.
Otherwise, print the minimum cost of a good painting in the first line. In the second line print n integers \(b_1, b_2, \dots, b_n (1 \le b_i \le 3)\), where the i-th integer should denote the color of the i-th vertex. If there are multiple good paintings with minimum cost, print any of them.
Examplesinput
3 3 2 3 4 3 2 3 1 3 1 2 2 3
output
6 1 3 2
input
5 3 4 2 1 2 4 2 1 5 4 5 3 2 1 1 1 2 3 2 4 3 5 3
output
-1
input
5 3 4 2 1 2 4 2 1 5 4 5 3 2 1 1 1 2 3 2 4 3 5 4
output
9 1 3 2 1 3
Note
All vertices should be painted in different colors in the first example. The optimal way to do it is to paint the first vertex into color 1, the second vertex — into color 3, and the third vertex — into color 2. The cost of this painting is \(3 + 2 + 1 = 6\).
合法的解只能是一条链，枚举一开始两个点的6种情况暴力算即可
#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 int mod=(int)1e9+7;
int n,ind[maxn],pos=1,pp=1,id[10][maxn];
ll c[4][maxn];
vector<int> g[maxn<<1];
ll dfs(int pos,int st,int fa,int col1,int col2){
ll ans=0;int col;
rep(i,1,3) if(i!=col1&&i!=col2) col=i;
id[pos][st]=col;
if((int)g[st].size()==1) return c[col-1][st];
rep(i,0,1) if(g[st][i]!=fa) ans+=c[col-1][st]+dfs(pos,g[st][i],st,col2,col);
return ans;
}
int main(){
scanf("%d",&n);
rep(i,1,n) scanf("%lld",&c[0][i]);
rep(i,1,n) scanf("%lld",&c[1][i]);
rep(i,1,n) scanf("%lld",&c[2][i]);
rep(i,1,n-1){
int u,v;scanf("%d%d",&u,&v);
g[u].pb(v);g[v].pb(u);
ind[u]++;ind[v]++;
}
int num=0,st=0,ed=0;
rep(i,1,n){
if(ind[i]==1){
num++;
if(st) ed=i;
else st=i;
}
else if(ind[i]>2) return puts("-1"),0;
}
if(num!=2) return puts("-1"),0;
ll ans=(ll)1e18;
int st2=g[st][0],st3;
rep(i,0,1) if(g[st2][i]!=st) st3=g[st2][i];
rep(i,1,3) rep(j,1,3) if(i!=j){
pos++;
id[pos][st]=i;id[pos][st2]=j;
ll tmp=c[i-1][st]+c[j-1][st2]+dfs(pos,st3,st2,i,j);
if(ans>tmp) ans=tmp,pp=pos;
}
printf("%lld\n",ans);
rep(i,1,n) printf("%d ",id[pp][i]);
puts("");
}
E. Minimizing Difference
time limit per test2 seconds memory limit per test256 megabytes
You are given a sequence \(a_1, a_2, \dots, a_n\) consisting of n integers.
You may perform the following operation on this sequence: choose any element and either increase or decrease it by one.
Calculate the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than k times.Input
The first line contains two integers n and k \((2 \le n \le 10^{5}, 1 \le k \le 10^{14})\) — the number of elements in the sequence and the maximum number of times you can perform the operation, respectively.
The second line contains a sequence of integers \(a_1, a_2, \dots, a_n (1 \le a_i \le 10^{9})\).Output
Print the minimum possible difference between the maximum element and the minimum element in the sequence, if you can perform the aforementioned operation no more than k times.
Examplesinput
4 5 3 1 7 5
output
2
input
3 10 100 100 100
output
0
input
10 9 4 5 5 7 5 4 5 2 4 3
output
1
Note
In the first example you can increase the first element twice and decrease the third element twice, so the sequence becomes \([3, 3, 5, 5]\), and the difference between maximum and minimum is 2. You still can perform one operation after that, but it's useless since you can't make the answer less than 2.
In the second example all elements are already equal, so you may get 0 as the answer even without applying any operations.
暴力贪心，考虑每次的最小值mn和最小值的个数cnt1，以及最大值mx和最大值的个数cnt2，每次暴力增加或者减少，贪心
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const ll maxn=(ll)2e5+100;
const ll mod=(ll)1e9+7;
int n,a[maxn];
map<int,int> cnt;
ll k;
int main(){
scanf("%d%lld",&n,&k);
rep(i,1,n) scanf("%d",&a[i]),cnt[a[i]]++;
sort(a+1,a+1+n);
int sz=unique(a+1,a+1+n)-a-1;
int pos1=1,pos2=sz,mn=a[pos1],mx=a[pos2],cnt1=cnt[a[1]],cnt2=cnt[a[sz]];//pos1大于等于mn的最小
while(1){
if(k==0||mn>=mx) break;
if(cnt1<cnt2){
ll sub=0;
if(a[pos1]==mn){
if(pos1+1>sz) break;
sub=a[pos1+1]-mn;
}
else sub=a[pos1]-mn;
ll num=k/cnt1;
if(num<=sub){
k=0;
mn+=num;
break;
}
else{
k-=1ll*cnt1*sub;
mn=a[++pos1];
cnt1+=cnt[a[pos1]];
}
}
else{
ll sub=0;
if(a[pos2]==mx){
if(pos2-1<1) break;
sub=mx-a[pos2-1];
}
else sub=mx-a[pos2];
ll num=k/cnt2;
if(num<=sub){
k=0;
mx-=num;
break;
}
else{
k-=1ll*cnt2*sub;
mx=a[--pos2];
cnt2+=cnt[a[pos2]];
}
}
}
if(k==0) return printf("%d\n",mx-mn),0;
else puts("0");
}
G. Running in Pairs
time limit per test1 second memory limit per test256 megabytes
Demonstrative competitions will be held in the run-up to the 20NN Berlatov Olympic Games. Today is the day for the running competition!
Berlatov team consists of 2n runners which are placed on two running tracks; n runners are placed on each track. The runners are numbered from 1 to n on each track. The runner with number i runs through the entire track in i seconds.
The competition is held as follows: first runners on both tracks start running at the same time; when the slower of them arrives at the end of the track, second runners on both tracks start running, and everyone waits until the slower of them finishes running, and so on, until all n pairs run through the track.
The organizers want the run to be as long as possible, but if it lasts for more than k seconds, the crowd will get bored. As the coach of the team, you may choose any order in which the runners are arranged on each track (but you can't change the number of runners on each track or swap runners between different tracks).
You have to choose the order of runners on each track so that the duration of the competition is as long as possible, but does not exceed k seconds.
Formally, you want to find two permutations p and q (both consisting of n elements) such that sum = \(\sum\limits_{i=1}^{n} max(p_i, q_i)\) is maximum possible, but does not exceed k. If there is no such pair, report about it.Input
The first line contains two integers n and k \((1 \le n \le 10^6, 1 \le k \le n^2)\) — the number of runners on each track and the maximum possible duration of the competition, respectively.Output
If it is impossible to reorder the runners so that the duration of the competition does not exceed k seconds, print -1.
Otherwise, print three lines. The first line should contain one integer sum — the maximum possible duration of the competition not exceeding k. The second line should contain a permutation of n integers \(p_1, p_2, \dots, p_n (1 \le p_i \le n\), all\( p_i\) should be pairwise distinct) — the numbers of runners on the first track in the order they participate in the competition. The third line should contain a permutation of n integers \(q_1, q_2, \dots, q_n (1 \le q_i \le n\), all \(q_i\) should be pairwise distinct) — the numbers of runners on the second track in the order they participate in the competition. The value of sum = \(\sum\limits_{i=1}^{n} max(p_i, q_i)\) should be maximum possible, but should not exceed k. If there are multiple answers, print any of them.
Examplesinput
5 20
output
20 1 2 3 4 5 5 2 4 3 1
input
3 9
output
8 1 2 3 3 2 1
input
10 54
output
-1
Note
In the first example the order of runners on the first track should be \([5, 3, 2, 1, 4]\), and the order of runners on the second track should be \([1, 4, 2, 5, 3]\). Then the duration of the competition is max(5, 1) + max(3, 4) + max(2, 2) + max(1, 5) + max(4, 3) = 5 + 4 + 2 + 5 + 4 = 20, so it is equal to the maximum allowed duration.
In the first example the order of runners on the first track should be [2, 3, 1], and the order of runners on the second track should be [2, 1, 3]. Then the duration of the competition is 8, and it is the maximum possible duration for n = 3.
这题真的2500分？我觉得1500差不多，很简单的构造题
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
ll n,k;
int main(){
scanf("%lld%lld",&n,&k);
ll st,ed;
if(n%2) st=(1+n)*n/2,ed=((n+1)/2)*((n+1)/2)+(1+n)*(n-1)/2;
else st=(1+n)*n/2,ed=st+n*n/4;
if(k<st) return puts("-1"),0;
if(k>=ed){
printf("%lld\n",ed);
rep(i,1,n) printf("%d ",i); puts("");
rep(i,1,n) printf("%d ",n-i+1); puts("");
return 0;
}
printf("%lld\n",k);
rep(i,1,n) printf("%d ",i); puts("");
k-=st;
ll l=0,r=n/2,num;
while(l<=r){
ll mid=(l+r)>>1;
if((n-mid)*mid<=k) num=mid,l=mid+1;
else r=mid-1;
}
k-=(n-num)*num;
rep(i,1,num) printf("%d ",n-i+1);
if(k) printf("%lld ",num+1+k);
rep(i,num+2,num+k) printf("%d ",i);
printf("%lld ",num+1);
rep(i,num+2+k,n-num) printf("%d ",i);
rep(i,1,num) printf("%d ",num-i+1); puts("");
}
