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

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

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

(Л. Евич) В операционном зале есть N банкоматов, работающих круглосуточно. Все банкоматы пронумерованы. В течение дня M клиентов хотят воспользоваться банкоматом. Клиенты обслуживаются в порядке общей очереди. Если в один момент подошли несколько клиентов, то они становятся в очередь в порядке расположения данных в файле. Клиент, стоящий первым в очереди, подходит к первому освободившемуся банкомату (если таких несколько – к банкомату с наименьшим номером). Обслуживание очередного клиента может начаться в ту же минуту, когда банкомат станет свободным. Известно время в минутах от начала суток, когда клиент подошёл к банкомату, и время его обслуживания.

Определите наибольшее количество клиентов, которые были обслужены одним банкоматом за 24 часа, и время начала обслуживания последнего клиента. Последним обслуженным клиентом считается тот, который подошёл к любому банкомату до окончания суток (его обслуживание могло закончиться в следующие сутки).

Входные данные представлены в файле 26-112.txt следующим образом. В первой строке входных данных задается два числа: N - количество банкоматов и M – количество клиентов. В каждой из последующих M строк содержится информация по одному клиенту: время начала обслуживания клиента (в минутах с начала суток) и время обслуживания (в минутах).

Запишите в ответе два числа: наибольшее количество клиентов, которые были обслужены одним банкоматом за 24 часа, и время начала обслуживания последнего клиента.

Пример входного файла:
2 5
1 8
6 12
8 4
8 14
8 9

При таких исходных данных наибольшее число клиентов (3) обслужит 1-й банкомат: это клиенты со временем обслуживания 8, 4 и 14. Последний клиент начинает работу со 2-м банкоматом на 18-й минуте. Ответ: 3 18.

Решение

Считываем данные в массив/список и сортируем стабильным алгоритмом сортировки (пузырьковая сортировка или сортировка вставкой), чтобы сохранить порядок клиентов с одинаковым временем начала обслуживания. Создадим двухмерный массив/список atms, где для каждого банкомата будем хранить количество обслуженных клиентов за 24 часа, время обслуживания последнего клиента до истечения суток и время освобождения банкомата. Для каждого клиента находим свободный к моменту визита банкомат с минимальным номером, а если такового нет, то с минимальным временем освобождения. Если время освобождения находится до истечения 24 часов, меняем для банкомата количество обслуженных клиентов и время обслуживания последнего клиента. После обработки всех клиентов ищем банкомат с наибольшим числом обслуженных клиентов и банкомат с максимальным временем последнего обслуженного клиента.

Python

f = open('26-112.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])
atms = [[0] * 3 for i in range(n)]
for i in a:
    atm = 0
    for j in range(1, n):
        if atms[j][2] < atms[atm][2] and atms[atm][2] > i[0]:
            atm = j
    if atms[atm][2] <= 1440:
        atms[atm][1] = atms[atm][2]
        atms[atm][0] += 1
    atms[atm][2] = max(atms[atm][2], i[0]) + i[1]
mxi = 0
mxt = 0
for i in range(1, n):
    if atms[i][0] > atms[mxi][0]:
        mxi = i
    if atms[i][1] > atms[mxt][1]:
        mxt = i
print(atms[mxi][0], atms[mxt][1])

PascalABC

var
    n, m, maxi, maxt, atm, i, j, t: Integer;
    a: array [1..3500, 1..2] of Integer;
    atms: array [1..20, 1..3] of Integer;
    f: TEXT;
begin
    Assign(f, '26-112.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
    begin
        atms[i, 1] := 0;
        atms[i, 2] := 0;
        atms[i, 3] := 0;
    end;
    for i := 1 to m do
    begin
        atm := 1;
        for j := 2 to n do
            if (atms[j, 3] < atms[atm, 3]) and (atms[atm][3] > a[i, 1]) then
                atm := j;
        if atms[atm, 3] <= 1440 then
        begin
            atms[atm, 2] := atms[atm, 3];
            atms[atm, 1] := atms[atm, 1] + 1;
        end;
        if atms[atm, 3] > a[i, 1] then
            atms[atm, 3] := atms[atm, 3] + a[i, 2]
        else
            atms[atm, 3] := a[i, 1] + a[i, 2];
    end;
    maxi := 1;
    maxt := 1;
    for i := 2 to n do
    begin
        if atms[i, 1] > atms[maxi, 1] then
            maxi := i;
        if atms[i, 2] > atms[maxt, 2] then
            maxt := i;
    end;
    Writeln(atms[maxi, 1], ' ', atms[maxt, 2]);
end.

C++

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f;
    f.open("26-112.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 atms[20][3];
    for (int i = 0; i < n; i++)
    {
        atms[i][0] = 0;
        atms[i][1] = 0;
        atms[i][2] = 0;
    }
    for (int i = 0; i < m; i++)
    {
        int atm = 0;
        for (int j = 1; j < n; j++)
            if (atms[j][2] < atms[atm][2] && atms[atm][2] > a[i][0])
                atm = j;
        if (atms[atm][2] <= 1440)
        {
            atms[atm][1] = atms[atm][2];
            atms[atm][0]++;
        }
        if (atms[atm][2] > a[i][0])
            atms[atm][2] += a[i][1];
        else
            atms[atm][2] = a[i][0] + a[i][1];
    }
    int maxi = 0, maxt = 0;
    for (int i = 1; i < n; i++)
    {
        if (atms[i][0] > atms[maxi][0])
            maxi = i;
        if (atms[i][1] > atms[maxt][1])
            maxt = i;
    }
    cout << atms[maxi][0] << " " << atms[maxt][1] << endl;
}

Ответ

91 1439

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

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

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

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