Codeforces Round #575 #579

A. Three Piles of Candies 

Alice and Bob have received three big piles of candies as a gift. Now they want to divide these candies as fair as possible. To do this, Alice takes one pile of candies, then Bob takes one of the other two piles. The last pile is split between Alice and Bob as they want: for example, it is possible that Alice takes the whole pile, and Bob gets nothing from it.

After taking the candies from the piles, if Alice has more candies than Bob, she discards some candies so that the number of candies she has is equal to the number of candies Bob has. Of course, Bob does the same if he has more candies.

Alice and Bob want to have as many candies as possible, and they plan the process of dividing candies accordingly. Please calculate the maximum number of candies Alice can have after this division process (of course, Bob will have the same number of candies).

You have to answer qq independent queries.

Let's see the following example: [1,3,4][1,3,4]. Then Alice can choose the third pile, Bob can take the second pile, and then the only candy from the first pile goes to Bob — then Alice has 44 candies, and Bob has 44 candies.

Another example is [1,10,100][1,10,100]. Then Alice can choose the second pile, Bob can choose the first pile, and candies from the third pile can be divided in such a way that Bob takes 5454 candies, and Alice takes 4646 candies. Now Bob has 5555 candies, and Alice has 5656 candies, so she has to discard one candy — and after that, she has 5555 candies too.

Input

The first line of the input contains one integer qq (1≤q≤10001≤q≤1000) — the number of queries. Then qq queries follow.

The only line of the query contains three integers a,ba,b and cc (1≤a,b,c≤10161≤a,b,c≤1016) — the number of candies in the first, second and third piles correspondingly.

Output

Print qq lines. The ii-th line should contain the answer for the ii-th query — the maximum number of candies Alice can have after the division, if both Alice and Bob act optimally (of course, Bob will have the same number of candies).

Example

input

Copy

4
1 3 4
1 10 100
10000000000000000 10000000000000000 10000000000000000
23 34 45

output

Copy

4
55
15000000000000000
51

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;long long a,b,c;
    cin>>t;
    while(t--)
    {
        cin>>a>>b>>c;
        cout<<(a+b+c)/2<<endl;
        
    }
return 0;
} 

C. Common Divisors 

You are given an array aa consisting of nn integers.

Your task is to say the number of such positive integers xx such that xx divides each number from the array. In other words, you have to find the number of common divisors of all elements in the array.

For example, if the array aa will be [2,4,6,2,10][2,4,6,2,10], then 11 and 22 divide each number from the array (so the answer for this test is 22).

Input

The first line of the input contains one integer nn (1≤n≤4⋅1051≤n≤4⋅105) — the number of elements in aa.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤10121≤ai≤1012), where aiai is the ii-th element of aa.

Output

Print one integer — the number of such positive integers xx such that xx divides each number from the given array (in other words, the answer is the number of common divisors of all elements in the array).

Examples

input

5
1 2 3 4 5

output

1

input

6
6 90 12 18 30 18

output

4

题意：给出n个正整数，找出能整除这n个数的正整数个数。

分析：即求最大公因数的因子个数。

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
typedef long long ll;
using namespace std;
const int INT=1e6+5;
#define lson rt<<1, l, m  
#define rson rt<<1|1, m+1, r
#define read(x) scanf("%d",&x)
#define lread(x) scanf("%lld",&x);
#define pt(x) printf("%d
",(x))
#define cn cin>>
#define ct cout<<
#define en <<endl
#define rep(j,k) for (int i = (int)(j); i <= (int)(k); i++)
#define mem(s,t) memset(s,t,sizeof(s))
#define re return 0;
#define TLE std::ios::sync_with_stdio(false);
ll a[100000+5],b[10000+5];
priority_queue<ll>q1,q2;
int main()
{
    TLE;
    ll t,n,m,mx,flag,k=0,cnt=0;
    cn n;
    rep(1,n)
    {
        cn m;
        k=__gcd(m,k);
    }
    rep(1,sqrt(k))
    {
        if(k%i) continue;
        else
        {
            cnt++;
            if(i!=k/i) cnt++;   //计数 sqrt(k) ~ k范围内的公约数

　　　　　}
 　　} 
　　ct cnt en; 
　　re ; 
}

