Codeforces Round #508（ABCD）

A. Equality

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a string $\mathrm{ss of\; length nn,\; which\; consists\; only\; of\; the\; first kk letters\; of\; the\; Latin\; alphabet.\; All\; letters\; in\; string ss are\; uppercase.}$

A subsequence of string $\mathrm{ss is\; a\; string\; that\; can\; be\; derived\; from ss by\; deleting\; some\; of\; its\; symbols\; without\; changing\; the\; order\; of\; the\; remaining\; symbols.\; For\; example,\; "ADE"\; and\; "BD"\; are\; subsequences\; of\; "ABCDE",\; but\; "DEA"\; is\; not.}$

A subsequence of $\mathrm{ss called good if\; the\; number\; of\; occurences\; of\; each\; of\; the\; first kk letters\; of\; the\; alphabet\; is\; the\; same.}$

Find the length of the longest good subsequence of $\mathrm{ss.}$

Input

The first line of the input contains integers $\mathrm{nn (1\le n\le 1051\le n\le 105)\; and kk (1\le k\le 261\le k\le 26).}$

The second line of the input contains the string $\mathrm{ss of\; length nn.\; String ss only\; contains\; uppercase\; letters\; from\; \text{'}A\text{'}\; to\; the kk-th\; letter\; of\; Latin\; alphabet.}$

Output

Print the only integer — the length of the longest good subsequence of string $\mathrm{ss.}$

Examples

input

Copy

9 3
ACAABCCAB

output

Copy

6

input

Copy

9 4
ABCABCABC

output

Copy

0

Note

In the first example, "ACBCAB" ("ACAABCCAB") is one of the subsequences that has the same frequency of 'A', 'B' and 'C'. Subsequence "CAB" also has the same frequency of these letters, but doesn't have the maximum possible length.

In the second example, none of the subsequences can have 'D', hence the answer is $00.$

标记字母出现的次数

#include <iostream>
using namespace std;
int an[26];
int main(){
    int n,m;
    cin>>n>>m;
    string s;
    cin>>s;
    for(int i = 0; i < s.length(); ++i){
        an[s[i]-'A']++;
    }
    int ans = 100005;
    for(int i = 0; i < m; ++i){
        ans = min(ans,an[i]);
    }
    if(ans == 100005)
        ans = 0;
    cout<<ans*m<<endl;
    return 0;
}

B. Non-Coprime Partition

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Find out if it is possible to partition the first $\mathrm{nn positive\; integers\; into\; two non-empty disjoint\; sets S1S1 and S2S2 such\; that:}$

$\mathrm{gcd(sum(S1),sum(S2))>1gcd(sum(S1),sum(S2))>1}$

Here $\mathrm{sum(S)sum(S) denotes\; the\; sum\; of\; all\; elements\; present\; in\; set SS and gcdgcd means\; thegreatest\; common\; divisor.}$

Every integer number from $\mathrm{11 to nn should\; be\; present\; in exactly\; one of S1S1 or S2S2.}$

Input

The only line of the input contains a single integer $\mathrm{nn (1\le n\le 450001\le n\le 45000)}$

Output

If such partition doesn't exist, print "No" (quotes for clarity).

Otherwise, print "Yes" (quotes for clarity), followed by two lines, describing ${\mathrm{S1S1 and S2S2 respectively.}}^{}$

Each set description starts with the set size, followed by the elements of the set in any order. Each set must be non-empty.

If there are multiple possible partitions — print any of them.

Examples

input

Copy

1

output

Copy

No

input

Copy

3

output

Copy

Yes
1 2
2 1 3 

Note

In the first example, there is no way to partition a single number into two non-empty sets, hence the answer is "No".

In the second example, the sums of the sets are $\mathrm{22 and 44 respectively.\; The gcd(2,4)=2>1gcd(2,4)=2>1,\; hence\; that\; is\; one\; of\; the\; possible\; answers.}$

$\mathrm{判断是否为素数。}$

$\mathrm{然后按二进制插开输出。}$

#include <bits/stdc++.h>
#define N 45005
using namespace std;
int cnt = 0;

bool isprime(int x){
    bool flag = true;
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0){
            cnt = i;
            flag = false;
            break;
        }
    }
    return flag;
}
int a[N];
int vis[N];
int main(){
    int n;
    cin>>n;
    int ans = n*(n+1)/2;
    bool prime = isprime(ans);
    if(prime){
        cout<<"No"<<endl;
    }else{
        cout<<"Yes"<<endl;
        int ans = 0;
        int index = 1;
        while(cnt){
            if(cnt&1)
                a[ans++] = index,vis[index] = 1;
            index <<= 1;
            cnt >>= 1; 
        }
        cout<<ans<<" ";
        for(int i=0;i<ans;i++)
            cout<<a[i]<<" ";
        cout<<endl;
        cout<<n-ans<<" ";
        for(int i=1;i<=n;i++)
            if(vis[i]==0)
                cout<<i<<" ";
        cout<<endl;
    }
    return 0;
}

