CF825C.Multi-judge Solving

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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_1, _a_2, ..., 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.

Makes 在 Decoforces 以及其他众多在线评测系统(online judges)上解决题目。每道题用一个正整数表示其难度。所有评测系统的难度标度是统一的(即在 Decoforces 上难度为 dd 的题目,与在任意其他评测系统上难度为 dd 的题目难度相同)。

Makes 已从 Decoforces 中挑选了 nn 道题目来解决,其难度分别为 a1, a2, …, ana_1,\,a_2,\,\dots,\,a_n。他可以按任意顺序求解这些题目。但只有当他已经解决过某道难度为 的题目(无论该题出自哪个评测系统)时,他才能解决第 ii 道难度为 aia_i 的题目。

在开始解决这组选定题目之前,Makes 已经解决了若干题目,其中最高难度为 kk。

在给定条件下,显然 Makes 有时无论如何安排求解顺序,都无法完成全部选定题目。因此,他希望先在其他评测系统上解决一些题目,以确保最终能完成 Decoforces 上的全部选定题目。

对每个正整数 yy,至少存在一个除 Decoforces 外的评测系统,其上有一道难度为 yy 的题目。

Makes 可以在任意时刻、在任意评测系统上求解题目,无需将选定列表中的题目连续求解。

由于 Makes 的空闲时间有限,他请你计算:为完成 Decoforces 上全部选定题目,他最少需要在其他评测系统上额外求解多少道题目。

输入格式

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

The second line contains n space-separated integer numbers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109).

第一行包含两个整数 $ n 、、 k (( 1 \leq n \leq 10^3 ,, 1 \leq k \leq 10^9 $)。

第二行包含 $ n $ 个用空格分隔的整数 $ a_1,,a_2,,...,,a_n (( 1 \leq a_i \leq 10^9 $)。

输出格式

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

输出 Makes 为在 Decoforces 上解决所有选定题目,而需在其他评测系统上解决的最少题目数量。

输入输出样例

  • 输入#1

    3 3
    2 1 9

    输出#1

    1
  • 输入#2

    4 20
    10 3 6 3

    输出#2

    0

说明/提示

In the first example Makes at first solves problems 1 and 2. Then in order to solve the problem with difficulty 9, he should solve problem with difficulty no less than 5. The only available are difficulties 5 and 6 on some other judge. Solving any of these will give Makes opportunity to solve problem 3.

In the second example he can solve every problem right from the start.

在第一个例子中,Makes 首先解决了难度为 1 和 2 的问题。接着,为了求解难度为 9 的问题,他必须先解决一个难度不低于 5 的问题。此时唯一可选的是来自其他评测系统的、难度为 5 和 6 的问题。求解其中任意一个,都将使 Makes 获得求解问题 3 的资格。

在第二个例子中,他可以从一开始就解决所有问题。

输入解题思路,AI测评打分。不知道怎么写?

首页