Codeforces Round #526 (Div. 2)

A. The Fair Nut and Elevator

time limit per test1 second memory limit per test256 megabytes

The Fair Nut lives in 𝑛n story house. 𝑎𝑖ai people live on the 𝑖i-th floor of the house. Every person uses elevator twice a day: to get from the floor where he/she lives to the ground (first) floor and to get from the first floor to the floor where he/she lives, when he/she comes back home in the evening.

It was decided that elevator, when it is not used, will stay on the 𝑥x-th floor, but 𝑥x hasn’t been chosen yet. When a person needs to get from floor 𝑎a to floor 𝑏b, elevator follows the simple algorithm:

• Moves from the 𝑥x-th floor (initially it stays on the 𝑥x-th floor) to the 𝑎a-th and takes the passenger.
• Moves from the 𝑎a-th floor to the 𝑏b-th floor and lets out the passenger (if 𝑎a equals 𝑏b, elevator just opens and closes the doors, but stillcomes to the floor from the 𝑥x-th floor).
• Moves from the 𝑏b-th floor back to the 𝑥x-th.

The elevator never transposes more than one person and always goes back to the floor 𝑥x before transposing a next passenger. The elevator spends one unit of electricity to move between neighboring floors. So moving from the 𝑎a-th floor to the 𝑏b-th floor requires |𝑎−𝑏||a−b|units of electricity.

Your task is to help Nut to find the minimum number of electricity units, that it would be enough for one day, by choosing an optimal the 𝑥x-th floor. Don’t forget than elevator initially stays on the 𝑥x-th floor.Input

The first line contains one integer 𝑛n (1≤𝑛≤1001≤n≤100) — the number of floors.

The second line contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (0≤𝑎𝑖≤1000≤ai≤100) — the number of people on each floor.Output

In a single line, print the answer to the problem — the minimum number of electricity units.
Examples
input

30 2 1

output

16

input

21 1

output

4

Note

In the first example, the answer can be achieved by choosing the second floor as the 𝑥x-th floor. Each person from the second floor (there are two of them) would spend 44 units of electricity per day (22 to get down and 22 to get up), and one person from the third would spend 88units of electricity per day (44 to get down and 44 to get up). 4⋅2+8⋅1=164⋅2+8⋅1=16.

In the second example, the answer can be achieved by choosing the first floor as the 𝑥x-th floor.

作为一道签到题，这个题意并不难，让你选择一个电梯的初始楼层，告诉你每层楼的人数，让你算出每天电梯要走多少层。考虑到n<100，暴力！

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define sc3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
#define Exit {printf("-1\n");exit(0);}
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define maxn int(5e5)+100
#define mod int(1e9)+7
using namespace std;
int main(){
int n;sc(n);
int a[110];
rep(i,1,n) sc(a[i]);
int ans=INF;
rep(i,1,n){
int tot=0;
rep(j,1,n){
if(j<=i){
tot+=a[j]*(i-1)*4;
}
else tot+=a[j]*(j-1)*4;
}
ans=min(ans,tot);
}
pr(ans);
return 0;
}


B. Kvass and the Fair Nut

time limit per test1 second memory limit per test256 megabytes

The Fair Nut likes kvass very much. On his birthday parents presented him 𝑛n kegs of kvass. There are 𝑣𝑖vi liters of kvass in the 𝑖i-th keg. Each keg has a lever. You can pour your glass by exactly 11 liter pulling this lever. The Fair Nut likes this drink very much, so he wants to pour his glass by 𝑠s liters of kvass. But he wants to do it, so kvass level in the least keg is as much as possible.

Help him find out how much kvass can be in the least keg or define it’s not possible to pour his glass by 𝑠s liters of kvass.Input

The first line contains two integers 𝑛n and 𝑠s (1≤𝑛≤1031≤n≤103, 1≤𝑠≤10121≤s≤1012) — the number of kegs and glass volume.

The second line contains 𝑛n integers 𝑣1,𝑣2,…,𝑣𝑛v1,v2,…,vn (1≤𝑣𝑖≤1091≤vi≤109) — the volume of 𝑖i-th keg.Output

If the Fair Nut cannot pour his glass by 𝑠s liters of kvass, print −1−1. Otherwise, print a single integer — how much kvass in the least keg can be.
Examples
input

3 34 3 5

output

3

input

3 45 3 4

output

2

inputCopy

3 71 2 3

outputCopy

-1

Note

In the first example, the answer is 33, the Fair Nut can take 11 liter from the first keg and 22 liters from the third keg. There are 33 liters of kvass in each keg.

In the second example, the answer is 22, the Fair Nut can take 33 liters from the first keg and 11 liter from the second keg.

