Задача 6608. Источник: Поляков. Задание КИМ 26
(Е. Джобс) На стадионе есть система предварительных заявок на покупку билетов на футбольный матч. Каждая заявка содержит одно число – количество билетов, которые желает выкупить клиент. Утром перед матчем оператор распределяет заявки по следующему алгоритму:
- все билеты в одной заявке должны быть в одном ряду;
- в первую очередь подтверждаются заявки с наибольшим количеством забронированных мест;
- места проверяются в порядке следования рядов, то есть оператор старается разместить все места из заявки в ряд с наименьшим номером, и при этом максимально близко к началу ряда.
Определите, сколько заявок подтвердит оператор и сколько свободных мест останется на стадионе после распределения всех заявок по описанному алгоритму.
Входные данные представлены в файле 26-124.txt следующим образом. Первая строка входного файла содержит три натуральных числа: количество рядов на стадионе K (1 ≤ K ≤ 1000), количество мест в одном ряду M (1 ≤ M ≤ 1000) и количество заявок N (1 ≤ K ≤ 20000). В каждой из N следующих строк записано одно натуральное число – количество билетов в заявке.
В ответе запишите два числа: сначала количество подтвержденных заявок, затем количество оставшихся свободных мест на стадионе.
Пример входного файла:
3 20 7
8
15
10
17
13
6
4
При таких исходных данных оператор удовлетворит 5 заявок – 15, 17, 13, 6 и 4 (всего 55 мест). На стадионе останется 5 свободных мест. Ответ: 5 5.
Решение
Считываем данные в массив/список и сортируем в порядке убывания. Создаем массив rows с информацией о количестве оставшихся мест в ряду, а так же переменные free для количества оставшихся свободных мест и count для количества обработанных заявок. Последовательно обрабатываем заявки и ищем ряд с минимальным номером, где заявка может быть удовлетворена. Если такой ряд нашелся, меняем значения переменных.
Python
f = open('26-124.txt')
k, m, n = map(int, f.readline().split())
a = [int(x) for x in f]
a.sort(reverse=True)
rows = [m] * k
free = k * m
count = 0;
for i in a:
for j in range(k):
if rows[j] >= i:
rows[j] -= i
free -= i
count += 1
break
print(count, free)
PascalABC
var
k, m, n, free, count, i, j, max, t: Integer;
a: array [1..2000] of Integer;
rows: array [1..100] of Integer;
f: TEXT;
begin
Assign(f, '26-124.txt');
Reset(f);
Readln(f, k, m, n);
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;
for i := 1 to k do
rows[i] := m;
free := k * m;
count := 0;
for i := 1 to n do
for j := 1 to k do
if rows[j] >= a[i] then
begin
rows[j] := rows[j] - a[i];
free := free - a[i];
count := count + 1;
break;
end;
Writeln(count, ' ', free);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-124.txt");
int k, m, n;
f >> k >> m >> n;
int a[2000];
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 rows[100];
for (int i = 0; i < k; i++)
rows[i] = m;
int free = k * m, count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < k; j++)
if (rows[j] >= a[i])
{
rows[j] -= a[i];
free -= a[i];
count++;
break;
}
cout << count << " " << free << endl;
}
Ответ
196 335