Codeforces Round #535 (Div. 3)

Codeforces 1108 A. Two distinct points

time limit per test1 second memory limit per test256

You are given two segments [?1;?1][l1;r1] and [?2;?2][l2;r2] on the ?x-axis. It is guaranteed that ?1<?1l1<r1 and ?2<?2l2<r2. Segments may intersect, overlap or even coincide with each other.

The example of two segments on the ?x-axis.

Your problem is to find two integers ?a and ?b such that ?1≤?≤?1l1≤a≤r1, ?2≤?≤?2l2≤b≤r2 and ?≠?a≠b. In other words, you have to choose two distinct integer points in such a way that the first point belongs to the segment [?1;?1][l1;r1] and the second one belongs to the segment [?2;?2][l2;r2].

It is guaranteed that the answer exists. If there are multiple answers, you can print any of them.

You have to answer ?q independent queries.Input

The first line of the input contains one integer ?q (1≤?≤5001≤q≤500) — the number of queries.

Each of the next ?q lines contains four integers ?1?,?1?,?2?l1i,r1i,l2i and ?2?r2i (1≤?1?,?1?,?2?,?2?≤109,?1?<?1?,?2?<?2?1≤l1i,r1i,l2i,r2i≤109,l1i<r1i,l2i<r2i) — the ends of the segments in the ?i-th query.Output

Print 2?2q integers. For the ?i-th query print two integers ??ai and ??bi — such numbers that ?1?≤??≤?1?l1i≤ai≤r1i, ?2?≤??≤?2?l2i≤bi≤r2i and ??≠??ai≠bi. Queries are numbered in order of the input.

It is guaranteed that the answer exists. If there are multiple answers, you can print any.
Exampleinput

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

output

2 1 
3 4
3 2
1 2
3 7

题解:签到题,注意输出顺序不能反

#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 INF=0x3f3f3f3f;
int main(){
    int T;cin>>T;
    while(T--){
        int l1,l2,r1,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        int minl=min(l1,l2);
        if(minl==l1){
            rep(i,l2,r2) if(i!=minl){
                    	printf("%d %d\n",minl,i);
                    	break;
                	}
        }
        else{
            rep(i,l1,r1) if(i!=minl){
                    printf("%d %d\n",i,minl);
                    break;
                }
        }
    }
    return 0;
}

 


Codeforces 1108 B. Divisors of Two Integers

time limit per test1 second memory limit per test256 megabyte

Recently you have received two positive integer numbers ?x and ?y. You forgot them, but you remembered a shuffled list containing all divisors of ?x (including 11 and ?x) and all divisors of ?y (including 11 and ?y). If ?d is a divisor of both numbers ?x and ?y at the same time, there are two occurrences of ?d in the list.

For example, if ?=4x=4 and ?=6y=6 then the given list can be any permutation of the list [1,2,4,1,2,3,6][1,2,4,1,2,3,6]. Some of the possible lists are: [1,1,2,4,6,3,2][1,1,2,4,6,3,2], [4,6,1,1,2,3,2][4,6,1,1,2,3,2] or [1,6,3,2,4,1,2][1,6,3,2,4,1,2].

Your problem is to restore suitable positive integer numbers ?x and ?y that would yield the same list of divisors (possibly in different order).

It is guaranteed that the answer exists, i.e. the given list of divisors corresponds to some positive integers ?x and ?y.Input

The first line contains one integer ?n (2≤?≤1282≤n≤128) — the number of divisors of ?x and ?y.

The second line of the input contains ?n integers ?1,?2,…,??d1,d2,…,dn (1≤??≤1041≤di≤104), where ??di is either divisor of ?x or divisor of ?y. If a number is divisor of both numbers ?x and ?y then there are two copies of this number in the list.Output

Print two positive integer numbers ?x and ?y — such numbers that merged list of their divisors is the permutation of the given list of integers. It is guaranteed that the answer exists.
Exampleinput

10 
10 2 8 1 2 4 1 20 4 5

output

20 8

题意:给你两个整数的所有除数列表,让你输出这两个数

题解:暴力,首先升序排列,最大的肯定是一个数,再枚举这个数的每个除数,从原序列中减去,剩下的最大的那个数就是第二个数

#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 INF=0x3f3f3f3f;
int n,a[200],num[10010];
int main(){
	cin>>n;
    rep(i,1,n){
        scanf("%d",&a[i]);
        num[a[i]]++;
    } sort(a+1,a+1+n);
    printf("%d ",a[n-1]);
    for(int i=1;i<=a[n-1];++i){
        if(a[n-1]%i==0){
            num[i]--;
        }
    }
    for(int i=n-2;i>=0;--i){
        if(num[a[i]]){
            printf("%d\n",a[i]);
            break;
        }
    }    
    return 0;
}

 