In the third example, the Fair Nut can’t pour his cup by 77 liters, so the answer is −1−1.

11-大佬告诉我用二分（原谅我不知道怎么用），事实证明弱鸡的代码也是可以a的

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define sc3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
#define Exit {printf("-1\n");exit(0);}
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define maxn int(5e5)+100
#define mod int(1e9)+7
using namespace std;
int main(){
int n;sc(n);
ll k;scanf("%lld",&k);
ll tot=0;
ll minx=INF;
FF(i,n){
ll x;
scanf("%lld",&x);
tot+=x;
minx=min(minx,x);
}
if(tot<k){
printf("-1\n");
exit(0);
}
printf("%lld\n",min(minx,(tot-k)/n));
return 0;
}


C. The Fair Nut and String

time limit per test1 second memory limit per test256 megabytes

The Fair Nut found a string 𝑠s. The string consists of lowercase Latin letters. The Nut is a curious guy, so he wants to find the number of strictly increasing sequences 𝑝1,𝑝2,…,𝑝𝑘p1,p2,…,pk, such that:

1. For each 𝑖i (1≤𝑖≤𝑘1≤i≤k), 𝑠𝑝𝑖=spi= ‘a’.
2. For each 𝑖i (1≤𝑖<𝑘1≤i<k), there is such 𝑗j that 𝑝𝑖<𝑗<𝑝𝑖+1pi<j<pi+1 and 𝑠𝑗=sj= ‘b’.

The Nut is upset because he doesn’t know how to find the number. Help him.

This number should be calculated modulo 109+7109+7.Input

The first line contains the string 𝑠s (1≤|𝑠|≤1051≤|s|≤105) consisting of lowercase Latin letters.Output

In a single line print the answer to the problem — the number of such sequences 𝑝1,𝑝2,…,𝑝𝑘p1,p2,…,pk modulo 109+7109+7.
Examples
input

abbaa

output

5

input

baaaa

output

4

input

agaa

output

3

Note

In the first example, there are 55 possible sequences. [1][1], [4][4], [5][5], [1,4][1,4], [1,5][1,5].

In the second example, there are 44 possible sequences. [2][2], [3][3], [4][4], [5][5].

In the third example, there are 33 possible sequences. [1][1], [3][3], [4][4].

题意有点搞，半天没读懂，其实就是找首位都是a，并且两个a之间存在b的子段的数量，简单dp

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define sc3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
#define Exit {printf("-1\n");exit(0);}
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define maxn int(1e5)+100
#define mod (int(1e9)+7)
using namespace std;
int main(){
string t;cin>>t;
string s;
FF(i,t.length()){
if(t[i]=='a'){
s+=t[i];
}
else if(t[i]=='b'){
if(s.length()&&s[s.length()-1]=='b') continue;
else s+=t[i];
}
}
//cout<<s.length()<<endl;
int pre=0;
int v[maxn];
mst(v,0);
FF(i,s.length()){
if(s[i]=='b'){
if(i==0)
v[i]=0;
else{
v[i]=v[i-1];
pre=v[i-1];
}
}
else{
if(i==0) v[i]=1;
else {v[i]=(v[i-1]+pre+1)%mod;}
//cout<<tot<<endl;
}
//cout<<v[i]<<endl;
//cout<<s[i]<<" "<<v[i]<<endl;
}
pr(v[s.length()-1]);
return 0;
}


D. The Fair Nut and the Best Path

time limit per test3 seconds memory limit per test256 megabytes

The Fair Nut is going to travel to the Tree Country, in which there are 𝑛n cities. Most of the land of this country is covered by forest. Furthermore, the local road system forms a tree (connected graph without cycles). Nut wants to rent a car in the city 𝑢u and go by a simple path to city 𝑣v. He hasn’t determined the path, so it’s time to do it. Note that chosen path can consist of only one vertex.

A filling station is located in every city. Because of strange law, Nut can buy only 𝑤𝑖wi liters of gasoline in the 𝑖i-th city. We can assume, that he has infinite money. Each road has a length, and as soon as Nut drives through this road, the amount of gasoline decreases by length. Of course, Nut can’t choose a path, which consists of roads, where he runs out of gasoline. He can buy gasoline in every visited city, even in the first and the last.

He also wants to find the maximum amount of gasoline that he can have at the end of the path. Help him: count it.Input

The first line contains a single integer 𝑛n (1≤𝑛≤3⋅1051≤n≤3⋅105) — the number of cities.

The second line contains 𝑛n integers 𝑤1,𝑤2,…,𝑤𝑛w1,w2,…,wn (0≤𝑤𝑖≤1090≤wi≤109) — the maximum amounts of liters of gasoline that Nut can buy in cities.

