B - Japanese Cursed Doll Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200

問題文

N 人の人がおり、i 人目 (1\leq i\leq N) の現在の髪の長さは L_i です。
すべての人は 1 日経つごとに髪の長さが 1 ずつ増えます。

髪の長さが T 以上の人が初めて P 人以上になるのは現在から何日後か出力してください。
ただし、現在の時点ですでに髪の長さが T 以上の人が P 人以上にいる場合は 0 を出力してください。

制約

  • 1\leq N\leq 100
  • 1\leq L_i\leq 100
  • 1\leq T\leq 100
  • 1\leq P\leq N
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N T P
L_1 L_2 \ldots L_N

出力

髪の長さが T 以上の人が初めて P 人以上になるのは現在から何日後か出力せよ。 ただし、現在の時点ですでに条件をみたしている場合は 0 を出力せよ。


入力例 1

5 10 3
3 11 1 6 2

出力例 1

7

5 人の人がおり、現在の時点で髪の長さはそれぞれ 3,11,1,6,2 であるため、髪の長さが 10 以上の人は 1 人です。

現在から 7 日後にはそれぞれの人の髪の長さは順に 10,18,8,13,9 となり、髪の長さが 10 以上の人は 3 人となります。
現在から 6 日後の時点では髪の長さが 10 以上の人は 2 人であるため条件をみたしておらず、よって 7 を出力します。


入力例 2

2 5 2
10 10

出力例 2

0

現在の時点ですでに髪の長さが 5 以上の人が 2 人いるため条件をみたしており、0 を出力します。


入力例 3

3 10 1
1 2 3

出力例 3

7

Score : 200 points

Problem Statement

There are N people, and the current hair length of the i-th person (1 \leq i \leq N) is L_i.
Each person's hair grows by 1 per day.

Print the number of days after which the number of people whose hair length is at least T becomes P or more for the first time.
If there are already P or more people whose hair length is at least T now, print 0.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq L_i \leq 100
  • 1 \leq T \leq 100
  • 1 \leq P \leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N T P
L_1 L_2 \ldots L_N

Output

Print the number of days after which the number of people whose hair length is at least T becomes P or more for the first time. If this condition is already satisfied now, print 0.


Sample Input 1

5 10 3
3 11 1 6 2

Sample Output 1

7

There are five people, and their current hair lengths are 3, 11, 1, 6, 2, so there is one person whose hair length is at least 10.

After seven days, the hair lengths of the people will be 10, 18, 8, 13, 9, respectively, and there will be three people whose hair length is at least 10.
After six days, there are only two people whose hair length is at least 10, not satisfying the condition, so print 7.


Sample Input 2

2 5 2
10 10

Sample Output 2

0

Since there are already two people whose hair length is at least 5 now, satisfying the condition, so print 0.


Sample Input 3

3 10 1
1 2 3

Sample Output 3

7