Задача 6320. Источник: Поляков. Задание КИМ 26
(Л. Евич) В тренажёрном зале N тренажёров, работающих c 10:00 до 22:00. Все тренажёры пронумерованы от 1 до N. Каждый из M посетителей зала может воспользоваться любым тренажёром. Посетитель всегда выбирает свободный тренажёр с наименьшим номером; если свободных тренажёров нет, он уходит. Если в одно и то же время пришли несколько посетителей, то они занимают тренажёры в том порядке, в котором расположены данные в файле. Для каждого посетителя известно время начала и время окончания его тренировки. Время тренировки на тренажёре другого посетителя может начаться со следующей минуты после окончания времени тренировки предыдущего посетителя.
Определите количество посетителей тренажерного зала, которые могли воспользоваться тренажёрами за время работы зала и номер тренажёра, на котором начал свою тренировку последний посетитель.
Входные данные представлены в файле 26-115.txt следующим образом. В первой строке входных данных задается два числа: N - количество тренажёров и M – количество посетителей зала. В каждой из последующих M строк содержится информация по каждому посетителю: время начала и время окончания тренировки на тренажёре (в минутах от начала суток).
Запишите в ответе два числа: количество посетителей тренажерного зала, которые могли воспользоваться тренажёрами за время работы зала и номер тренажёра, на котором проводил свою тренировку последний посетитель.
Пример входного файла:
2 5
601 690
620 642
640 645
650 670
680 700
При этих исходных данных 1-й тренажёр с самого начала занимает первый посетитель. Посетители со временем прихода 620, 650 и 680 работают один за другим на 2-м тренажёре. Посетитель со временем прихода 640 уходит, потому что в этот момент свободных тренажёров нет. Всего обслужено 4 посетителя, последний начал работу на тренажёре 2. Ответ: 4 2.
Решение
Считываем исходные данные в список/массив a и сортируем данные только по времени визита. Следует использовать только алгоритмы стабильной сортировки, чтобы сохранить порядок посетителей с одинаковым временем визита. К таким алгоритмам относятся пузырьковая сортировка и сортировка вставкой. Создадим список/массив train, где будем сохранять время освобождения каждого тренажера. В переменной k будем подсчитывать количество обслуженных посетителей, а в переменной last - номер тренажера последнего обслуженного посетителя. Для каждого посетителя ищем свободный тренажер с минимальным номером. Если свободный тренажер нашелся, обновляем значения переменных. После обработки всех посетителей, выводим результат.
Python
f = open('26-115.txt')
n, m = map(int, f.readline().split())
a = [[int(y) for y in x.split()] for x in f]
a.sort(key=lambda x: x[0])
train = [0] * n
k = 0
last = 0
for i in a:
t = -1
for j in range(0, n):
if train[j] < i[0]:
t = j
break
if t != -1:
last = t + 1
k += 1
train[t] = i[1]
print(k, last)
PascalABC
var
n, m, k, last, i, j, t: Integer;
a: array [1..3500, 1..2] of Integer;
train: array [1..50] of Integer;
f: TEXT;
begin
Assign(f, '26-115.txt');
Reset(f);
Readln(f, n, m);
for i := 1 to m do
Readln(f, a[i, 1], a[i, 2]);
for i := 1 to m - 1 do
for j := m downto i + 1 do
if a[j, 1] < a[j - 1, 1] then
begin
t := a[j, 1];
a[j, 1] := a[j - 1, 1];
a[j - 1, 1] := t;
t := a[j, 2];
a[j, 2] := a[j - 1, 2];
a[j - 1, 2] := t;
end;
for i := 1 to n do
train[i] := 0;
k := 0;
last := 0;
for i := 1 to m do
begin
t := 0;
for j := 1 to n do
if train[j] < a[i, 1] then
begin
t := j;
break;
end;
if t <> 0 then
begin
last := t;
k := k + 1;
train[t] := a[i][2]
end;
end;
Writeln(k, ' ', last);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-115.txt");
int n, m;
f >> n >> m;
int a[3500][2];
for (int i = 0; i < m; i++)
f >> a[i][0] >> a[i][1];
for (int i = 0; i < m - 1; i++)
for (int j = m - 1; j > i; j--)
if (a[j][0] < a[j - 1][0])
{
int t = a[j][0];
a[j][0] = a[j - 1][0];
a[j - 1][0] = t;
t = a[j][1];
a[j][1] = a[j - 1][1];
a[j - 1][1] = t;
}
int train[50];
for (int i = 0; i < n; i++)
train[i] = 0;
int k = 0, last = 0;
for (int i = 0; i < m; i++)
{
int t = -1;
for (int j = 0; j < n; j++)
if (train[j] < a[i][0])
{
t = j;
break;
}
if (t != -1)
{
last = t + 1;
k++;
train[t] = a[i][1];
}
}
cout << k << " " << last << endl;
}
Ответ
1269 41