Codeforces 1108 C. Nice Garland

time limit per test1 second memory limit per test256 megabyte

You have a garland consisting of ?n lamps. Each lamp is colored red, green or blue. The color of the ?i-th lamp is ??si (‘R’, ‘G’ and ‘B’ — colors of lamps in the garland).

You have to recolor some lamps in this garland (recoloring a lamp means changing its initial color to another) in such a way that the obtained garland is nice.

A garland is called nice if any two lamps of the same color have distance divisible by three between them. I.e. if the obtained garland is ?t, then for each ?,?i,j such that ??=??ti=tj should be satisfied |?−?| ??? 3=0|i−j| mod 3=0. The value |?||x| means absolute value of ?x, the operation ? ??? ?x mod y means remainder of ?x when divided by ?y.

For example, the following garlands are nice: “RGBRGBRG”, “GB”, “R”, “GRBGRBG”, “BRGBRGB”. The following garlands are not nice: “RR”, “RGBG”.

Among all ways to recolor the initial garland to make it nice you have to choose one with the minimum number of recolored lamps. If there are multiple optimal solutions, print any of them.Input

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

The second line of the input contains the string ?s consisting of ?n characters ‘R’, ‘G’ and ‘B’ — colors of lamps in the garland.Output

In the first line of the output print one integer ?r — the minimum number of recolors needed to obtain a nice garland from the given one.

In the second line of the output print one string ?t of length ?n — a nice garland obtained from the initial one with minimum number of recolors. If there are multiple optimal solutions, print any of them.
Examplesinput

3 
BRB

output

1 
GRB

input

7 
RGBGRBB

output

3 
RGBRGBR

题解:对于每个重新涂色的花圈,其颜色都是“RGB”或“BGR”的循环,因此枚举六个长度为n的目标串,枚举六次答案,选最小的那个

#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 INF=0x3f3f3f3f;
int n;
string str;
int main(){
    map<int,char> mp; mp[0]='R'; mp[1]='G'; mp[2]='B';
	cin>>n; getline(cin,str);
    string s1,s2,s3,t1,t2,t3,s4,s5,s6;
    s1.clear();s2.clear();s3.clear();
    for(int i=0;i<n;++i){
        t1.pb(mp[i%3]);
        t2.pb(mp[(i+1)%3]);
        t3.pb(mp[(i+2)%3]);
    }
    s1=t1;s2=t2;s3=t3;
    reverse(t1.begin(), t1.end());
    reverse(t2.begin(), t2.end());
    reverse(t3.begin(), t3.end());
    s4=t1;s5=t2;s6=t3;
    int ans1,ans2,ans3,ans4,ans5,ans6;
    ans1=ans2=ans3=ans4=ans5=ans6=0;
    for(int i=0;i<str.length();++i){
        if(str[i]!=s1[i]) ans1++;
        if(str[i]!=s2[i]) ans2++;
        if(str[i]!=s3[i]) ans3++;
        if(str[i]!=s4[i]) ans4++;
        if(str[i]!=s5[i]) ans5++;
        if(str[i]!=s6[i]) ans6++;
    }
    int ans=min(min(min(min(min(ans1,ans2),ans3),ans4),ans5),ans6);
    printf("%d\n",ans);
    if(ans==ans1){cout<<s1<<endl;return 0;}
    else if(ans==ans2){cout<<s2<<endl;return 0;}
    else if(ans==ans3){cout<<s3<<endl;return 0;}
    else if(ans==ans4){cout<<s4<<endl;return 0;}
    else if(ans==ans5){cout<<s5<<endl;return 0;}
    else if(ans==ans6){cout<<s6<<endl;return 0;}
}

 


Codeforces 1108 D. Diverse Garland

time limit per test1 second memory limit per test256 megabytes

You have a garland consisting of ?n lamps. Each lamp is colored red, green or blue. The color of the ?i-th lamp is ??si (‘R’, ‘G’ and ‘B’ — colors of lamps in the garland).

You have to recolor some lamps in this garland (recoloring a lamp means changing its initial color to another) in such a way that the obtained garland is diverse.

A garland is called diverse if any two adjacent (consecutive) lamps (i. e. such lamps that the distance between their positions is 11) have distinct colors.

In other words, if the obtained garland is ?t then for each ?i from 11 to ?−1n−1 the condition ??≠??+1ti≠ti+1 should be satisfied.

Among all ways to recolor the initial garland to make it diverse you have to choose one with the minimum number of recolored lamps. If there are multiple optimal solutions, print any of them.Input

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

The second line of the input contains the string ?s consisting of ?n characters ‘R’, ‘G’ and ‘B’ — colors of lamps in the garland.Output

In the first line of the output print one integer ?r — the minimum number of recolors needed to obtain a diverse garland from the given one.

