Задача 6793. Источник: Поляков. Задание КИМ 26
(Е. Джобс) На въезде в город оборудована сельскохозяйственная ярмарка. Лотки для продажи стоят с двух сторон дороги с двусторонним движением. С каждой стороны расположено по К мест для торговли. Место бронируется на определенное количество минут, при этом управляющим ярмарки закладывается 15 минут на освобождение места после окончания его аренды. Места, которые расположены вдоль полосы по направлению в город, считаются наиболее прибыльными, поэтому при возможности занимаются в первую очередь. Если свободных мест нет, но новый продавец видит, что на одном из мест предыдущий продавец собирает вещи, то он встает в очередь за ним. При этом он не отличает сколько времени осталось на сбор, если несколько продавцов освобождают свое место. Поэтому встает в очередь за первым по номеру лотка. В случае, когда по направлению в город нет свободных мест, но есть места по направлению из города, продавец выбирает подождать собирающегося продавца с «прибыльной» стороны, если таковые имеются. Если на желаемое время мест нет и ни один из продавцов не собирается, то новый продавец уезжает с ярмарки.
В случае, когда на одно и тоже время претендует несколько продавцов, управляющий делает выбор в пользу продавца, который собирается арендовать место на большее время.
Определите, сколько продавцов смогут занять места, и сколько минут за обозначенный период будут заняты все места по направлению в город (с учетом времени на сборы).
Входные данные представлены в файле 26-131.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 10000) – количество потенциальных продавцов и натуральное число K (1 ≤ K ≤ 500) – количество мест на каждой стороне дороги. В каждой из N следующих строк содержится два числа: Т (1 ≤ Т ≤ 4200) – время от начала ярмарки в минутах, когда продавец планирует начать торговлю, и Р (1 ≤ Р ≤ 300) – желаемое время аренды лотка.
Запишите в ответе два числа: количество продавцов, которые смогут арендовать место, и суммарную длительность аренды всех лотков вдоль стороны дороги по направлению в город.
Пример входного файла:
26
1 10
11 25
16 15
21 25
26 20
31 10
Обозначим лотки, как 1В и 2В (выгодный) со стороны в город, и 1Н, 2Н (невыгодный) – из города. Тогда
1-й продавец: 1В – 1-10 минут + 15 минут на сборы (лоток занят с 1 по 25 минуты)
2-й продавец: 2В – 11-35 минут + 15 минут на сборы (лоток занят с 11 по 50 минуты)
3-й продавец: 1В – дождаться, пока соберется предыдущий, 26-40 + 15 минут на сборы (лоток занят с 26 по 55 минуты)
4-й продавец: 1Н – 21-45 + 15 минут на сборы (лоток занят с 21 по 60 минуты)
5-й продавец: 2Н – 26-45 + 15 минут на сборы (лоток занят с 26 по 60 минуты)
6-й продавец уезжает с ярмарки.
При этом все места с выгодной стороны будут заняты 40 минут (с 11 до 50). Ответ: 5 40.
Решение
Наиболее простой способ получить второе значение (количество минут, когда будут заняты все прибыльные места) - организовать цикл по минутам. В качестве конечного значения цикла берем сумму данных для самого последнего продавца и увеличиваем на 30 (15 минут потенциального ожидания освобождения места и 15 своих минут сбора). Исходные данные считываем и сортируем по времени прибытия в порядке убывания, а по продолжительности аренды - в порядке возрастания. В массиве/списке trays будем хранить время освобождения каждого лотка. В цикле по минутам для каждого продавца, прибывшего в данную минуту, находим лоток в соответствии с условиями задачи. Сначала ищем свободный лоток среди первых k. Если такой не найден, ищем первый освобождающийся. Эти два поиска можно объединить в один цикл: значение выбранного лотка меняется, если лоток свободен, а уже выбранный лоток относится к освобождающимся или лоток еще не выбран, а встретили освобождающийся лоток. Если среди первой половины лоток найти не удалось, ищем подходящий среди второй половины. Если подходящий лоток найден, увеличиваем счетчик продавцов count и меняем время освобождения выбранного лотка. Анализируем первую половину лотков. Если для всех лотков время освобождения больше текущего, увеличиваем счетчик занятости всех прибыльных лотков total. После обработки всех минут, выводим результат.
Python
f = open('26-131.txt')
n, k = map(int, f.readline().split())
a = [[int(y) for y in x.split()] for x in f]
a.sort(key=lambda x: x[1], reverse=True)
a.sort(key=lambda x: x[0])
trays = [0] * (k * 2)
count = 0
total = 0
i = 0
for time in range(a[-1][0] + a[-1][1] + 31):
while i < n and a[i][0] == time:
tray = - 1
for j in range(k):
if (trays[j] <= a[i][0] and (tray == -1 or trays[tray] > a[i][0]) or
tray == -1 and trays[j] - 15 <= a[i][0]):
tray = j
if tray == -1:
for j in range(k, k * 2):
if (trays[j] <= a[i][0] and (tray == -1 or trays[tray] > a[i][0]) or
tray == -1 and trays[j] - 15 <= a[i][0]):
tray = j
if tray != -1:
count += 1
trays[tray] = max(trays[tray], a[i][0]) + a[i][1] + 15
i += 1
all = True
for j in range(k):
if trays[j] <= time:
all = False
break
if all:
total += 1
print(count, total)
PascalABC
var
n, k, count, total, tray, time, min, i, j, t: Integer;
a: array [1..10000, 1..2] of Integer;
trays: array [1..100] of Integer;
all: Boolean;
f: TEXT;
begin
Assign(f, '26-131.txt');
Reset(f);
Readln(f, n, k);
for i := 1 to n do
Readln(f, a[i, 1], a[i, 2]);
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;
end;
end;
for i := 1 to k * 2 do
trays[i] := 0;
count := 0;
total := 0;
i := 1;
for time := 0 to a[n, 1] + a[n, 2] + 30 do
begin
while (i <= n) and (a[i, 1] = time) do
begin
tray := 0;
for j := 1 to k do
if (trays[j] <= a[i, 1]) and ((tray = 0) or (trays[tray] > a[i, 1])) or
(tray = 0) and (trays[j] - 15 <= a[i, 1]) then
tray := j;
if tray = 0 then
for j := k + 1 to k * 2 do
if (trays[j] <= a[i, 1]) and ((tray = 0) or (trays[tray] > a[i, 1])) or
(tray = 0) and (trays[j] - 15 <= a[i, 1]) then
tray := j;
if tray <> 0 then
begin
count := count + 1;
if trays[tray] > a[i, 1] then
trays[tray] := trays[tray] + a[i, 2] + 15
else
trays[tray] := a[i, 1] + a[i, 2] + 15;
end;
i := i + 1;
end;
all := True;
for j := 1 to k do
if trays[j] <= time then
begin
all := False;
break;
end;
if all then
total := total + 1;
end;
Writeln(count, ' ', totaL);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-131.txt");
int n, k;
f >> n>> k;
int a[10000][2];
for (int i = 0; i < n; i++)
f >> a[i][0] >> a[i][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] || 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;
}
}
int trays[100];
for (int i = 0; i < k * 2; i++)
trays[i] = 0;
int count = 0, total = 0, i = 0;
for (int time = 0; time < a[n - 1][0] + a[n - 1][1] + 30; time++)
{
while (i < n && a[i][0] == time)
{
int tray = -1;
for (int j = 0; j < k; j++)
if (trays[j] <= a[i][0] && (tray == -1 || trays[tray] > a[i][0]) ||
tray == -1 && trays[j] - 15 <= a[i][0])
tray = j;
if (tray == -1)
for (int j = k; j < k * 2; j++)
if (trays[j] <= a[i][0] && (tray == -1 || trays[tray] > a[i][0]) ||
tray == -1 && trays[j] - 15 <= a[i][0])
tray = j;
if (tray != -1)
{
count++;
if (trays[tray] > a[i][0])
trays[tray] += a[i][1] + 15;
else
trays[tray] = a[i][0] + a[i][1] + 15;
}
i++;
}
bool all = true;
for (int j = 0; j < k; j++)
if (trays[j] <= time)
{
all = false;
break;
}
if (all)
total++;
}
cout << count << " " << total << endl;
}
Ответ
1957 4095