Each of the next 𝑛−1n−1 lines describes road and contains three integers 𝑢u, 𝑣v, 𝑐c (1≤𝑢,𝑣≤𝑛1≤u,v≤n, 1≤𝑐≤1091≤c≤109, 𝑢≠𝑣u≠v), where 𝑢u and 𝑣v — cities that are connected by this road and 𝑐c — its length.

It is guaranteed that graph of road connectivity is a tree.Output

Print one number — the maximum amount of gasoline that he can have at the end of the path.
Examples
input

31 3 31 2 21 3 2

output

3

input

56 3 2 5 01 2 102 3 32 4 11 5 1

output

7

Note

The optimal way in the first example is 2→1→32→1→3.

The optimal way in the second example is 2→42→4.

学了一手树型dp，dp[i]表示编号为i的节点最大的贡献，但是对于每个点能产生的答案是这个节点的子节点中最大值和次大值的和（因为可以从最大值节点经过当前节点再回到次大节点），因此每次更新ans和节点信息的时候要记录一下最大和次大，然后dfs搜到底再回溯上来就可以了

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define sc3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
#define Exit {printf("-1\n");exit(0);}
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define maxn (int(3e5)+100)
#define mod (int(1e9)+7)
using namespace std;
struct node{
int v,w;
};
vector<node> g[maxn];//存边
ll w[maxn];
int vis[maxn];
ll dp[maxn];
ll ans=0;
int n;
void tree_dp(int s,int fa){
vis[s]=1;dp[s]=w[s];ll maxx=-INF;ll cmax=-INF;
FF(i,g[s].size()){
if(g[s][i].v!=fa&&vis[g[s][i].v]==0){
tree_dp(g[s][i].v,s);
if(max(0ll,dp[g[s][i].v]-g[s][i].w)>maxx){//更新最大值和次大值
cmax=maxx;
maxx=max(0ll,dp[g[s][i].v]-g[s][i].w);
}
else if(max(0ll,dp[g[s][i].v]-g[s][i].w)>cmax){//更新次大值
cmax=max(0ll,dp[g[s][i].v]-g[s][i].w);
}
}
}
ans=max(ans,maxx+cmax+w[s]);//更新答案
dp[s]+=max(0ll,maxx);//s节点能产生的最大贡献
ans=max(ans,dp[s]);
}
int main(){
sc(n);
rep(i,1,n) sc(w[i]),ans=max(ans,w[i]);//原地不动的情况
rep(i,1,n-1){
int u,v,w;sc3(u,v,w);
g[u].pb({v,w});
g[v].pb({u,w});
}
mst(vis,0);
tree_dp(1,1);
printf("%lld\n",ans);
return 0;
}


E. The Fair Nut and Strings

time limit per test1 second memory limit per test256 megabytes

Recently, the Fair Nut has written 𝑘k strings of length 𝑛n, consisting of letters “a” and “b”. He calculated 𝑐c — the number of strings that are prefixes of at least one of the written strings. Every string was counted only one time.

Then, he lost his sheet with strings. He remembers that all written strings were lexicographically not smaller than string 𝑠s and not biggerthan string 𝑡t. He is interested: what is the maximum value of 𝑐c that he could get.

A string 𝑎a is lexicographically smaller than a string 𝑏b if and only if one of the following holds:

• 𝑎a is a prefix of 𝑏b, but 𝑎≠𝑏a≠b;
• in the first position where 𝑎a and 𝑏b differ, the string 𝑎a has a letter that appears earlier in the alphabet than the corresponding letter in 𝑏b.

Input

The first line contains two integers 𝑛n and 𝑘k (1≤𝑛≤5⋅1051≤n≤5⋅105, 1≤𝑘≤1091≤k≤109).

The second line contains a string 𝑠s (|𝑠|=𝑛|s|=n) — the string consisting of letters “a” and “b.

The third line contains a string 𝑡t (|𝑡|=𝑛|t|=n) — the string consisting of letters “a” and “b.

It is guaranteed that string 𝑠s is lexicographically not bigger than 𝑡t.Output

Print one number — maximal value of 𝑐c.
Examples
input

2 4 aa bb

output

6


input

3 3 aba bba

output

8


input

4 5 abbb baaa

output

8


Note

In the first example, Nut could write strings “aa”, “ab”, “ba”, “bb”. These 44 strings are prefixes of at least one of the written strings, as well as “a” and “b”. Totally, 66 strings.

In the second example, Nut could write strings “aba”, “baa”, “bba”.

In the third example, there are only two different strings that Nut could write. If both of them are written, 𝑐=8c=8.