D1. RGB Substring (easy version) 

The only difference between easy and hard versions is the size of the input.

You are given a string ss consisting of nn characters, each character is 'R', 'G' or 'B'.

You are also given an integer kk. Your task is to change the minimum number of characters in the initial string ss so that after the changes there will be a string of length kk that is a substring of ss, and is also a substring of the infinite string "RGBRGBRGB ...".

A string aa is a substring of string bb if there exists a positive integer ii such that a1=bia1=bi, a2=bi+1a2=bi+1, a3=bi+2a3=bi+2, ..., a|a|=bi+|a|−1a|a|=bi+|a|−1. For example, strings "GBRG", "B", "BR" are substrings of the infinite string "RGBRGBRGB ..." while "GR", "RGR" and "GGG" are not.

You have to answer qq independent queries.

Input

The first line of the input contains one integer qq (1≤q≤20001≤q≤2000) — the number of queries. Then qq queries follow.

The first line of the query contains two integers nn and kk (1≤k≤n≤20001≤k≤n≤2000) — the length of the string ss and the length of the substring.

The second line of the query contains a string ss consisting of nn characters 'R', 'G' and 'B'.

It is guaranteed that the sum of nn over all queries does not exceed 20002000 (∑n≤2000∑n≤2000).

Output

For each query print one integer — the minimum number of characters you need to change in the initial string ss so that after changing there will be a substring of length kk in ss that is also a substring of the infinite string "RGBRGBRGB ...".

Example

input

Copy

3
5 2
BGGGG
5 3
RBRGR
5 5
BBBRR

output

Copy

1
0
3

Note

In the first example, you can change the first character to 'R' and obtain the substring "RG", or change the second character to 'R' and obtain "BR", or change the third, fourth or fifth character to 'B' and obtain "GB".

In the second example, the substring is "BRG".

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
#define N 500005
char str[N];
char t[N];
int a[N],sum[N];
int main()
{
    int q;
    scanf("%d",&q);
    while(q--)
    {
 
        int n,k;
        scanf("%d%d",&n,&k);
        scanf("%s",str+1);
 
        for(int i=1;i<=n+100;i+=3)
        {
            t[i]='R';
            t[i+1]='G';
            t[i+2]='B';
        }
        int ans=1e18;
        for(int j=1;j<=3;j++)
        {
            for(int i=1;i<=n;i++)
            {
                if(t[i+j-1]!=str[i])
                    a[i]=1;
                else
                    a[i]=0;
            }
            for(int i=1;i<=n;i++)
            {
                sum[i]=sum[i-1]+a[i];
            }
 
            for(int i=k;i<=n;i++)
            {
                ans=min(ans,sum[i]-sum[i-k]);
            }
        }
        cout<<ans<<endl;
 
 
    }
    return 0;
}

D2. RGB Substring (hard version) 

The only difference between easy and hard versions is the size of the input.

You are given a string ss consisting of nn characters, each character is 'R', 'G' or 'B'.

You are also given an integer kk. Your task is to change the minimum number of characters in the initial string ss so that after the changes there will be a string of length kk that is a substring of ss, and is also a substring of the infinite string "RGBRGBRGB ...".

A string aa is a substring of string bb if there exists a positive integer ii such that a1=bia1=bi, a2=bi+1a2=bi+1, a3=bi+2a3=bi+2, ..., a|a|=bi+|a|−1a|a|=bi+|a|−1. For example, strings "GBRG", "B", "BR" are substrings of the infinite string "RGBRGBRGB ..." while "GR", "RGR" and "GGG" are not.

You have to answer qq independent queries.

Input

