Задача 6406. Источник: Поляков. Задание КИМ 26
На парковке есть L мест для легковых автомобилей и M мест для микроавтобусов. Приезжающий на парковку автомобиль занимает любое подходящее свободное место, при этом легковой автомобиль может встать на свободное место, предназначенное для микроавтобуса, но микроавтобус не может занять место, предназначенное для легкового автомобиля. Если подходящего свободного места нет, автомобиль уезжает. Гарантируется, что никакие два автомобиля не приезжают одновременно. Если время прибытия автомобиля совпадает со временем окончания стоянки другого автомобиля, вновь прибывший автомобиль может занять освободившееся место, если оно подходит ему по типу.
Определите количество микроавтобусов, которые смогут припарковаться, и общее количество автомобилей (как легковых, так и микроавтобусов), которые уедут из-за отсутствия мест.
Входные данные представлены в файле 26-119.txt следующим образом. Первая строка входного файла содержит три целых числа: N – общее количество автомобилей, приехавших на парковку в течение суток; L – количество мест для легковых автомобилей и M – количество мест для микроавтобусов. Каждая из следующих N строк описывает один автомобиль и содержит два целых числа и букву. Первое число означает время в минутах с начала суток, когда автомобиль прибыл на парковку, второе – необходимую длительность стоянки в минутах. Буква означает тип автомобиля: A – легковой, B – микроавтобус.
В ответе запишите два целых числа: сначала количество микроавтобусов, которые смогут припарковаться, затем – общее количество автомобилей (как легковых, так и микроавтобусов), которые уедут из-за отсутствия мест.
Пример входного файла:
5 2 1
5 22 A
8 30 B
14 15 A
25 12 A
20 40 B
При таких исходных сумеет припарковаться только один микроавтобус, приехавший на 8-й минуте. Два автомобиля – легковой на 25-й минуте и микроавтобус на 20-й – уедут, не найдя место для парковки. Ответ: 1 2.
Решение
Отсортируем исходные данные в двухмерном массиве a по времени прибытия на парковку (в программах на PascalABC и C++ использован алгоритм сортировки выбором). Последовательно обрабатывая информацию об автомобилях, будем выбирать подходящее парковочное место и помещать информацию о времени его освобождения в двухмерный массив b, где первым элементом является время освобождения, а вторым - тип места. Переменная nb хранит фактическое количество данных в массиве. Перед помещением каждого нового автомобиля в массив b, будем удалять из него все автомобили, которые должны были покинуть парковку к прибытию обрабатываемой машины. Объем данных в задаче небольшой, а потому нет фактической необходимости оптимизации работы с массивом b. Новые данные добавляются в конец массива, а при обработке нового автомобиля, в нем анализируется каждая строка. При значительно большем объеме данных целесообразно делать этот массив отсортированным. Вариант такого оптимизированного решения приведен в схожей Задаче 6413. Помимо указанных двух массивов, в программе используются следующие одномерные массивы:
total - общее количество мест по типам;
busy - количество занятых в данный момент мест для каждого типа.
Python
f = open('26-119.txt')
total = [0] * 2
n, total[0], total[1] = map(int, f.readline().split())
busy = [0] * 2
count = 0;
lost = 0;
a = []
for i in f:
x, y, z = i.split()
if z == 'A':
a.append([int(x), int(y), 0])
else:
a.append([int(x), int(y), 1])
a.sort()
b = []
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
if i[2] == 0:
if total[0] > busy[0]:
category = 0
elif total[1] > busy[1]:
category = 1
elif total[1] > busy[1]:
category = 1
if category != - 1:
b.append([i[0] + i[1], category])
busy[category] += 1
if i[2] == 1:
count += 1
else:
lost += 1
print(count, lost)
PascalABC
var
n, m, i, j, z, nb, t, count, lost, category, min: Integer;
a: array [1..900, 1..3] of Integer;
b: array [1..900, 1..2] of Integer;
total, busy: array [0..1] of Integer;
s: String;
f: TEXT;
begin
Assign(f, '26-119.txt');
Reset(f);
Readln(f, n, total[0], total[1]);
busy[0] := 0;
busy[1] := 0;
for i := 1 to n do
begin
Readln(f, a[i, 1], a[i, 2], s);
if s.Contains('A') then
a[i, 3] := 0
else
a[i, 3] := 1
end;
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;
count := 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;
if a[i, 3] = 0 then
begin
if total[0] > busy[0] then
category := 0
else if total[1] > busy[1] then
category := 1;
end
else if total[1] > busy[1] then
category := 1;
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;
if a[i, 3] = 1 then
count := count + 1;
end
else
lost := lost + 1;
end;
Writeln(count, ' ', lost);
end.
C++
#include
#include
using namespace std;
int main()
{
ifstream f;
f.open("26-119.txt");
int m, n;
int total[2], busy[2] = {0, 0};
int a[900][3], b[900][2];
f >> n >> total[0] >> total[1];
for (int i = 0; i < n; i++)
{
string s;
f >> a[i][0] >> a[i][1] >> s;
if (s == "A")
a[i][2] = 0;
else
a[i][2] = 1;
}
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, count = 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;
if (a[i][2] == 0)
{
if (total[0] > busy[0])
category = 0;
else if (total[1] > busy[1])
category = 1;
}
else if (total[1] > busy[1])
category = 1;
if (category != -1)
{
b[nb][0] = a[i][0] + a[i][1];
b[nb][1] = category;
nb++;
busy[category]++;
if (a[i][2] == 1)
count++;
}
else
lost++;
}
cout << count << " " << lost << endl;
}
Ответ
439 26