8月5号团队赛补题

 1.Commentary Boxes

Description

Berland Football Cup starts really soon! Commentators from all over the world come to the event.

Organizers have already built $\mathrm{nn commentary\; boxes. mm regional\; delegations\; will\; come\; to\; the\; Cup.\; Every\; delegation\; should\; get\; the same\; number of\; the\; commentary\; boxes.\; If\; any\; box\; is\; left\; unoccupied\; then\; the\; delegations\; will\; be\; upset. So\; each\; box\; should\; be\; occupied\; by\; exactly\; one\; delegation.}$

If $\mathrm{nn is\; not\; divisible\; by mm,\; it\; is\; impossible\; to\; distribute\; the\; boxes\; to\; the\; delegations\; at\; the\; moment.}$

Organizers can build a new commentary box paying $\mathrm{aa burles\; and\; demolish\; a\; commentary\; box\; paying bb burles.\; They\; can\; both\; build\; and\; demolish\; boxes\; arbitrary\; number\; of\; times\; (each\; time\; paying\; a\; corresponding\; fee).\; It\; is\; allowed\; to\; demolish\; all\; the\; existing\; boxes.}$

What is the minimal amount of burles organizers should pay to satisfy all the delegations (i.e. to make the number of the boxes be divisible by $\mathrm{mm)?}$

Input

The only line contains four integer numbers $\mathrm{nn, mm, aa and bb (1\le n,m\le 10121\le n,m\le 1012, 1\le a,b\le 1001\le a,b\le 100),\; where nn is\; the\; initial\; number\; of\; the\; commentary\; boxes, mm is\; the\; number\; of\; delegations\; to\; come, aa is\; the\; fee\; to\; build\; a\; box\; and bb is\; the\; fee\; to\; demolish\; a\; box.}$

Output

Output the minimal amount of burles organizers should pay to satisfy all the delegations (i.e. to make the number of the boxes be divisible by $\mathrm{mm).\; It\; is\; allowed\; that\; the\; final\; number\; of\; the\; boxes\; is\; equal\; to 00.}$

Sample Input

Input

9 7 3 8

Output

15

Input

2 7 3 7

Output

14

Input

30 6 17 19

Output

0

Hint

In the first example organizers can build $\mathrm{55 boxes\; to\; make\; the\; total\; of 1414 paying 33 burles\; for\; the\; each\; of\; them.}$

In the second example organizers can demolish $\mathrm{22 boxes\; to\; make\; the\; total\; of 00 paying 77 burles\; for\; the\; each\; of\; them.}$

In the third example organizers are already able to distribute all the boxes equally among the delegations, each one get $\mathrm{55 boxes.}$

$\mathrm{题目意思：足球赛之前要给每一支代表队分配评论框，每一支代表队都必须得到数量相同的评论框，现在有n个评论框，m支代表队，可以新建一些评论框代价是a，}$$\mathrm{也可以拆除一些评论框代价是b。问最后至少花费多少。}$

$\mathrm{解题思路：分别算出新建一些和拆除一些评论框的花费，找到最少的花费就行了。}$

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long int
using namespace std;
int main()
{
    ll n,m,a,b,x,y,ans1,ans2,ans;
    scanf("%lld%lld%lld%lld",&n,&m,&a,&b);
    x=n%m;
    y=n/m;
    ans1=x*b;///拆
    ans2=((y+1)*m-n)*a;//建
    ans=min(ans1,ans2);
    printf("%lld
",ans);
    return 0;
}

 

 2.Micro-World

You have a Petri dish with bacteria and you are preparing to dive into the harsh micro-world. But, unfortunately, you don't have any microscope nearby, so you can't watch them.

You know that you have $n$ bacteria in the Petri dish and size of the $i$-th bacteria is $a_i$. Also you know intergalactic positive integer constant $K$.

The $i$-th bacteria can swallow the $j$-th bacteria if and only if $a_i>a_j$ and $a_i\le a_j+K$. The $j$-th bacteria disappear, but the $i$-th bacteria doesn't change its size. The bacteria can perform multiple swallows. On each swallow operation any bacteria $i$ can swallow any bacteria $j$if $a_i>a_j$ and $a_i\le a_j+K$. The swallow operations go one after another.

For example, the sequence of bacteria sizes $a=[101,53,42,102,101,55,54]$ and $K=1$. The one of possible sequences of swallows is: $[101,53,42,102,\underset{–}{101},55,54]$ $\to$ $[101,\underset{–}{53},42,102,55,54]$ $\to$ $[\underset{–}{101},42,102,55,54]$ $\to$ $[42,102,55,\underset{–}{54}]$ $\to$ $[42,102,55]$. In total there are $3$ bacteria remained in the Petri dish.

Since you don't have a microscope, you can only guess, what the minimal possible number of bacteria can remain in your Petri dish when you finally will find any microscope.

Input

The first line contains two space separated positive integers $n$ and $K$ ($1\le n\le 2\cdot {10}^5$, $1\le K\le {10}^6$) — number of bacteria and intergalactic constant $K$.

The second line contains $n$ space separated integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le {10}^6$) — sizes of bacteria you have.

Output

Print the only integer — minimal possible number of bacteria can remain.

Examples

input

Copy

7 1
101 53 42 102 101 55 54

output

Copy

3

