Задача 7356. Источник: Поляков. Задание КИМ 26
(Н. Кургуз) В поезде, состоящем из M вагонов (вагоны пронумерованы от 1 до M), размещаются N групп людей, в каждой из которых не более 4 человек, среди них могут быть дети. Каждый вагон содержит K четырёхместных купе, а также K двухместных боковых блоков. Каждая группа, в которой больше двух человек, размещается в отдельном купе, а каждая группа из 1 или 2 человек – в отдельном боковом блоке или купе. Разделять группы нельзя. В первую очередь размещаются группы с большей численностью, а при равной численности приоритет получают те, в которых больше детей. Группы размещаются на первом подходящем месте в вагоне с наименьшим номером. Определите наибольшее количество детей, которых удастся разместить в поезде, а также номер вагона, в котором останется наибольшее количество свободных мест. Если таких вагонов несколько, укажите наименьший номер подходящего вагона.
Входные данные представлены в файле 26-145.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 1000) – количество групп, желающих попасть на поезд. Во второй строке записаны два натуральных числа, не превышающих 10 000: M – количество вагонов, и K – количество купе и боковых блоков в одном вагоне. Каждая из следующих N строк описывает одну группу и содержит два целых количество людей в группе и количество детей среди них.
Запишите в ответе два числа: сначала наибольшее количество детей, которое поедут в поезде, затем номер вагона с наибольшим количеством свободных мест.
Пример входного файла:
12
2 2
3 1
3 0
1 0
2 0
4 2
3 2
2 0
4 1
3 1
2 1
3 2
1 0
При таких исходных данных смогут заселиться группы (4,2), (4,1), (3,2), (3,2), (2,1), (2,0), (2,0), (1,0), в 1 вагоне свободных мест – 0, во втором – 3. Ответ: 8 2.
Решение
Считываем исходные данные и сортируем их в порядке убывания по обоим полям. В переменной current будет содержаться номер вагона, где возможно разместить следующую группу. В переменной children будем подсчитывать число размещенных детей. Создадим двухмерный массив carriages, где для каждого вагона будет хранится число оставшихся купе, оставшихся блоков боковых мест и число свободных мест. Последовательно обрабатываем отсортированные данные и размещаем группу в текущем вагоне, если вагоны для размещения еще есть. Если после размещения группы число свободных купе или блоков стало равным нулю, переходим к следующему вагону. Когда встретим первую группу с численностью менее трех человек, current должна указывать на первый вагон. После обработки всех данных, находим номер вагона с наибольшим числом свободных мест и выводим результат.
Python
f = open('26-145.txt')
n = int(f.readline())
m, k = map(int, f.readline().split())
a = [[int(y) for y in x.split()] for x in f]
a.sort(reverse=True)
carriages = [[k, k, k * 6] for i in range(m)]
current = 0
children = 0
for i in range(n):
if a[i][0] < 3 and a[i - 1][0] > 2:
current = 0
if current < m:
carriages[current][2] -= a[i][0]
children += a[i][1]
if a[i][0] > 2:
carriages[current][0] -= 1
if carriages[current][0] == 0:
current += 1
else:
carriages[current][1] -= 1
if carriages[current][1] == 0:
current += 1
mxi = 0
for i in range(1, m):
if carriages[i][2] > carriages[mxi][2]:
mxi = i
print(children, mxi + 1)
PascalABC
type
qarray = array of Integer;
var
n, m, k, children, current, max, i, j, t: Integer;
a: array [1..500, 1..2] of Integer;
carriages: array[1..24, 1..3] of Integer;
f: TEXT;
begin
Assign(f, '26-145.txt');
Reset(f);
Readln(f, n, m, k);
for i := 1 to n do
Readln(f, a[i, 1], a[i, 2]);
for i := 1 to n - 1 do
begin
max := i;
for j := i + 1 to n do
if (a[j, 1] > a[max, 1]) or (a[j, 1] = a[max, 1]) and (a[j, 2] > a[max, 2]) then
max := j;
if max <> i then
begin
t := a[i, 1];
a[i, 1] := a[max, 1];
a[max, 1] := t;
t := a[i, 2];
a[i, 2] := a[max, 2];
a[max, 2] := t;
end;
end;
for i := 1 to m do
begin
carriages[i, 1] := k;
carriages[i, 2] := k;
carriages[i, 3] := k * 6;
end;
children := 0;
current := 1;
for i := 1 to n do
begin
if (a[i, 1] < 3) and (a[i - 1, 1] > 2) then
current := 1;
if current <= m then
begin
carriages[current, 3] := carriages[current, 3] - a[i, 1];
children := children + a[i, 2];
if a[i, 1] > 2 then
begin
carriages[current, 1] := carriages[current, 1] - 1;
if carriages[current, 1] = 0 then
current := current + 1;
end
else
begin
carriages[current, 2] := carriages[current, 2] - 1;
if carriages[current, 2] = 0 then
current := current + 1;
end
end;
end;
max := 1;
for i := 2 to m do
if carriages[i, 3] > carriages[max, 3] then
max := i;
Writeln(children, ' ', max);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-145.txt");
int n, m, k;
f >> n >> m >> k;
int a[500][2];
for (int i = 0; i < n; i++)
f >> a[i][0] >> a[i][1];
for (int i = 0; i < n - 1; i++)
{
int max = i;
for (int j = i + 1; j < n; j++)
if (a[j][0] > a[max][0] || a[j][0] == a[max][0] && a[j][1] > a[max][1])
max = j;
if (max != i)
{
int t = a[i][0];
a[i][0] = a[max][0];
a[max][0] = t;
t = a[i][1];
a[i][1] = a[max][1];
a[max][1] = t;
}
}
int carriages[24][3];
for (int i = 0; i < m; i++)
{
carriages[i][0] = k;
carriages[i][1] = k;
carriages[i][2] = k * 6;
}
int current = 0, children = 0;
for (int i = 0; i < n; i++)
{
if (a[i][0] < 3 && a[i - 1][0] > 2)
current = 0;
if (current < m)
{
carriages[current][2] -= a[i][0];
children += a[i][1];
if (a[i][0] > 2)
{
carriages[current][0]--;
if (carriages[current][0] == 0)
current++;
}
else
{
carriages[current][1]--;
if (carriages[current][1] == 0)
current++;
}
}
}
int max = 0;
for (int i = 1; i < m; i++)
if (carriages[i][2] > carriages[max][2])
max = i;
cout << children << " " << max + 1 << endl;
}
Ответ
308 18