In the second line of the output print one string ?t of length ?n — a diverse garland obtained from the initial one with minimum number of recolors. If there are multiple optimal solutions, print any of them.
Examplesinput

9 
RBGRRBRGG

output

2 
RBGRGBRGR

input

8 
BBBGBRRR

output

2 
BRBGBRGR

input

13 
BBRRRRGGGGGRR

output

6 
BGRBRBGBGBGRG

题解:对于每个灯笼,如果它和前面那个颜色一样,就把它换成和后面颜色不一样的颜色,这样肯定是最优解

#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 INF=0x3f3f3f3f;
int main(){
    int n;cin>>n;
    map<int,char> mp;
    mp[0]='R';mp[1]='G';mp[2]='B';
    string str;getline(cin,str);str+='0';
    int ans=0;
    for(int i=1;i<n;++i){
        if(str[i]==str[i-1]){
            for(int j=0;j<3;++j){
                if(mp[j]!=str[i]&&mp[j]!=str[i+1]){
                    str[i]=mp[j];ans++;break;
                }
            }
        }
    }
    str.erase(str.length()-1);
    printf("%d\n",ans);
    cout<<str<<endl;
}

 


Codeforces 1108 E1. Array and Segments (Easy version)

time limit per test2 seconds memory limit per test256 megabytes

The only difference between easy and hard versions is a number of elements in the array.

You are given an array ?a consisting of ?n integers. The value of the ?i-th element of the array is ??ai.

You are also given a set of ?m segments. The ?j-th segment is [??;??][lj;rj], where 1≤??≤??≤?1≤lj≤rj≤n.

You can choose some subset of the given set of segments and decrease values on each of the chosen segments by one (independently). For example, if the initial array ?=[0,0,0,0,0]a=[0,0,0,0,0] and the given segments are [1;3][1;3] and [2;4][2;4] then you can choose both of them and the array will become ?=[−1,−2,−2,−1,0]b=[−1,−2,−2,−1,0].

You have to choose some subset of the given segments (each segment can be chosen at most once) in such a way that if you apply this subset of segments to the array ?a and obtain the array ?b then the value max?=1???−min?=1???maxi=1nbi−mini=1nbi will be maximum possible.

Note that you can choose the empty set.

If there are multiple answers, you can print any.

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

The first line of the input contains two integers ?n and ?m (1≤?≤300,0≤?≤3001≤n≤300,0≤m≤300) — the length of the array ?a and the number of segments, respectively.

The second line of the input contains ?n integers ?1,?2,…,??a1,a2,…,an (−106≤??≤106−106≤ai≤106), where ??ai is the value of the ?i-th element of the array ?a.

The next ?m lines are contain two integers each. The ?j-th of them contains two integers ??lj and ??rj (1≤??≤??≤?1≤lj≤rj≤n), where ??lj and ??rj are the ends of the ?j-th segment.Output

In the first line of the output print one integer ?d — the maximum possible value max?=1???−min?=1???maxi=1nbi−mini=1nbi if ?b is the array obtained by applying some subset of the given segments to the array ?a.

In the second line of the output print one integer ?q (0≤?≤?0≤q≤m) — the number of segments you apply.

In the third line print ?q distinct integers ?1,?2,…,??c1,c2,…,cq in any order (1≤??≤?1≤ck≤m) — indices of segments you apply to the array ?a in such a way that the value max?=1???−min?=1???maxi=1nbi−mini=1nbi of the obtained array ?b is maximum possible.

If there are multiple answers, you can print any.

input

5 4 
2 -2 3 1 2
1 3
4 5
2 5
1 3

output

6 
2
1 4

input

5 4 
2 -2 3 1 4
3 5
3 4
2 4
2 5

output

7 
2
3 2

input

1 
0
1000000

output

0 
0

Note

In the first example the obtained array ?b will be [0,−4,1,1,2][0,−4,1,1,2] so the answer is 66.

In the second example the obtained array ?b will be [2,−3,1,−1,4][2,−3,1,−1,4] so the answer is 77.

In the third example you cannot do anything so the answer is 00.

题解:暴力,枚举每个点,假设这个点是最大的数,然后枚举区间,如果这个区间不包括这个点就用,最后求一个最大差值

#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 INF=0x3f3f3f3f;
int main(){
    int n,m;
    pair<int,int> p[305];
    vector<int> v;
    int pre[305], a[305];
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&p[i].first, &p[i].second);
    }
    int cnt;
    int ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i == j) continue;
            cnt = 0;
            int xx = a[j] - a[i];
            for(int k=1;k<=m;k++){
                if(i >= p[k].first && i <= p[k].second && (j < p[k].first || j > p[k].second)){
                    pre[cnt++] = k;
                    xx ++;
                }
            }
            if(ans < xx){ 
                ans = xx;
                v.clear();
                for(int i=0;i<cnt;i++) v.push_back(pre[i]);
            }
        }
    }
    cout<<ans<<endl;
    cout<<v.size()<<endl;
    for(int i=0;i<v.size();i++){
        cout<<v[i]<<" ";
    }
    return 0;
}

 