The first line of the input contains one integer qq (1≤q≤2⋅1051≤q≤2⋅105) — the number of queries. Then qq queries follow.

The first line of the query contains two integers nn and kk (1≤k≤n≤2⋅1051≤k≤n≤2⋅105) — the length of the string ss and the length of the substring.

The second line of the query contains a string ss consisting of nn characters 'R', 'G' and 'B'.

It is guaranteed that the sum of nn over all queries does not exceed 2⋅1052⋅105 (∑n≤2⋅105∑n≤2⋅105).

Output

For each query print one integer — the minimum number of characters you need to change in the initial string ss so that after changing there will be a substring of length kk in ss that is also a substring of the infinite string "RGBRGBRGB ...".

#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 2e5+7;
int n,k;
string ori = "RGB";
string s;
int a[maxn],sum[maxn];
int solve(int st)
{
    for(int i=0; i<s.size(); i++)
    {
        a[i]=(s[i]==ori[(st+i)%3]?0:1);
        sum[i]=(i>0?a[i]+sum[i-1]:a[i]);
    }
    int res = s.size();
    for(int i=k-1; i<s.size(); i++)
    {
        res = min(res, sum[i]-(i-k>=0?sum[i-k]:0));
    }
    return res;
}
void solve()
{
    scanf("%d%d",&n,&k);
    cin>>s;
    int ans = s.size();
    for(int st=0; st<3; st++)
    {
        ans = min(ans, solve(st));
    }
    printf("%d
", ans);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        solve();
    }
    return 0;
}

E. Boxers 

There are nn boxers, the weight of the ii-th boxer is aiai. Each of them can change the weight by no more than 11 before the competition (the weight cannot become equal to zero, that is, it must remain positive). Weight is always an integer number.

It is necessary to choose the largest boxing team in terms of the number of people, that all the boxers' weights in the team are different (i.e. unique).

Write a program that for given current values ​aiai will find the maximum possible number of boxers in a team.

It is possible that after some change the weight of some boxer is 150001150001 (but no more).

Input

The first line contains an integer nn (1≤n≤1500001≤n≤150000) — the number of boxers. The next line contains nn integers a1,a2,…,ana1,a2,…,an, where aiai (1≤ai≤1500001≤ai≤150000) is the weight of the ii-th boxer.

Output

Print a single integer — the maximum possible number of people in a team.

Examples

input

Copy

4
3 2 4 1

output

Copy

4

input

Copy

6
1 1 1 4 4 4

output

Copy

5

Note

In the first example, boxers should not change their weights — you can just make a team out of all of them.

In the second example, one boxer with a weight of 11 can be increased by one (get the weight of 22), one boxer with a weight of 44 can be reduced by one, and the other can be increased by one (resulting the boxers with a weight of 33 and 55, respectively). Thus, you can get a team consisting of boxers with weights of 5,4,3,2,15,4,3,2,1.

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
typedef long long ll;
using namespace std;
const int INT=1e6+5;
#define lson rt<<1, l, m  
#define rson rt<<1|1, m+1, r
#define read(x) scanf("%d",&x)
#define lread(x) scanf("%lld",&x);
#define pt(x) printf("%d
",(x))
#define cn cin>>
#define ct cout<<
#define en <<endl
#define rep(j,k) for (int i = (int)(j); i <= (int)(k); i++)
#define input(k) for (int i = 1; i <= (int)(k); i++)  {cin>>a[i] ; }
#define mem(s,t) memset(s,t,sizeof(s))
#define re return 0;
#define TLE std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int a[151000];
bool vis[151000];
int main()
{
    TLE;
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    int sum = 0;
    for(int i = 1; i <= n; ++i){
        if(!vis[a[i]-1] && a[i] != 1){ vis[a[i]-1] = true; sum++;continue; }
        if(!vis[a[i]]){ vis[a[i]] = true; sum++;continue; }
        if(!vis[a[i]+1]){ vis[a[i]+1] = true; sum++;continue; }
    }
    cout<<sum<<endl;
    return 0;
}

 F. K-th Path 

 

