CodeForces 825C(贪心)-蒲公英云

CodeForces 825C(贪心)

r囧r小猫 2022-06-06 13:00 255阅读 0赞

问题描述:

Makes solves problems on Decoforces and lots of other different online judges. Each problem is denoted by its difficulty — a positive integer number. Difficulties are measured the same across all the judges (the problem with difficulty d on Decoforces is as hard as the problem with difficulty d on any other judge).

Makes has chosen n problems to solve on Decoforces with difficulties a1, a2, …, an. He can solve these problems in arbitrary order. Though he can solve problem i with difficulty ai only if he had already solved some problem with difficulty b62c9d4e5642f890a7dac1e8671969eb_v_1509638843 (no matter on what online judge was it).

Before starting this chosen list of problems, Makes has already solved problems with maximum difficulty k.

With given conditions it’s easy to see that Makes sometimes can’t solve all the chosen problems, no matter what order he chooses. So he wants to solve some problems on other judges to finish solving problems from his list.

For every positive integer y there exist some problem with difficulty y on at least one judge besides Decoforces.

Makes can solve problems on any judge at any time, it isn’t necessary to do problems from the chosen list one right after another.

Makes doesn’t have too much free time, so he asked you to calculate the minimum number of problems he should solve on other judges in order to solve all the chosen problems from Decoforces.

Input

The first line contains two integer numbers n, k (1 ≤ n ≤ 103, 1 ≤ k ≤ 109).

The second line contains n space-separated integer numbers a1, a2, …, an (1 ≤ ai ≤ 109).

Output

Print minimum number of problems Makes should solve on other judges in order to solve all chosen problems on Decoforces.

Example

Input

3 3
2 1 9

Output

Input

4 20
10 3 6 3

Output

题目题意:CF现在有n道题目，需要我们解决，每道题目的难度系数为k，我们当前可以做的最高的系数KM，我们可以做每道题目必须满足2*kM>=k，而且如果我们成功做出了K，那么我们的kM=max(kM,k), 现在我们为了做完n题，问还需要最少解决其他oj的题目。因为如果我们解决不了当前的题目，我们就需要解决别的题目，来提升KM

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int a[1010];
int main()
{
    int n,k;
    while (scanf("%d%d",&n,&k)!=EOF) {
        for (int i=0;i<n;i++) {
            scanf("%d",&a[i]);
        }
        sort (a,a+n);
        int ans=0;
        for (int i=0;i<n;i++) {
            if (a[i]<=k*2) {
                k=max(k,a[i]);
                continue;
            }
            else {
                k=k*2;
                ans++;
                i--;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}