Задача 7186. Источник: Поляков. Задание КИМ 26
На автозаправке работают две заправочные колонки. Заправиться дизельным топливом можно только в колонке 1, бензином А-76 – только в колонке 2. Клиент заезжает на заправку и встаёт в очередь к той колонке, в которой есть необходимое ему топливо. Если нужное топливо есть в обеих колонках, клиент выбирает ту, очередь к которой в данный момент меньше. Если обе очереди одинаковые, клиент выбирает колонку с меньшим номером. Если при этом в очереди к выбранной колонке уже стоит 5 или более машин (считая ту машину, которая сейчас заправляется), клиент сразу уезжает.
Входные данные представлены в файле 26-143.txt следующим образом. В первой строке входного файла содержит натуральное число N (1 ≤ N ≤ 1000) – количество клиентов, которые заезжали на заправку в течение дня. Каждая из следующих N строк описывает одного клиента и содержит 3 целых числа: время приезда клиента на заправку (количество минут с начала рабочего дня); время, необходимое для заправки, и номер колонки, в которой ему необходимо заправляться (0 означает, что клиент может заправляться на любой колонке). Гарантируется, что никакие два клиента не приезжают одновременно.
Запишите в ответе два числа: количество машин, которые будут заправлены в течение дня на колонке 1, и количество клиентов, которые уехали с заправки из-за очередей.
Пример входного файла:
5
10 5 0
11 3 1
12 4 0
13 4 1
15 5 0
Предположим, что клиент уезжает, если очередь к нужной ему колонке включает более одной машины. При таких исходных данных на первой колонке заправятся первая и вторая машины, а четвёртый клиент уедет, поскольку ему нужна первая колонка, где в очереди в момент 13 находятся две машины. Ответ: 2 1.
Решение
Не смотря на то, что в условии задачи гарантируется, что две машины не приезжают в одно время, в файле данных присутствуют такие машины. Поэтому результат зависит от сортировки. Ответ, указанный для задачи получается при сортировке в порядке возрастания по первым двум полям. Иной способ сортировки, в т.ч. сортировка только по времени прибытия может дать другой ответ.
Считываем данные и сортируем их. В переменной k будем подсчитывать количество автомобилей, заправившихся на первой колонке, а в k1 - количество машин, уехавших из-за очередей. Помимо этого для каждой колонки создадим список/массив/вектор с временем завершения заправки автомобилей в очереди. Наиболее удобно это сделать в виде списка/массива из двух элементов queues. Последовательно обрабатываем информацию о каждой машине. Из очередей удаляем данные о машинах, которые покинули их на момент приезда обрабатываемой машины. Если машина может быть обслужена в любой колонке, выбираем колонку с наименьшим размером очереди. Если размер очереди меньше пяти, добавляем машину в очередь. Если она обслуживается в первой колонке, увеличиваем значение k. Если в очереди много машин, увеличиваем k1. После обработки всех машин выводим результат.
Python
f = open('26-143.txt')
n = int(f.readline())
a = [[int(y) for y in x.split()] for x in f]
a.sort()
queues = [[], []]
k = 0
k1 = 0
for i in a:
for j in range(2):
z = 0
while z < len(queues[j]):
if queues[j][z] <= i[0]:
del queues[j][z]
else:
z += 1
if i[2] == 0:
if len(queues[0]) <= len(queues[1]):
i[2] = 1
else:
i[2] = 2
if len(queues[i[2] - 1]) < 5:
if i[2] == 1:
k += 1
if len(queues[i[2] - 1]) == 0:
queues[i[2] - 1].append(i[0] + i[1])
else:
queues[i[2] - 1].append(queues[i[2] - 1][-1] + i[1])
else:
k1 += 1
print(k, k1)
PascalABC
type
qarray = array of Integer;
var
n, k, k1, min, z, i, j, t: Integer;
a: array [1..1000, 1..3] of Integer;
queues: array [1..2] of qarray = (new Integer[0], new Integer[0]);
f: TEXT;
begin
Assign(f, '26-143.txt');
Reset(f);
Readln(f, n);
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]) or (a[j, 1] = a[min, 1]) and (a[j, 2] < a[min, 2]) 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;
k := 0;
k1 := 0;
for i := 1 to n do
begin
for j := 1 to 2 do
begin
z := 0;
while z < queues[j].Length do
if queues[j][z] <= a[i][1] then
if z < queues[j].Length - 1 then
queues[j] := queues[j][:z] + queues[j][z + 1:]
else
queues[j] := queues[j][:z]
else
z := z + 1;
end;
if a[i][3] = 0 then
if queues[1].Length <= queues[2].Length then
a[i][3] := 1
else
a[i][3] := 2;
if queues[a[i][3]].Length < 5 then
begin
if a[i][3] = 1 then
k := k + 1;
if queues[a[i][3]].Length = 0 then
queues[a[i][3]] := Arr(a[i][1] + a[i][2])
else
queues[a[i][3]] := queues[a[i][3]] +
Arr(queues[a[i][3]][queues[a[i][3]].Length - 1] + a[i][2]);
end
else
k1 := k1 + 1;
end;
Writeln(k, ' ', k1);
end.
C++
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main()
{
ifstream f;
f.open("26-143.txt");
int n;
f >> n;
int a[1000][3];
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] || a[j][0] == a[min][0] && a[j][1] < a[min][1])
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 k = 0, k1 = 0;
vector<int> queues[2];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < 2; j++)
{
int z = 0;
while (z < queues[j].size())
if (queues[j][z] <= a[i][0])
queues[j].erase(queues[j].begin() + z);
else
z++;
}
if (a[i][2] == 0)
if (queues[0].size() <= queues[1].size())
a[i][2] = 1;
else
a[i][2] = 2;
if (queues[a[i][2] - 1].size() < 5)
{
if (a[i][2] == 1)
k++;
if (queues[a[i][2] - 1].size() == 0)
queues[a[i][2] - 1].push_back(a[i][0] + a[i][1]);
else
queues[a[i][2] - 1].push_back(*(queues[a[i][2] - 1].end() - 1) + a[i][1]);
}
else
k1++;
}
cout << k << " " << k1 << endl;
}
Ответ
257 480