dja4enkodanil16

24.07.2021 04:21

Информатика

Есть ответ 👍

У Дмитра є n пластикових пляшок, кожна з яких вміщує рівно k літрів води. i-та пляшка заповнена водою на a i
​
літрів.
Нещодавно Дмитро дізнався про шкоду пластика довкіллю, тому він хоче здати як можна більше пляшок на переробку. Для цього йому потрібно всю воду з цих пляшок перелити в інші, так, щоб жодна пляшка не була переповнена (у i-ій пляшці після переливань має міститись не більше, ніж k літрів). При цьому хлопець лінивий, тому він хоче перелити як можна менше води.
До ть Дмитру знайти мінімальну кількість пляшок, яких вистачить для того, щоб перелити всю воду в них, а також мінімальну кількість літрів води, яку для цього потрібно перелити.
Зверніть увагу, що рідину з однієї пляшки можна розподіляти між декількома іншими. Тобто, необов'язково переливати всю воду з однієї пляшки в якусь одну.
Входные данные

Перший рядок містить два цілі числа n та k (1≤n≤10
5
, 1≤k≤10
4
) — загальна кількість пляшок та максимальний об'єм кожної з них.
Другий рядок містить n цілих чисел a
1
​
,a
2
​
,…,a
n
​
(0≤a
i
​
≤k) — кількість літрів води у пляшках.
Выходные данные

В єдиному рядку виведіть два цілі числа — кількість пляшок, яких вистачить для того, щоб перелити всю воду в них, а також мінімальну кількість літрів, які для цього потрібно перелити.
Примечание

У першому прикладі можна перелити всю воду з 5-ї пляшки у 3-ю, а з 1-ї — у 6-у.
У другому прикладі знадобляться всі 5 пляшок, тому переливати нічого не потрібно.
У третьому прикладі можна вибрати будь-яку пляшку й попереливати з неї по 1 літру в усі інші.
timer
Лимит на использование времени: 1000 ms
storage
Лимит на использование памяти: 256 MB
arrow_circle_up
У вас есть еще 49 попыток отправить эту задачу
Примеры

Ниже вы найдете примеры входных данных и ответы которые должна вывести ваша программа.

Пример ввода #1

6 5
1 5 3 0 2 4
Пример ответа #1

3 3
Пример ввода #2

5 8
6 8 7 5 8
Пример ответа #2

5 0
Пример ввода #3

6 6
5 5 5 5 5 5
Пример ответа #3

5 5