У Дмитра є 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
#include <iostream>
int main()
{
using namespace std;
int N;
cout << "Enter N: ";
cin >> N;
int num;
int max = 1;
int i;
for (i = 0; i < N; ++i)
{
cout << "Enter #" << i + 1 << " number: ";
cin >> num;
if ((num - 9) % 10 != 0 && num % 3 == 0)
{
max = num;
break;
}
}
for (int j = i + 1; j < N; ++j)
{
cout << "Enter #" << j + 1 << " number: ";
cin >> num;
if ((num - 9) % 10 != 0 && num % 3 == 0)
if (num > max)
max = num;
}
if (max != 1)
cout << "Max number div by 3 and don't end 9: " << max << endl;
else
cout << "No numbers div by 3 and don't end 9" << endl;
return 0;
}
begin
var s:=ReadLines('in.txt').ToArray;
var n:=StrToInt(s[0]);
var a:=s[1].ToWords.Select(e->StrToInt(e)).ToArray;
var f:=OpenWrite('out.txt');
Writeln(f,n,' - (кол-во чисел)');
foreach var e in a do Write(f,e,' '); Writeln(f);
Writeln(f,'Среднее значение четных ',
a.Where(x->x.IsEven).Average);
Writeln(f,'Среднее значение нечетных ',
a.Where(x->x.IsOdd).Average);
f.Close
end.
Файлы in.txt и out.txt находятся во вложении.
Содержимое файла out.txt:
15 - (кол-во чисел)
-22 49 33 47 -10 -1 20 -18 2 21 2 -25 21 -47 -36
Среднее значение четных -8.85714285714286
Среднее значение нечетных 12.25