Программное решение задач ЕГЭ по информатике

Задача 6666. Источник: Поляков. Задание КИМ 26

Страница задачи 6666

(Е. Джобс) Поезд, в котором К мест (с номерами от 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

Отправить замечание по решению

Код по которому имеется замечание:

Ваш вариант кода:

Комментарий: