Codeforces Round #529 (Div. 3)

A. Repeating Cipher

time limit per test1 second memory limit per test256 megabytes

Polycarp loves ciphers. He has invented his own cipher called repeating.

Repeating cipher is used for strings. To encrypt the string ?=?1?2…??s=s1s2…sm (1≤?≤101≤m≤10), Polycarp uses the following algorithm:

• he writes down ?1s1 ones,
• he writes down ?2s2 twice,
• he writes down ?3s3 three times,
• ...
• he writes down ??sm ?m times.

For example, if ?s="bab" the process is: "b" →→ "baa" →→ "baabbb". So the encrypted ?s="bab" is "baabbb".

Given string ?t — the result of encryption of some string ?s. Your task is to decrypt it, i. e. find the string ?s.Input

The first line contains integer ?n (1≤?≤551≤n≤55) — the length of the encrypted string. The second line of the input contains ?t — the result of encryption of some string ?s. It contains only lowercase Latin letters. The length of ?t is exactly ?n.

It is guaranteed that the answer to the test exists.Output

Print such string ?s that after encryption it equals ?t.
Examplesinput

6
baabbb

output

bab

input

10
ooopppssss

output

oops

input

1
z

output

z

签到

#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=(1<<16)+100;
const int INF=0x3f3f3f3f;
int main(){
int n;cin>>n;
string s;cin>>s;
string ans="";
int i=0,st=1;
while(i<n){
ans+=s[i];
i+=st++;
} cout<<ans;
}

B. Array Stabilization

time limit per test1 second memory limit per test256 megabytes

You are given an array ?a consisting of ?n integer numbers.

Let instability of the array be the following value: max?=1???−min?=1???maxi=1nai−mini=1nai.

You have to remove exactly one element from this array to minimize instability of the resulting (?−1)(n−1)-elements array. Your task is to calculate the minimum possible instability.Input

The first line of the input contains one integer ?n (2≤?≤1052≤n≤105) — the number of elements in the array ?a.

The second line of the input contains ?n integers ?1,?2,…,??a1,a2,…,an (1≤??≤1051≤ai≤105) — elements of the array ?a.Output

Print one integer — the minimum possible instability of the array if you have to remove exactly one element from the array ?a.
Examplesinput

4
1 3 3 7

output

2

input

2
1 100000

output

0

Note

In the first example you can remove 77 then instability of the remaining array will be 3−1=23−1=2.

In the second example you can remove either 11 or 100000100000 then instability of the remaining array will be 100000−100000=0100000−100000=0and 1−1=01−1=0 correspondingly.

sort一下就可以了

#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)1e5+100;
const int INF=0x3f3f3f3f;
int main(){
int n;cin>>n;
int a[maxn]={0,};
rep(i,1,n) scanf("%d",&a[i]);
sort(a+1,a+1+n);
if(n==2) puts("0");
else{
int ans=min(a[n-1]-a,a[n]-a);
cout<<ans<<endl;
}
}

C. Powers Of Two

time limit per test4 seconds memory limit per test256 megabytes

A positive integer ?x is called a power of two if it can be represented as ?=2?x=2y, where ?y is a non-negative integer. So, the powers of two are 1,2,4,8,16,…1,2,4,8,16,….

You are given two positive integers ?n and ?k. Your task is to represent ?n as the sum of exactly ?k powers of two.Input

The only line of the input contains two integers ?n and ?k (1≤?≤1091≤n≤109, 1≤?≤2⋅1051≤k≤2⋅105).Output

If it is impossible to represent ?n as the sum of ?k powers of two, print NO.

Otherwise, print YES, and then print ?k positive integers ?1,?2,…,??b1,b2,…,bk such that each of ??bi is a power of two, and ∑?=1???=?∑i=1kbi=n. If there are multiple answers, you may print any of them.
Examplesinput

9 4

output

YES
1 2 2 4

input

8 1

output

YES
8

input

5 1

output

NO

input

3 7

output

NO

位运算，每次高位向低位移一次，直到sum等于k

#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,k;cin>>n>>k;
if(k>n) {puts("NO");exit(0);}
int a,pos=0,sum=0;
int x=n;
while(x){
a[++pos]=x&1;
x>>=1;
if(a[pos]) sum++;
}
while(sum<k){
if(pos==1) break;
if(a[pos]){
a[pos-1]+=2;
a[pos]--;
}
if(!a[pos]) pos--;
sum++;
}
if(sum!=k) {puts("NO");exit(0);}
puts("YES");
int t=1;
rep(i,1,pos){
rep(j,1,a[i]) printf("%d ",t);
t<<=1;
}
}

D. Circular Dance

time limit per test3 seconds memory limit per test256 megabytes

There are ?n kids, numbered from 11 to ?n, dancing in a circle around the Christmas tree. Let's enumerate them in a clockwise direction as ?1p1, ?2p2, ..., ??pn (all these numbers are from 11 to ?n and are distinct, so ?p is a permutation). Let the next kid for a kid ??pi be kid ??+1pi+1 if ?<?i<n and ?1p1 otherwise. After the dance, each kid remembered two kids: the next kid (let's call him ?x) and the next kid for ?x. Each kid told you which kids he/she remembered: the kid ?i remembered kids ??,1ai,1 and ??,2ai,2. However, the order of ??,1ai,1 and ??,2ai,2can differ from their order in the circle.

Example: 5 kids in a circle, ?=[3,2,4,1,5]p=[3,2,4,1,5] (or any cyclic shift). The information kids remembered is: ?1,1=3a1,1=3, ?1,2=5a1,2=5; ?2,1=1a2,1=1, ?2,2=4a2,2=4; ?3,1=2a3,1=2, ?3,2=4a3,2=4; ?4,1=1a4,1=1, ?4,2=5a4,2=5; ?5,1=2a5,1=2, ?5,2=3a5,2=3.

You have to restore the order of the kids in the circle using this information. If there are several answers, you may print any. It is guaranteed that at least one solution exists.

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

The first line of the input contains one integer ?n (3≤?≤2⋅1053≤n≤2⋅105) — the number of the kids.

The next ?n lines contain 22 integers each. The ?i-th line contains two integers ??,1ai,1 and ??,2ai,2 (1≤??,1,??,2≤?,??,1≠??,21≤ai,1,ai,2≤n,ai,1≠ai,2) — the kids the ?i-th kid remembered, given in arbitrary order.Output

Print ?n integers ?1p1, ?2p2, ..., ??pn — permutation of integers from 11 to ?n, which corresponds to the order of kids in the circle. If there are several answers, you may print any (for example, it doesn't matter which kid is the first in the circle). It is guaranteed that at least one solution exists.
Examplesinput

5
3 5
1 4
2 4
1 5
2 3

output

3 2 4 1 5

input

3
2 3
3 1
1 2

output

3 1 2

第一次从1开始选，之后有两种可能a和b，枚举两个可能；在枚举过程中，已知当前点和上一个点时，可以推出下一个点，那么就可以得出整条链，遇到不能走下去的情况就是一开始选ab时选错了，换一个走就好了

#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 a[maxn],b[maxn];
int ck(int now,int has){
if(a[now]==has) return b[now];
else if(b[now]==has) return a[now];
else return -1;
}
int main(){
int n;cin>>n;
rep(i,1,n) scanf("%d%d",&a[i],&b[i]);
int flag=0;
vector<int> ans; ans.pb(1);
int tem=a,pre=1;
rep(i,1,n){
ans.pb(tem);
int pp=pre;
pre=tem;
tem=ck(pp,tem);
if(tem==-1){flag=1;break;}
}
if(flag){
ans.clear();ans.pb(1);
int tem=b,pre=1;
rep(i,1,n){
ans.pb(tem);
int pp=pre;
pre=tem;
tem=ck(pp,tem);
if(tem==-1){flag=1;break;}
}
}
for(int i=0;i<ans.size()-1;++i) printf("%d ",ans[i]);
}

E. Almost Regular Bracket Sequence

time limit per test3 seconds memory limit per test256 megabytes

You are given a bracket sequence ?s consisting of ?n opening '(' and closing ')' brackets.

regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example, bracket sequences "()()", "(())" are regular (the resulting expressions are: "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.

You can change the type of some bracket ??si. It means that if ??=si= ')' then you can change it to '(' and vice versa.

Your task is to calculate the number of positions ?i such that if you change the type of the ?i-th bracket, then the resulting bracket sequence becomes regular.Input

The first line of the input contains one integer ?n (1≤?≤1061≤n≤106) — the length of the bracket sequence.

The second line of the input contains the string ?s consisting of ?n opening '(' and closing ')' brackets.Output

Print one integer — the number of positions ?i such that if you change the type of the ?i-th bracket, then the resulting bracket sequence becomes regular.
Examplesinput

6
(((())

output

3

input

6
()()()

output

0

input

1
)

output

0

input

8
)))(((((

output

0

枚举每个位置，如果这个位置左边的‘（’和右边的‘）’相差1则有可能实现变化后合法

#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)1e6+100;
const int INF=0x3f3f3f3f;
int main(){
int n;cin>>n;
string s;cin>>s;
s='@'+s+'@';
int ans=0,tot=0;
int l[maxn],r[maxn];
l=r[n+1]=0;
rep(i,1,n){
if(s[i]=='(') tot++;
else tot--;
if(tot<0||l[i-1]<0) l[i]=-1;
else l[i]=tot;
}
tot=0;
dep(i,n,1){
if(s[i]==')') tot++;
else tot--;
if(tot<0||r[i+1]<0) r[i]=-1;
else r[i]=tot;
}
rep(i,1,n){
if(l[i-1]>=0&&r[i+1]>=0){
int t=l[i-1]-r[i+1];
if(t==1&&s[i]=='(')  ans++;
if(t==-1&&s[i]==')') ans++;
}
}
printf("%d\n",ans);
}

F. Make It Connected

time limit per test2 seconds memory limit per test256 megabytes

You are given an undirected graph consisting of ?n vertices. A number is written on each vertex; the number on vertex ?i is ??ai. Initially there are no edges in the graph.

You may add some edges to this graph, but you have to pay for them. The cost of adding an edge between vertices ?x and ?y is ??+??ax+ay coins. There are also ?m special offers, each of them is denoted by three numbers ?x, ?y and ?w, and means that you can add an edge connecting vertices ?x and ?y and pay ?w coins for it. You don't have to use special offers: if there is a pair of vertices ?xand ?y that has a special offer associated with it, you still may connect these two vertices paying ??+??ax+ay coins for it.

What is the minimum number of coins you have to spend to make the graph connected? Recall that a graph is connected if it's possible to get from any vertex to any other vertex using only the edges belonging to this graph.Input

The first line contains two integers ?n and ?m (1≤?≤2⋅1051≤n≤2⋅105, 0≤?≤2⋅1050≤m≤2⋅105) — the number of vertices in the graph and the number of special offers, respectively.

The second line contains ?n integers ?1,?2,…,??a1,a2,…,an (1≤??≤10121≤ai≤1012) — the numbers written on the vertices.

Then ?m lines follow, each containing three integers ?x, ?y and ?w (1≤?,?≤?1≤x,y≤n, 1≤?≤10121≤w≤1012, ?≠?x≠y) denoting a special offer: you may add an edge connecting vertex ?x and vertex ?y, and this edge will cost ?w coins.Output

Print one integer — the minimum number of coins you have to pay to make the graph connected.
Examplesinput

3 2
1 3 3
2 3 5
2 1 1

output

5

input

4 0
1 3 3 7

output

16

input

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

output

18

Note

In the first example it is possible to connect 11 to 22 using special offer 22, and then 11 to 33 without using any offers.

In next two examples the optimal answer may be achieved without using special offers.

并查集裸题，注意开long long

#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 ll INF=(ll)1e15;
ll a[maxn],c[maxn],n,num=0;
ll ans=0;
struct node{
ll u,v,w;
bool operator <(const node& b) const{return w<b.w;}
}g[maxn<<1];
ll pre[maxn];
ll find(ll x){return x==pre[x]?x:pre[x]=find(pre[x]);}
void join(){
rep(i,1,num){
ll x=find(g[i].u);
ll y=find(g[i].v);
if(x!=y) pre[x]=y,ans+=g[i].w;
}
}
int main(){
int m;cin>>n>>m;
ll minx=INF,id=0;
rep(i,1,n){
pre[i]=i;
scanf("%lld",&a[i]);
if(a[i]<minx) minx=a[i],id=i;
}
rep(i,1,m){
ll u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
w=min(w,a[u]+a[v]);
g[++num].u=u; g[num].v=v; g[num].w=w;
}
rep(i,1,n){
if(i==id) continue;
g[++num].u=i; g[num].v=id; g[num].w=a[i]+a[id];
}
sort(g+1,g+1+num);
join(); printf("%lld\n",ans);
}

0 评论