Задача 7014. Источник: Поляков. Задание КИМ 26
(Л. Шастин) На склад магазина привезли N упаковок свежей продукции. Вновь привезенную продукцию сортируют по K холодильным камерам, вместимость каждой из которых равна M кг. Холодильные камеры, в свою очередь, пронумерованы от 1 до K. Фасовщики заполняют холодильные камеры последовательно, начиная с 1-й. Сначала погружают товары наибольшего объема (до тех пор, пока самый большой из оставшихся товаров влезает в холодильную камеру), стремясь заполнить текущую холодильную камеру до предела, а оставшееся свободное место начиняют товарами наименьшего объема. Гарантируется, что K камер хранения достаточно для сортировки всей продукции по описанной выше стратегии.
Определите номер холодильной камеры, в которую погрузили последний товар, а также остаток свободного в ней места.
Входные данные представлены в файле 26-138.txt следующим образом. В первой строке входного файла находится число N – количество упаковок привезенной продукции (натуральное число, не превышающее 5000). Во второй строке находится число K – количество холодильных камер. А в третьей строке находится число M – вместимость каждой из холодильных камер в кг. В следующих N строках находятся натуральные числа – веса упаковок в кг.
Запишите в ответе два целых числа: сначала номер холодильной камеры, в которую погрузили последний товар, а затем количество оставшегося в ней свободного места (в кг).
Пример входного файла:
5
5
10
9
7
6
4
1
При таких исходных данных первая холодильная камера будет заполнена до отвала, во второй останется 3 кг свободного места, а в третьей - 0 кг. В третью же камеру и погрузят последний товар. Ответ: 3 0.
Решение
Сортируем исходные данные по убыванию. В переменной hi будем хранить индекс незагруженного продукта максимальной массы, в переменной low - индекс незагруженного продукта минимальной массы, в переменной fridge - номер текущего холодильника. В цикле загружаем очередной холодильник сначала продуктами наибольшей массы, а потом наименьшей, пока незагруженных продуктов не останется. Свободное место в холодильнике будет храниться в m1.
Python
f = open('26-138.txt')
n = int(f.readline())
k = int(f.readline())
m = int(f.readline())
a = [int(x) for x in f]
a.sort(reverse=True)
fridge = 0
hi = 0
low = n - 1
while hi <= low:
fridge += 1
m1 = m
while hi <= low and a[hi] <= m1:
m1 -= a[hi]
hi += 1
while hi <= low and a[low] <= m1:
m1 -= a[low]
low -= 1
print(fridge, m1)
PascalABC
var
n, k, m, m1, fridge, hi, low, max, i, j, t: Integer;
a: array [1..5000] of Integer;
f: TEXT;
begin
Assign(f, '26-138.txt');
Reset(f);
Readln(f, n, k, m);
for i := 1 to n do
Readln(f, a[i]);
for i := 1 to n - 1 do
begin
max := i;
for j := i + 1 to n do
if a[j] > a[max] then
max := j;
if max <> i then
begin
t := a[i];
a[i] := a[max];
a[max] := t;
end;
end;
fridge := 0;
hi := 1;
low := n;
while hi <= low do
begin
fridge := fridge + 1;
m1 := m;
while (hi <= low) and (a[hi] <= m1) do
begin
m1 := m1 - a[hi];
hi := hi + 1;
end;
while (hi <= low) and (a[low] <= m1) do
begin
m1 := m1 - a[low];
low := low - 1;
end;
end;
Writeln(fridge, ' ', m1);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-138.txt");
int n, k, m;
f >> n >> k >> m;
int a[5000];
for (int i = 0; i < n; i++)
f >> a[i];
for (int i = 0; i < n - 1; i++)
{
int max = i;
for (int j = i + 1; j < n; j++)
if (a[j] > a[max])
max = j;
if (max != i)
{
int t = a[i];
a[i] = a[max];
a[max] = t;
}
}
int fridge = 0, hi = 0, low = n - 1, m1;
while (hi <= low)
{
fridge++;
m1 = m;
while (hi <= low && a[hi] <= m1)
m1 -= a[hi++];
while (hi <= low && a[low] <= m1)
m1 -= a[low--];
}
cout << fridge << " " << m1 << endl;
}
Ответ
426 5783