C. Gambling

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Two players A and B have a list of $\mathrm{nn integers\; each.\; They\; both\; want\; to\; maximize\; the\; subtraction\; between\; their\; score\; and\; their\; opponent\text{'}s\; score.}$

In one turn, a player can either add to his score any element from his list (assuming his list is not empty), the element is removed from the list afterward. Or remove an element from his opponent's list (assuming his opponent's list is not empty).

Note, that in case there are equal elements in the list only one of them will be affected in the operations above. For example, if there are elements $\{1,2,2,3\}\{1,2,2,3\} in\; a\; list\; and\; you\; decided\; to\; choose 22 for\; the\; next\; turn,\; only\; a\; single\; instance\; of 22 will\; be\; deleted\; (and\; added\; to\; the\; score,\; if\; necessary).$

The player A starts the game and the game stops when both lists are empty. Find the difference between A's score and B's score at the end of the game, if both of the players are playing optimally.

Optimal play between two players means that both players choose the best possible strategy to achieve the best possible outcome for themselves. In this problem, it means that each player, each time makes a move, which maximizes the final difference between his score and his opponent's score, knowing that the opponent is doing the same.

Input

The first line of input contains an integer $\mathrm{nn (1\le n\le 1000001\le n\le 100000) —\; the\; sizes\; of\; the\; list.}$

The second line contains $\mathrm{nn integers aiai (1\le ai\le 1061\le ai\le 106),\; describing\; the\; list\; of\; the\; player\; A,\; who\; starts\; the\; game.}$

The third line contains $\mathrm{nn integers bibi (1\le bi\le 1061\le bi\le 106),\; describing\; the\; list\; of\; the\; player\; B.}$

Output

Output the difference between A's score and B's score ($\mathrm{A-BA-B)\; if\; both\; of\; them\; are\; playing\; optimally.}$

Examples

input

Copy

2
1 4
5 1

output

Copy

0

input

Copy

3
100 100 100
100 100 100

output

Copy

0

input

Copy

2
2 1
5 6

output

Copy

-3

Note

In the first example, the game could have gone as follows:

• A removes $\mathrm{55 from\; B\text{'}s\; list.}$
• B removes $\mathrm{44 from\; A\text{'}s\; list.}$
• A takes his $11.$
• B takes his $11.$

Hence, A's score is $\mathrm{11,\; B\text{'}s\; score\; is 11 and\; difference\; is 00.}$

There is also another optimal way of playing:

• A removes $\mathrm{55 from\; B\text{'}s\; list.}$
• B removes $\mathrm{44 from\; A\text{'}s\; list.}$
• A removes $\mathrm{11 from\; B\text{'}s\; list.}$
• B removes $\mathrm{11 from\; A\text{'}s\; list.}$

The difference in the scores is still $00.$

In the second example, irrespective of the moves the players make, they will end up with the same number of numbers added to their score, so the difference will be $00.$

当自己的最大值大于别人的最大值时，就加自己的为分数，否则就删掉别人的。

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

priority_queue<ll, vector<ll>, less<ll> > qa,qb;
ll n,x;
int main(){
    cin>>n;
    for (int i = 0; i < n; ++i)
        cin>>x,qa.push(x);
    
    for (int i = 0; i < n; ++i)
        cin>>x,qb.push(x);
    ll aa = 0,bb = 0;
    while(!qa.empty()||!qb.empty()){
        if(qa.empty()){
            qb.pop();
        }else{
            if(qb.empty() || qa.top() > qb.top()){
                aa += qa.top(), qa.pop();
            }else{
                qb.pop();
            }
        }

        if(qb.empty()){
            qa.pop();
        }else{
            if(qa.empty() || qb.top() > qa.top()){
                bb += qb.top(), qb.pop();
            }else{
                qa.pop();
            }
        }
    }
    cout<<aa-bb<<endl;
    return 0;
}

D. Slime

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There are $\mathrm{nn slimes\; in\; a\; row.\; Each\; slime\; has\; an\; integer\; value\; (possibly\; negative\; or\; zero)\; associated\; with\; it.}$

Any slime can eat its adjacent slime (the closest slime to its left or to its right, assuming that this slime exists).

When a slime with a value $\mathrm{xx eats\; a\; slime\; with\; a\; value yy,\; the\; eaten\; slime\; disappears,\; and\; the\; value\; of\; the\; remaining\; slime\; changes\; to x-yx-y.}$

The slimes will eat each other until there is only one slime left.

Find the maximum possible value of the last slime.

Input

The first line of the input contains an integer $\mathrm{nn (1\le n\le 5000001\le n\le 500000)\; denoting\; the\; number\; of\; slimes.}$

The next line contains $\mathrm{nn integers aiai (-109\le ai\le 109-109\le ai\le 109),\; where aiai is\; the\; value\; of ii-th\; slime.}$

Output

Print an only integer — the maximum possible value of the last slime.

Examples

input

Copy

4
2 1 2 1

output

Copy

4

input

Copy

5
0 -1 -1 -1 -1

output

Copy

4

Note

In the first example, a possible way of getting the last slime with value $\mathrm{44 is:}$

• Second slime eats the third slime, the row now contains slimes $\mathrm{2,-1,12,-1,1}$
• Second slime eats the third slime, the row now contains slimes $\mathrm{2,-22,-2}$
• First slime eats the second slime, the row now contains $44$

In the second example, the first slime can keep eating slimes to its right to end up with a value of $44.$

当非负数和负数同事存在时，则只需要绝对值的累加和。

否则的话就是制造一个非正数。然后取最大值。

只需要遍历一次即可。

#include <bits/stdc++.h>
#define N 500000
#define ll long long int
using namespace std;

int n;
ll a[N];
int main(){
    scanf("%d",&n);
    ll ans = 0;
    bool prime = true, flag = true;
    for(int i = 0; i < n; ++i){
        scanf("%lld", &a[i]);
        ans += abs(a[i]);
        if(a[i]<0)
            prime = false;
        else
            flag = false;
    }
    if(n==1)
        cout<<a[0]<<endl;
    else{
        if(!prime && !flag){
            cout<<ans<<endl;
        }else{
            ll cnt = 0;
            for(int i = 1; i < n; ++i){
                ll an = ans - abs(a[i-1]) - abs(a[i]) + abs(a[i-1] - a[i]);
                cnt = max(cnt,an);
            }
            cout<<cnt<<endl;
        }
    }
    return 0;
}