input

Copy

6 5
20 15 10 15 20 25

output

Copy

1

input

Copy

7 1000000
1 1 1 1 1 1 1

output

Copy

7

Note

The first example is clarified in the problem statement.

In the second example an optimal possible sequence of swallows is: $[20,15,10,15,\underset{–}{20},25]$ $\to$ $[20,15,10,\underset{–}{15},25]$ $\to$ $[20,15,\underset{–}{10},25]$ $\to$ $[20,\underset{–}{15},25]$ $\to$ $[\underset{–}{20},25]$ $\to$ $\left[25\right]$.

In the third example no bacteria can swallow any other bacteria.

题目意思：有n个细菌，每个细菌的尺寸为ai，现在有以常数k，如果细菌i的尺寸ai大于细菌j的尺寸aj，并且ai<=aj+k,那么细菌i就可以吃掉细菌j，问最后可以剩于多少个细菌。

解题思路：用map记录相同尺寸的细菌的个数，之后排序去重，遍历的是一类的细菌（尺寸相同的细菌归为一类），这样会降低时间复杂度。

 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
#define LL long long int
LL a[300010];
int main()
{
    LL m,n,i,j,l;
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        map<int,int>mp;
        memset(a,0,sizeof(a));
        for(i=0; i<n; i++)
        {
            scanf("%lld",&a[i]);
            mp[a[i]]++;
        }
        sort(a,a+n);
        l=unique(a,a+n)-a;
        for(i=1; i<l; i++)
        {
            if(a[i]>a[i-1]&&a[i-1]+m>=a[i])
            {
                n=n-mp[a[i-1]];
            }
        }
        printf("%lld
",n);
    }
    return 0;
}

 

 3.Strage

Description

Natasha is going to fly to Mars. She needs to build a rocket, which consists of several stages in some order. Each of the stages is defined by a lowercase Latin letter. This way, the rocket can be described by the string — concatenation of letters, which correspond to the stages.

There are $n$stages available. The rocket must contain exactly $k$of them. Stages in the rocket should be ordered by their weight. So, after the stage with some letter can go only stage with a letter, which is at least two positions after in the alphabet (skipping one letter in between, or even more). For example, after letter 'c' can't go letters 'a', 'b', 'c' and 'd', but can go letters 'e', 'f', ..., 'z'.

For the rocket to fly as far as possible, its weight should be minimal. The weight of the rocket is equal to the sum of the weights of its stages. The weight of the stage is the number of its letter in the alphabet. For example, the stage 'a 'weighs one ton,' b 'weighs two tons, and' z' — $26$tons.

Build the rocket with the minimal weight or determine, that it is impossible to build a rocket at all. Each stage can be used at most once.

Input

The first line of input contains two integers — $n$$\mathrm{and\; k\; (1\le k\le n\le 50}$) – the number of available stages and the number of stages to use in the rocket.

The second line contains string $s$$\mathrm{,\; which\; consists\; of\; exactly\; n}$lowercase Latin letters. Each letter defines a new stage, which can be used to build the rocket. Each stage can be used at most once.

Output

Print a single integer — the minimal total weight of the rocket or -1, if it is impossible to build the rocket at all.

Sample Input

Input

5 3
xyabd

Output

29

Input

7 4
problem

Output

34

Input

2 2
ab

Output

-1

Input

12 1
abaabbaaabbb

Output

1

Hint

In the first example, the following rockets satisfy the condition:

• "adx" (weight is $\mathrm{1+4+24=29}$);
• "ady" (weight is $\mathrm{1+4+25=0}$);
• "bdx" (weight is $\mathrm{2+4+24=30}$);
• "bdy" (weight is $\mathrm{2+4+25=31}$).

Rocket "adx" has the minimal weight, so the answer is $29$.

In the second example, target rocket is "belo". Its weight is $\mathrm{2+5+12+15=34}$.

In the third example, $\mathrm{n=k=2}$$\mathrm{,\; so\; the\; rocket\; must\; have\; both\; stages:\; \text{'}a\text{'}\; and\; \text{'}b\text{'}.\; This\; rocket\; doesn\text{'}t\; satisfy\; the\; condition,\; because\; these\; letters\; are\; adjacent\; in\; the}$

$\mathrm{alphabet.\; Answer\; is\; -1.}$

 题目意思：给一串字符串，让我们从其中取指定数量的字符，使得得到字符的值是所取的指定的数量所有字符中值最小的，这个取法规定是相邻的不能取，另一个要求是不能取这个字母之前的数。

解题思路：先排序，之后按照题目要求遍历一遍就可以了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
    return a<b;
}
int main()
{
    int a,b,i,j,k=0,ans=0;
    char x[10000],y[10000];
    scanf("%d %d",&a,&b);
    getchar();
    scanf("%s",&x);
    sort(x,x+a,cmp);
    for(i=0; i<a; i++)
    {
        if(x[i]-1!=y[k-1]&&x[i]!=y[k-1])///不相邻不相同
        {
            y[k++]=x[i];
        }
        if(k>=b)
        {
            break;
        }
    }
    for(i=0; i<k; i++)
    {
        ans+=y[i]-'a'+1;
    }
    if(k!=b)
    {
        printf("-1
");
    }
    else
    {
        printf("%d
",ans);
    }
    return 0;
}