Задача 6412. Источник: Поляков. Задание КИМ 26
(Д. Муфаззалов) На парковке расположены парковочные места для M категорий автомобилей. Номер категории – целое неотрицательное число, меньшее, чем M. Для каждой категории автомобилей выделено некоторое количество парковочных мест. Приезжающий на парковку автомобиль занимает любое свободное место среди мест, предназначенных для автомобилей его категории, а также среди мест, предназначенных для автомобилей c бóльшим номером категории. Автомобиль всегда паркуется на подходящем свободном месте для автомобилей с наименьшей категорией. Если подходящего свободного места нет, автомобиль уезжает. Гарантируется, что никакие два автомобиля не приезжают одновременно. Если время прибытия автомобиля совпадает со временем окончания стоянки другого автомобиля, вновь прибывший автомобиль может занять освободившееся место, если оно подходит ему.
Пусть K – максимальный номер категории автомобилей, в которой за всё время припарковалось наибольшее количество автомобилей. Определите время, через которое освободятся (и больше не будут заняты) все парковочные места, предназначенные для категории автомобилей с номером K, и общее количество автомобилей всех категорий, которые уедут из-за отсутствия мест.
Входные данные представлены в файле 26-120.txt следующим образом. Первая строка входного файла содержит два натуральных числа, записанных через пробел: M – количество категорий автомобилей, 1 ≤ M < 525 600, и N – общее количество автомобилей, приехавших на парковку в течение одного года, 0 ≤ N ≤ 106. Вторая строка содержит M чисел – количество парковочных мест на стоянке для автомобилей каждой категории, начиная с категории под номером 0, в порядке возрастания номеров категорий. Каждое из этих чисел не превышает 1000. Каждая из N последующих строк описывает один автомобиль и содержит три целых числа: время в минутах с начала года, когда автомобиль прибыл на парковку; необходимую длительность стоянки в минутах и номер категории автомобиля.
В ответе запишите два целых числа: время освобождения парковочных мест для автомобилей категории K, затем – общее количество автомобилей всех категорий, которые уедут из-за отсутствия мест.
Пример входного файла:
2 5
2 1
5 22 0
8 30 1
14 15 0
25 12 0
20 40 1
При таких исходных данных: 1-й автомобиль (категории 0) припаркуется на месте категории 0 с 5 по 27 минуты, 2-й автомобиль (категории 1) припаркуется на месте категории 1 с 8 по 38 минуты, 3-й автомобиль (категории 0) припаркуется на месте категории 0 с 14 по 29 минуты, 4-й автомобиль (категории 0) не найдет место, 5-й автомобиль (категории 1) не найдет место. В максимальное количество припаркованных автомобилей (2) имели категорию 0, все парковочные места для автомобилей категории 0 (т. е. места категорий 0 и 1) освободились на 38-й минуте. Ответ: 38 2.
Решение
Отсортируем исходные данные в двухмерном массиве a по времени прибытия на парковку (в программах на PascalABC и C++ использован алгоритм сортировки выбором). Последовательно обрабатывая информацию об автомобилях, будем выбирать наименьшую подходящую категорию и помещать информацию о времени освобождения парковочного места в двухмерный массив b, где первым элементом является время освобождения, а вторым - категория места. Переменная nb хранит фактическое количество данных в массиве. Перед помещением каждого нового автомобиля в массив b, будем удалять из него все автомобили, которые должны были покинуть парковку к прибытию очередного автомобиля. Объем данных в задаче небольшой, а потому нет фактической необходимости оптимизации работы с массивом b. Новые данные добавляются в конец массива, а при обработке нового автомобиля, в нем анализируется каждая строка. При значительно большем объеме данных целесообразно делать этот массив отсортированным. Вариант такого оптимизированного решения приведен в Задаче 6413. Помимо указанных двух массивов, в программе используются следующие одномерные массивы:
total - общее количество мест по категориям;
busy - количество занятых в данный момент мест в категориях;
count - общее количество машин, припарковавшихся в каждой категории;
time - время освобождения всех парковочных мест для каждой категории.
Python
f = open('26-120.txt')
m, n = map(int, f.readline().split())
total = [int(x) for x in f.readline().split()]
busy = [0] * m
count = [0] * m
time = [0] * m
a = [[int(y) for y in x.split()] for x in f]
a.sort()
b = []
lost = 0;
for i in a:
j = 0
while j < len(b):
if b[j][0] <= i[0]:
busy[b[j][1]] -= 1
del b[j]
else:
j += 1
category = -1
for j in range(i[2], m):
if total[j] > busy[j]:
category = j
break
if category != - 1:
b.append([i[0] + i[1], category])
busy[category] += 1
count[category] += 1
time[category] = max(time[category], i[0] + i[1])
else:
lost += 1
mx = 0
for i in range(1, m):
if count[i] >= count[mx]:
mx = i
print(time[mx], lost)
PascalABC
var
n, m, i, j, z, nb, t, lost, category, min, max: Integer;
a: array [1..900, 1..3] of Integer;
b: array [1..900, 1..2] of Integer;
total, busy, count, time: array [0..5] of Integer;
f: TEXT;
begin
Assign(f, '26-120.txt');
Reset(f);
Readln(f, m, n);
for i := 0 to m - 1 do
begin
Read(f, total[i]);
busy[i] := 0;
count[i] := 0;
time[i] := 0;
end;
for i := 1 to n do
Readln(f, a[i, 1], a[i, 2], a[i, 3]);
for i := 1 to n - 1 do
begin
min := i;
for j := i + 1 to n do
if a[j, 1] < a[min, 1] then
min := j;
if min <> i then
begin
t := a[i, 1];
a[i, 1] := a[min, 1];
a[min, 1] := t;
t := a[i, 2];
a[i, 2] := a[min, 2];
a[min, 2] := t;
t := a[i, 3];
a[i, 3] := a[min, 3];
a[min, 3] := t;
end;
end;
nb := 0;
lost := 0;
for i := 1 to n do
begin
j := 1;
while j <= nb do
if b[j, 1] <= a[i, 1] then
begin
busy[b[j, 2]] := busy[b[j, 2]] - 1;
for z := j + 1 to nb do
begin
b[z - 1, 1] := b[z, 1];
b[z - 1, 2] := b[z, 2];
end;
nb := nb - 1
end
else
j := j + 1;
category := -1;
for j := a[i, 3] to m - 1 do
if total[j] > busy[j] then
begin
category := j;
break;
end;
if category <> -1 then
begin
nb := nb + 1;
b[nb, 1] := a[i, 1] + a[i, 2];
b[nb, 2] := category;
busy[category] := busy[category] + 1;
count[category] := count[category] + 1;
if a[i, 1] + a[i, 2] > time[category] then
time[category] := a[i, 1] + a[i, 2];
end
else
lost := lost + 1;
end;
max := 0;
for i := 0 to m - 1 do
if count[i] >= count[max] then
max := i;
Writeln(time[max], ' ', lost);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-120.txt");
int m, n;
f >> m >> n;
int total[6], busy[6], count[6], time[6];
int a[900][3], b[900][2];
for (int i = 0; i < m; i++)
{
f >> total[i];
busy[i] = 0;
count[i] = 0;
time[i] = 0;
}
for (int i = 0; i < n; i++)
f >> a[i][0] >> a[i][1] >> a[i][2];
for (int i = 0; i < n - 1; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
if (a[j][0] < a[min][0])
min = j;
if (min != i)
{
int t = a[i][0];
a[i][0] = a[min][0];
a[min][0] = t;
t = a[i][1];
a[i][1] = a[min][1];
a[min][1] = t;
t = a[i][2];
a[i][2] = a[min][2];
a[min][2] = t;
}
}
int nb = 0, lost = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < nb; j++)
if (b[j][0] <= a[i][0])
{
busy[b[j][1]]--;
for (int z = j + 1; z < nb; z++)
{
b[z - 1][0] = b[z][0];
b[z - 1][1] = b[z][1];
}
nb--;
j--;
}
int category = -1;
for (int j = a[i][2]; j < m; j++)
if (total[j] > busy[j])
{
category = j;
break;
}
if (category != -1)
{
b[nb][0] = a[i][0] + a[i][1];
b[nb][1] = category;
nb++;
busy[category]++;
count[category]++;
if (a[i][0] + a[i][1] > time[category])
time[category] = a[i][0] + a[i][1];
}
else
lost++;
}
int max = 0;
for (int i = 1; i < m; i++)
if (count[i] > count[max])
max = i;
cout << time[max] << " " << lost << endl;
}
Ответ
194534 642