原SDAU暑假训练第21天一周总结(2018819)

原SDAU暑假训练第21天一周总结(2018819)

本周把前面学过的DP大体的框架理顺溜了,尤其是背包之类的,感觉也没想象中的那么难。

到了疲惫期了,每天都感觉睡不够。

不过也是学到了很多东西,也见识到了什么是真正的学霸

还有最后一周,

撸起袖子加油干!

原CodeForces–1013AAPilesWithStones

原CodeForces–1013AAPilesWithStones

There is a beautiful garden of stones in Innopolis.

Its most beautiful place is the nn piles with stones numbered from 11 to nn.

EJOI participants have visited this place twice.

When they first visited it, the number of stones in piles was x1,x2,…,xnx1,x2,…,xn, correspondingly. One of the participants wrote down this sequence in a notebook.

They visited it again the following day, and the number of stones in piles was equal to y1,y2,…,yny1,y2,…,yn. One of the participants also wrote it down in a notebook.

It is well known that every member of the EJOI jury during the night either sits in the room 108108 or comes to the place with stones. Each jury member who comes there either takes one stone for himself or moves one stone from one pile to another. We can assume that there is an unlimited number of jury members. No one except the jury goes to the place with stones at night.

Participants want to know whether their notes can be correct or they are sure to have made a mistake.

 

Input

The first line of the input file contains a single integer nn, the number of piles with stones in the garden (1≤n≤501≤n≤50).

The second line contains nn integers separated by spaces x1,x2,…,xnx1,x2,…,xn, the number of stones in piles recorded in the notebook when the participants came to the place with stones for the first time (0≤xi≤10000≤xi≤1000).

The third line contains nn integers separated by spaces y1,y2,…,yny1,y2,…,yn, the number of stones in piles recorded in the notebook when the participants came to the place with stones for the second time (0≤yi≤10000≤yi≤1000).

Output

If the records can be consistent output “Yes”, otherwise output “No” (quotes for clarity).

Examples

input

Copy

5
1 2 3 4 5
2 1 4 3 5

output

Copy

Yes

input

Copy

5
1 1 1 1 1
1 0 1 0 1

output

Copy

Yes

input

Copy

3
2 3 9
1 7 9

output

Copy

No

Note

In the first example, the following could have happened during the night: one of the jury members moved one stone from the second pile to the first pile, and the other jury member moved one stone from the fourth pile to the third pile.

In the second example, the jury took stones from the second and fourth piles.

It can be proved that it is impossible for the jury members to move and took stones to convert the first array into the second array.

题目分析:吐槽!!!!题面看了老半天才看懂。。。明明就是个入门水题。。

有些人两次观察石头,首先,他们在观察石头。对于这么多堆的石头,他们在第二天可以移动石头到另一堆或直接拿走。问他们的观察每堆石头数量的记录是否有问题。如果是移动则总数不变,如果拿走则总数减少,所以第二堆石头一定不可能比第一堆多。所以我们只要比较第一天与第二天的数量之和就可以了,只要第一天的总和大于等于第二天,那么就是对的。

