14085: Коровакадемія I-Acowdemia I-USACO2021OpenBronze


Відправити розв'язок

Бали: 100 (partial)
Time limit: 2.0s
Memory limit: 500M

Authors:
Problem type
Allowed languages
Brain****, C, C++, Java, Pascal, Python, v8js

Бесі навчається на PhD у комп'ютерних науках. Вона опублікувала \(N\) статей (\(1 \leq N \leq 10^5\)) і її \(i\)-у статтю цитували \(c_i\) раз (\(0 \leq c_i \leq 10^5\)).

Бесі чула, що академічні успіхи вимірюються \(h\)-індексом. \(h\)-індекс - це найбільше число \(h\) таке, що вчений має не менше \(h\) статей, кожна з яких цитується не менше \(h\) разів. Наприклад, вчений у якого чотири статті з кількостями цитат \((1,100,2,3)\) має \(h\)-індекс рівний \(2\), а вчений з кількостями цитат (1,100,3,3) має \(h\)-індекс рівний \( 3\).

Щоб підвищити свій \(h\)-індекс Бесі планує написати оглядову статтю, яка цитує деякі з її минулих статей. У зв'язку з обмеженням на кількість сторінок, вона може включити не більше \(L\) цитат у свій огляд (\(0 \leq L \leq 10^5\)), і звичайно вона може процитувати кожну зі своїх статей не більше одного разу.

Допоможіть Бесі визначити максимальний \(h\)-індекс, який вона може досягти написанням своєї оглядової статті.

Зауважимо, що науковий керівник повинен був попередити Бесі, що написання статті виключно з метою збільшення свого \(h\)-індексу сумнівно з етичної точки зору.

Формат вхідних даних

Перший рядок введення містить \(N\) та \(L\).

Другий рядок введення містить \(N\) розділених одиночними пробілами цілих чисел \(c_1,\ldots, c_N\).

Формат вихідних даних

Максимальний \(h\)-індекс, який Бесі може отримати написанням оглядової статті.

Приклад вхідних даних

4 0
1 100 2 3

Приклад вихідних даних

2

Бесі не може цитувати свої статті. Як зазначено раніше її \(h\)-індекс для \((1,100,2,3)\) дорівнює \(2\).

Приклад вхідних даних

4 1
1 100 2 3

Приклад вихідних даних

3

Якщо Бесі процитує третю статтю, її кількості цитувань стануть \((1,100,3,3)\). Як зазначено раніше, \(h\) у цьому випадку дорівнює \(3\).

ОЦІНЮВАННЯ:

  • У тестах 1-7 \(N \leq 100\).
  • У тестах 8-10 \(N \leq 1000\).
  • У тестах 11-17 \(N \leq 10^5\).

Коментарі

Ще немає коментарів.