F. MST Unification

time limit per test3 seconds memory limit per test256 megabytes

You are given an undirected weighted connected graph with 𝑛n vertices and 𝑚m edges without loops and multiple edges.

The 𝑖i-th edge is 𝑒𝑖=(𝑢𝑖,𝑣𝑖,𝑤𝑖)ei=(ui,vi,wi); the distance between vertices 𝑢𝑖ui and 𝑣𝑖vi along the edge 𝑒𝑖ei is 𝑤𝑖wi (1≤𝑤𝑖1≤wi). The graph is connected, i. e. for any pair of vertices, there is at least one path between them consisting only of edges of the given graph.

A minimum spanning tree (MST) in case of positive weights is a subset of the edges of a connected weighted undirected graph that connects all the vertices together and has minimum total cost among all such subsets (total cost is the sum of costs of chosen edges).

You can modify the given graph. The only operation you can perform is the following: increase the weight of some edge by 11. You canincrease the weight of each edge multiple (possibly, zero) times.

Suppose that the initial MST cost is 𝑘k. Your problem is to increase weights of some edges with minimum possible number of operations in such a way that the cost of MST in the obtained graph remains 𝑘k, but MST is unique (it means that there is only one way to choose MST in the obtained graph).

Your problem is to calculate the minimum number of operations required to do it.Input

The first line of the input contains two integers 𝑛n and 𝑚m (1≤𝑛≤2⋅105,𝑛−1≤𝑚≤2⋅1051≤n≤2⋅105,n−1≤m≤2⋅105) — the number of vertices and the number of edges in the initial graph.

The next 𝑚m lines contain three integers each. The 𝑖i-th line contains the description of the 𝑖i-th edge 𝑒𝑖ei. It is denoted by three integers 𝑢𝑖,𝑣𝑖ui,viand 𝑤𝑖wi (1≤𝑢𝑖,𝑣𝑖≤𝑛,𝑢𝑖≠𝑣𝑖,1≤𝑤≤1091≤ui,vi≤n,ui≠vi,1≤w≤109), where 𝑢𝑖ui and 𝑣𝑖vi are vertices connected by the 𝑖i-th edge and 𝑤𝑖wi is the weight of this edge.

It is guaranteed that the given graph doesn’t contain loops and multiple edges (i.e. for each 𝑖i from 11 to 𝑚m 𝑢𝑖≠𝑣𝑖ui≠vi and for each unordered pair of vertices (𝑢,𝑣)(u,v) there is at most one edge connecting this pair of vertices). It is also guaranteed that the given graph is connected.Output

Print one integer — the minimum number of operations to unify MST of the initial graph without changing the cost of MST.
Examplesinput

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

output

1

input

4 3
2 1 3
4 3 4
2 4 1

output

0

input

3 3
1 2 1
2 3 2
1 3 3

output

0

input

3 3
1 2 1
2 3 3
1 3 3

output

1

input

1 0

output

0

input

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

output

2

Note

The picture corresponding to the first example:

You can, for example, increase weight of the edge (1,6)(1,6) or (6,3)(6,3) by 11 to unify MST.

The picture corresponding to the last example:

You can, for example, increase weights of edges (1,5)(1,5) and (2,4)(2,4) by 11 to unify MST.

先把所有边按照边权进行排序,然后再去处理矛盾的边

#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 INF=0x3f3f3f3f;
int pre[maxn];
int n,m;
struct node{
    int fr,to,dis;
}edge[maxn];
int cmp(node a,node b){return a.dis<b.dis;}
void init(){rep(i,0,n) pre[i]=i;}
int find(int x){return x==pre[x]?x:pre[x]=find(pre[x]);}
void join(int x,int y){
    x=find(x);y=find(y);
    if(x!=y) pre[x]=y;
}
int main(){
	cin>>n>>m;init();
    int ans=0;
    rep(i,0,m-1) scanf("%d%d%d",&edge[i].fr,&edge[i].to,&edge[i].dis);
    sort(edge,edge+m,cmp);
    for(int i=0;i<m;){
        int num=0,j=i;
        while(edge[j].dis==edge[i].dis) j++;
        for(int k=i;k<j;++k){
            if(find(edge[k].fr)!=find(edge[k].to)) num++;
        }
        for(int k=i;k<j;++k){
            if(find(edge[k].fr)!=find(edge[k].to)){
                join(find(edge[k].fr),find(edge[k].to));
                num--;
            }
        } ans+=num; i=j;
    }
    printf("%d\n",ans);
}

 

发表评论,支持MarkDown语法