#include<iostream>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
  {
        int sum1=0,sum2=0;
        int a;
        for(int i=0;i<n;i++){
            cin>>a;
            sum1=sum1+a;
        }
        for(int i=0;i<n;i++){
            cin>>a;
            sum2=sum2+a;
        }
        if(sum2<=sum1)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

 

原CodeForces–1011BPlanningTheExpedit

原CodeForces–1011BPlanningTheExpedit

Natasha is planning an expedition to Mars for nn people. One of the important tasks is to provide food for each participant.

The warehouse has mm daily food packages. Each package has some food type aiai.

Each participant must eat exactly one food package each day. Due to extreme loads, each participant must eat the same food type throughout the expedition. Different participants may eat different (or the same) types of food.

Formally, for each participant jj Natasha should select his food type bjbj and each day jj-th participant will eat one food package of type bjbj. The values bjbj for different participants may be different.

What is the maximum possible number of days the expedition can last, following the requirements above?

 

Input

The first line contains two integers nn and mm (1≤n≤1001≤n≤100, 1≤m≤1001≤m≤100) — the number of the expedition participants and the number of the daily food packages available.

The second line contains sequence of integers a1,a2,…,ama1,a2,…,am (1≤ai≤1001≤ai≤100), where aiai is the type of ii-th food package.

Output

Print the single integer — the number of days the expedition can last. If it is not possible to plan the expedition for even one day, print 0.

Examples

input

Copy

4 10
1 5 2 1 1 1 2 5 7 2

output

Copy

2

input

Copy

100 1
1

output

Copy

0

input

Copy

2 5
5 4 3 2 1

output

Copy

1

input

Copy

3 9
42 42 42 42 42 42 42 42 42

output

Copy

3

Note

In the first example, Natasha can assign type 11 food to the first participant, the same type 11 to the second, type 55 to the third and type 22 to the fourth. In this case, the expedition can last for 22 days, since each participant can get two food packages of his food type (there will be used 44 packages of type 11, two packages of type 22 and two packages of type 55).

In the second example, there are 100100 participants and only 11 food package. In this case, the expedition can’t last even 11 day.

题目大意:n个人m个食物,每个食物都有种类,每个人只能吃一种食物(无论哪一种),求最多能活多少天。

思路:枚举可存活的天数,依次判断食物够多少人吃,若满足就更新最大存活天数。题目的英语不是特别容易懂。。

 

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 105;
int vis[N];  //每种食物的数量 
int main(){
  int n,m;
  scanf("%d%d",&n,&m);
  for(int i=0;i<m;i++){
    int x;
    scanf("%d",&x);
    vis[x]++;
  }
  int ans=0;
    for(int i=1;i<=m;i++){ //假设可以吃i天 
    	int cnt=0; //如果吃i天,可以供多少人吃 
        for(int j=1;j<=100;j++)
          cnt+=vis[j]/i;
        if(cnt>=n) ans=max(ans,i);
  }
  printf("%d\n",ans);
  return 0;
}

 

原CodeForces–1011AAStages

原CodeForces–1011AAStages

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 nn stages available. The rocket must contain exactly kk 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’ — 2626 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 — nn and kk (1≤k≤n≤501≤k≤n≤50) – the number of available stages and the number of stages to use in the rocket.

The second line contains string ss, which consists of exactly nn 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.

Examples

input

Copy

5 3
xyabd

output

Copy

29

input

Copy

7 4
problem

output

Copy

34

input

Copy

2 2
ab

output

Copy

-1

input

Copy

12 1
abaabbaaabbb

output

Copy

1

Note

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

  • “adx” (weight is 1+4+24=291+4+24=29);
  • “ady” (weight is 1+4+25=301+4+25=30);
  • “bdx” (weight is 2+4+24=302+4+24=30);
  • “bdy” (weight is 2+4+25=312+4+25=31).

Rocket “adx” has the minimal weight, so the answer is 2929.

In the second example, target rocket is “belo”. Its weight is 2+5+12+15=342+5+12+15=34.

In the third example, n=k=2n=k=2, so the rocket must have both stages: ‘a’ and ‘b’. This rocket doesn’t satisfy the condition, because these letters are adjacent in the alphabet. Answer is -1.

题意:

给你n,m,n个字母,求m个最小字母和,不能选连续的字母。

#include<bits/stdc++.h>
using namespace std;
char s[200];
int main()
{
    int n,m;
    cin>>n>>m;
  getchar();
    gets(s);
    sort(s,s+n);
    int sum=s[0]-'a'+1,k=1;
    char ans=s[0];
    for(int i=1;i<n;i++)
    {
        if(k==m) break;
        if(s[i]>ans+1)
    {
      k++;
      ans=s[i];
      sum=sum+s[i]-'a'+1;
    }
    }
    if(k==m)cout<<sum<<endl;
    else cout<<"-1"<<endl;
    return 0;
}

 

原SDAU暑假训练第20天DP训练(2018818)

原SDAU暑假训练第20天DP训练(2018818)

除了区间,树形,数位几种反人类的DP,

比较好想的基础DP例如背包啥的已经会了。

(这是背包九讲看完之后留下的自己觉着挺重要的内容背包九讲

明天开始启动区间DP的学习内容,希望开学之前能把DP搞的差不多。

 

另外 :

吐槽!!
     今天进行安全加固改数据库的前缀时的时候不小心把服务器系统弄坏了。。尽力去修了,没弄好,现在用了16号的备份镜像才恢复过来,凭着印象最大的还原的案发前的现场,但是昨天和前天的大概四篇文章还是没了,没有保住。。。

永远怀念我的那四篇文章

算了,昨天和前天发的题会了就行,累死我了。。
以后一定要经常备份!!
休息去了。

补充,自己的博客可以用很漂亮的字体,真舒服。比如上面的吐槽 这里这里。幼圆大法好。

原SDAU暑假训练第18天做题(2018816)

原SDAU暑假训练第18天做题(2018816)

训练第18天了啊。今天是16号了,还有一周半就结束了。

感觉前面看数学知识好像又开始有遗忘了。看来强扭的瓜不甜,必须深刻理解才行。

队内分工是我搞数据结构,图论,今天有一部分时间看了这个,另外也看了看DP,也是前面训练的全都忘了。

HDU一直关着,很烦。做了几个洛谷的题,挑了几个题解发我新博客上了,点击查看

备注:两个博客大概一周同步一次,新博客上只会挑一些比较精华的东西发过去,是CSDN的子集。CSDN依旧发文章(因为我怕哪天服务器会崩掉)