Задача 6666. Источник: Поляков. Задание КИМ 26
(Е. Джобс) Поезд, в котором К мест (с номерами от 1 до К), следует по магистрали через M населенных пунктов. мест. Дан список из N заявок на поездку, для каждой из которых известно, на какой станции пассажир собирается садиться, а на какой — выходить. При посадке на некоторой станции контроллер отдает предпочтение тому пассажиру, который едет дальше остальных, определяя место пассажира, как свободное с минимальным номером. При этом сначала осуществляется высадка пассажиров, а затем посадка.
Определите, сколько пассажиров смогут добраться до пункта своего назначения и на скольких перегонах в поезде будут заняты все места (перегон – это участок магистрали между соседними населенными пунктами).
Входные данные представлены в файле 26-126.txt следующим образом. Первая строка входного файла содержит три натуральных числа: M (2 ≤ M ≤ 2000) – количество населенных пунктов со станциями на магистрали, K (1 ≤ K ≤ 1000) – количество мест в поезде и N (1 ≤ N ≤ 10000) – количество пассажиров, желающих проехать на поезде.
В каждой из последующих N строк располагаются пары чисел: сначала номер населенного пункта, откуда хочет начать свою поездку пассажир, затем номер населенного пункта, где пассажир собирается сойти с поезда.
В ответе запишите два числа: количество пассажиров, которые смогут добраться до пункта своего назначения, и количество перегонов, на которых в поезде будут заняты все места.
Пример входного файла:
10 3 6
2 6
2 4
3 5
3 8
4 9
4 6
При таких исходных данных добраться до нужного пункта смогут 4 пассажира ( (2, 6), (2, 4), (3, 8), (4, 9) ). При этом свободных мест не будет на перегонах 3 перегонах (3-4, 4-5 и 5-6). Ответ: 4 3.
Решение
Сортируем исходные данные по станции посадки в порядке возрастания, а при одинаковой станции посадки, по станции высадки в порядке убывания. Создадим массив/список/вектор places, в котором будем хранить данные о станциях высадки пассажиров, севших в поезд. В цикле по станциям удаляем из places информацию о пассажирах, которые выходят на текущей станции и добавляем пассажиров с текущей станции, пока для них есть места, увеличивая счетчик перевезенных пассажиров count. Если после обработки всех пассажиров текущей станции поезд заполнен полностью, увеличиваем счетчик перегонов stages.
Python
f = open('26-126.txt')
m, k, n = 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])
count = 0
stages = 0
places = []
z = 0
for i in range(1, m + 1):
j = 0
while j < len(places):
if places[j] == i:
del places[j]
else:
j += 1
while z < n and a[z][0] == i:
if len(places) < k:
count += 1
places.append(a[z][1])
z += 1
if len(places) == k:
stages += 1
print(count, stages)
PascalABC
var
n, m, k, count, stages, i, j, min, t, z: Integer;
a: array [1..3333, 1..2] of Integer;
places: array of Integer = new Integer[0];
f: TEXT;
begin
Assign(f, '26-126.txt');
Reset(f);
Readln(f, m, k, n);
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;
count := 0;
stages := 0;
z := 1;
for i := 1 to m do
begin
j := 0;
while j < places.Length do
if places[j] = i then
if j < places.Length - 1 then
places := places[:j] + places[j + 1:]
else
places := places[:j]
else
j := j + 1;
while (z <= n) and (a[z, 1] = i) do
begin
if places.Length < k then
begin
count := count + 1;
places := places + Arr(a[z, 2]);
end;
z := z + 1;
end;
if places.Length = k then
stages := stages + 1;
end;
Writeln(count, ' ', stages);
end.
C++
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-126.txt");
int m, k, n;
f >> m >> k >> n;
int a[3333][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 count = 0, stages = 0, z = 0;
vector<int> places;
for (int i = 1; i <= m; i++)
{
int j = 0;
while (j < places.size())
if (places[j] == i)
places.erase(places.begin() + j);
else
j++;
while (z < n && a[z][0] == i)
{
if (places.size() < k)
{
count++;
places.push_back(a[z][1]);
}
z++;
}
if (places.size() == k)
stages++;
}
cout << count << " " << stages << endl;
}
Ответ
2873 267