Задача 7013. Источник: Поляков. Задание КИМ 26
(Л. Шастин) В отеле есть K жилых номеров, предназначенных для размещения туристов. Все номера пронумерованы, начиная с единицы. Известно время, в которое каждая группа туристов заселяются в номера; время, в которое они планируют их освободить, а также количество номеров, которое потребуется для того, чтобы разместить всю группу туристов сразу. Каждая группа туристов заселяется в свободные номера с наименьшими номерами. Если несколько групп туристов пришли одновременно, то прежде всего обслуживаются группы, которые планируют уйти раньше и для размещения которых требуется меньшее количество номеров. На заселение и выселение туристов уходит одна минута. Со следующей минуты можно заселять в освободившийся номер других туристов. Если группа туристов пришла, но необходимого количества (которого достаточно для заселения их всех) свободных номеров нет – вся группа уходит, потому что заселиться не может.
Определите, сколько всего групп туристов смогут заселиться в номера отеля за 24 часа, а также суммарное время, в которое хотя бы один из номеров был свободен.
Входные данные представлены в файле 26-137.txt следующим образом. В первой строке входного файла находится число K – количество жилых номеров в отеле (натуральное число, не превышающее 1000). Во второй строке находится число N – количество групп туристов, которые собираются заселиться в номера. В каждой из следующих N строках находятся три значения:
– минута заселения группы туристов;
– минута, до которой группа туристов планирует проживать в номерах;
– количество номеров, которое потребуется для размещения всей группы.
Отсчёт ведётся от начала суток (все числа натуральные, не превышающие 1440), для каждой группы – в отдельной строке.
Запишите в ответе два целых числа: сначала количество групп туристов, которые смогут заселиться в номера отеля за 24 часа, затем суммарное время, в которое хотя бы один из номеров был свободен.
Пример входного файла:
10
5
30 60 5
40 1110 2
30 60 3
60 120 1
120 1440 2
При таких исходных данных первая, вторая, третья и пятая группа туристов смогут заселиться в номера. В первые 29 минут от начала дня все номера были свободны, далее до 40 минуты были свободны 2 номера. С 40-й и до 60-й минуты все номера были заняты на протяжении 21-й минуты, а затем до конца дня хотя бы один из номеров всегда был свободен. Значит, суммарное время, в которое хотя бы один из номеров был свободен, равно 1440 - (60 - 40 + 1) = 1440 - 21 = 1419. Ответ: 4 1419.
Решение
Данные сортируем в порядке возрастания по всем полям. В переменной count будем подсчитывать количество размещенных групп, alltime - общее время, когда все номера были заняты, free - текущее количество свободных номеров, allstart - начальное время, когда были заняты все номера (если все номера не были заняты, то значение -1). Так же в списке/массиве/векторе busy будем хранить информацию о занятых номерах. Каждый элемент будет содержать время освобождения и количество освобождаемых номеров.
Последовательно обрабатываем отсортированные данные. Из busy удаляем информацию о номерах, которые освободились к моменту заселения рассматриваемой группы. При удалении увеличиваем free на количество освобождаемых номеров, , а так же находим минимальное время, когда освободился какой-то номер mintime. Ели ранее у нас были заняты все номера (allstart имеет положительное значение) и какие-то номера освободились, то добавляем к alltime интервал от mintime до allstart включительно (в этом промежутке были заняты все номера). Если количество свободных номеров позволяет разместить рассматриваемую группу, то увеличиваем count, уменьшаем free на количество занятых номеров и добавляем информацию о занятых номерах в busy. Если с заселением данной группы были заняты все номера, обновляем значение allstart. После обработки всех групп выводим count и разницу между 1440 (количество минут в сутках) и alltime (в течение этого времени был свободен хотя бы один номер).
Python
f = open('26-137.txt')
k = int(f.readline())
n = int(f.readline())
a = [[int(y) for y in x.split()] for x in f]
a.sort()
count = 0
alltime = 0
allstart = -1
free = k
busy = []
for i in a:
mintime = 10000
j = 0
while j < len(busy):
if busy[j][0] < i[0]:
mintime = min(mintime, busy[j][0])
free += busy[j][1]
del busy[j]
else:
j += 1
if allstart != -1 and free != 0:
alltime += mintime - allstart + 1
allstart = -1
if free >= i[2]:
count += 1
free -= i[2]
busy.append(i[1:])
if free == 0:
allstart = i[0]
print(count, 1440 - alltime)
PascalABC
type
Rec = record
time: Integer;
count: Integer;
end;
var
n, k, count, alltime, mintime, allstart, free, min, i, j, t: Integer;
a: array [1..1000, 1..3] of Integer;
busy: array of Rec = new Rec[0];
tmp: Rec;
f: TEXT;
begin
Assign(f, '26-137.txt');
Reset(f);
Readln(f, k, 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])or
(a[j, 1] = a[min, 1]) and (a[j, 2] = a[min, 2]) and (a[j, 3] < a[min, 3]) 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;
count := 0;
alltime := 0;
allstart := -1;
free := k;
for i := 1 to n do
begin
mintime := 10000;
j := 0;
while j < busy.Length do
if busy[j].time < a[i, 1] then
begin
if busy[j].time < mintime then
mintime := busy[j].time;
free := free + busy[j].count;
if j < busy.Length - 1 then
busy := busy[:j] + busy[j + 1:]
else
busy := busy[:j];
end
else
j := j + 1;
if (allstart <> -1) and (free <> 0) then
begin
alltime := alltime + mintime - allstart + 1;
allstart := -1;
end;
if free >= a[i, 3] then
begin
count := count + 1;
free := free - a[i, 3];
tmp.time := a[i, 2];
tmp.count := a[i, 3];
busy := busy + Arr(tmp);
if free = 0 then
allstart := a[i][1];
end;
end;
Writeln(count, ' ', 1440 - alltime);
end.
C++
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
struct rec
{
int time;
int count;
};
int main()
{
ifstream f;
f.open("26-137.txt");
int n, k;
f >> k >> 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] ||
a[j][0] == a[min][0] && a[j][1] == a[min][1] && a[j][2] < a[min][2])
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 count = 0, alltime = 0, allstart = -1, free = k;
vector<rec> busy;
for (int i = 0; i < n; i++)
{
int mintime = 10000, j = 0;
while (j < busy.size())
if (busy[j].time < a[i][0])
{
if (busy[j].time < mintime)
mintime = busy[j].time;
free += busy[j].count;
busy.erase(busy.begin() + j);
}
else
j++;
if (allstart != -1 && free != 0)
{
alltime += mintime - allstart + 1;
allstart = -1;
}
if (free >= a[i][2])
{
count++;
free -= a[i][2];
rec tmp;
tmp.time = a[i][1];
tmp.count = a[i][2];
busy.push_back(tmp);
if (free == 0)
allstart = a[i][0];
}
}
cout << count << " " << 1440 - alltime << endl;
}
Ответ
291 1077