You are given a connected undirected weighted graph consisting of nn vertices and mm edges.

You need to print the kk-th smallest shortest path in this graph (paths from the vertex to itself are not counted, paths from ii to jj and from jjto ii are counted as one).

More formally, if dd is the matrix of shortest paths, where di,jdi,j is the length of the shortest path between vertices ii and jj (1≤i<j≤n1≤i<j≤n), then you need to print the kk-th element in the sorted array consisting of all di,jdi,j, where 1≤i<j≤n1≤i<j≤n.

Input

The first line of the input contains three integers n,mn,m and kk (2≤n≤2⋅1052≤n≤2⋅105, n−1≤m≤min(n(n−1)2,2⋅105)n−1≤m≤min(n(n−1)2,2⋅105), 1≤k≤min(n(n−1)2,400)1≤k≤min(n(n−1)2,400) — the number of vertices in the graph, the number of edges in the graph and the value of kk, correspondingly.

Then mm lines follow, each containing three integers xx, yy and ww (1≤x,y≤n1≤x,y≤n, 1≤w≤1091≤w≤109, x≠yx≠y) denoting an edge between vertices xx and yy of weight ww.

It is guaranteed that the given graph is connected (there is a path between any pair of vertices), there are no self-loops (edges connecting the vertex with itself) and multiple edges (for each pair of vertices xx and yy, there is at most one edge between this pair of vertices in the graph).

Output

Print one integer — the length of the kk-th smallest shortest path in the given graph (paths from the vertex to itself are not counted, paths from ii to jj and from jj to ii are counted as one).

Examples

input

Copy

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

output

Copy

3

input

Copy

7 15 18
2 6 3
5 7 4
6 5 4
3 6 9
6 7 7
1 6 4
7 1 6
7 2 1
4 3 2
3 2 8
5 3 6
2 5 5
3 7 9
4 1 8
2 1 1

output

Copy

9

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define N 500005
struct Node
{
    ll index;
    ll u,v,w;
 
} arc;
bool cmp(Node x,Node y)
{
    return x.w<y.w;
}
vector<Node>e;
vector<ll>vert;
ll dist[1010][1010];
int main()
{
    ll n,m,k;
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1; i<=m; i++)
    {
        ll a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
      //  a--;b--;
        arc.u=a;
        arc.v=b;
        arc.w=c;
        e.push_back(arc);
    }
 
    sort(e.begin(),e.end(),cmp);
 
    for(int i=0; i<min(m,k); i++)
    {
        vert.push_back(e[i].u);
        vert.push_back(e[i].v);
    }
 
    sort(vert.begin(),vert.end());
    
    vert.resize(unique(vert.begin(), vert.end()) - vert.begin());
    
 
    int cntv = vert.size();
    
    memset(dist,0x3f,sizeof(dist));
    
    for(int i=0; i<=cntv; i++)
    {
        dist[i][i]=0;
    }
    
 
    for (int i = 0; i < min(m, k); ++i)
    {
        int x = lower_bound(vert.begin(), vert.end(), e[i].u) - vert.begin();
        
        int y = lower_bound(vert.begin(), vert.end(), e[i].v) - vert.begin();
        
     //   cout<<x<<" "<<y<<"    "<<e[i].w<<endl;
        dist[x][y] = dist[y][x] = min(dist[x][y], e[i].w);
    }
 
    for (int z = 0; z <cntv; ++z)
    {
        for (int x = 0; x <cntv; ++x)
        {
            for (int y = 0; y <cntv; ++y)
            {
                dist[x][y] = min(dist[x][y], dist[x][z] + dist[z][y]);
            }
        }
    }
    
    vector<ll> res;
    for (int i = 0; i <= cntv; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            res.push_back(dist[i][j]);
        }
    }
 
    sort(res.begin(), res.end());
    cout << res[k - 1] << endl;
 
    return 0;
}