題目鏈接：http://codeforces.com/contest/825/problem/C

C. Multi-judge Solving

time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

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 a₁,?a₂,?...,?a_n. He can solve these problems in arbitrary order. Though he can solve problem i with difficulty a_i only if he had already solved some problem with difficulty (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?≤?10³, 1?≤?k?≤?10⁹).

The second line contains n space-separated integer numbers a₁,?a₂,?...,?a_n (1?≤?a_i?≤?10⁹).

Output

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

Examples

Input

3 3
2 1 9

Output

1

Input

4 20
10 3 6 3

Output

　0

題目大意：

有個人想在CF上做題，每個題目有一個難度系數，現在這個人打算在CF上做n道題，這個人目前做出來的最高系數難度的題目是k，并且我們知道，對于難度系數為ai的題目，如果他已經做出來一道題d,且有2*d>=ai,他就能做出來ai這道題，否則的話，他就需要去BOJ上找一道題來做，使得他能做ai這道題。請問他至少要到BOJ上做幾道題，才能全部做完n道題。

題解：

先排序，之后掃一遍，一邊判斷能做否，一邊更新k。遇到不能做時候就去BOJ做一題ans++，然后繼續更新k，輸出ans...

代碼：

#include<cstring> #include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define maxn 1005 int main() {int n,k,a[maxn];while(cin>>n>>k){int ans=0;for(int i=0;i<n;i++) scanf("%d",&a[i]);sort(a,a+n);for(int i=0;i<n;i++){if(a[i]<k*2) k=max(a[i],k);else{while(a[i]>k*2) {k*=2; ans++;}k=max(a[i],k);}}cout<<ans<<endl;} }

?

轉載于:https://www.cnblogs.com/weimeiyuer/p/7204306.html

總結

以上是生活随笔為你收集整理的Educational Codeforces Round 25 C. Multi-judge Solving的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。