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

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

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

На парковке есть L мест для легковых автомобилей и M мест для микроавтобусов. Приезжающий на парковку автомобиль занимает любое подходящее свободное место, при этом легковой автомобиль может встать на свободное место, предназначенное для микроавтобуса, но микроавтобус не может занять место, предназначенное для легкового автомобиля. Если подходящего свободного места нет, автомобиль уезжает. Гарантируется, что никакие два автомобиля не приезжают одновременно. Если время прибытия автомобиля совпадает со временем окончания стоянки другого автомобиля, вновь прибывший автомобиль может занять освободившееся место, если оно подходит ему по типу.

Определите количество микроавтобусов, которые смогут припарковаться, и общее количество автомобилей (как легковых, так и микроавтобусов), которые уедут из-за отсутствия мест.

Входные данные представлены в файле 26-119.txt следующим образом. Первая строка входного файла содержит три целых числа: N – общее количество автомобилей, приехавших на парковку в течение суток; L – количество мест для легковых автомобилей и M – количество мест для микроавтобусов. Каждая из следующих N строк описывает один автомобиль и содержит два целых числа и букву. Первое число означает время в минутах с начала суток, когда автомобиль прибыл на парковку, второе – необходимую длительность стоянки в минутах. Буква означает тип автомобиля: A – легковой, B – микроавтобус.

В ответе запишите два целых числа: сначала количество микроавтобусов, которые смогут припарковаться, затем – общее количество автомобилей (как легковых, так и микроавтобусов), которые уедут из-за отсутствия мест.

Пример входного файла:
5 2 1
5 22 A
8 30 B
14 15 A
25 12 A
20 40 B

При таких исходных сумеет припарковаться только один микроавтобус, приехавший на 8-й минуте. Два автомобиля – легковой на 25-й минуте и микроавтобус на 20-й – уедут, не найдя место для парковки. Ответ: 1 2.

Решение

Отсортируем исходные данные в двухмерном массиве a по времени прибытия на парковку (в программах на PascalABC и C++ использован алгоритм сортировки выбором). Последовательно обрабатывая информацию об автомобилях, будем выбирать подходящее парковочное место и помещать информацию о времени его освобождения в двухмерный массив b, где первым элементом является время освобождения, а вторым - тип места. Переменная nb хранит фактическое количество данных в массиве. Перед помещением каждого нового автомобиля в массив b, будем удалять из него все автомобили, которые должны были покинуть парковку к прибытию обрабатываемой машины. Объем данных в задаче небольшой, а потому нет фактической необходимости оптимизации работы с массивом b. Новые данные добавляются в конец массива, а при обработке нового автомобиля, в нем анализируется каждая строка. При значительно большем объеме данных целесообразно делать этот массив отсортированным. Вариант такого оптимизированного решения приведен в схожей Задаче 6413. Помимо указанных двух массивов, в программе используются следующие одномерные массивы:
total - общее количество мест по типам;
busy - количество занятых в данный момент мест для каждого типа.

Python

f = open('26-119.txt')
total = [0] * 2
n, total[0], total[1] = map(int, f.readline().split())
busy = [0] * 2
count = 0;
lost = 0;
a = []
for i in f:
    x, y, z = i.split()
    if z == 'A':
        a.append([int(x), int(y), 0])
    else:
        a.append([int(x), int(y), 1])
a.sort()
b = []
for i in a:
    j = 0
    while j < len(b):
        if b[j][0] <= i[0]:
            busy[b[j][1]] -= 1
            del b[j]
        else:
            j += 1
    category = -1
    if i[2] == 0:
        if total[0] > busy[0]:
            category = 0
        elif total[1] > busy[1]:
            category = 1
    elif total[1] > busy[1]:
        category = 1
    if category != - 1:
        b.append([i[0] + i[1], category])
        busy[category] += 1
        if i[2] == 1:
            count += 1
    else:
        lost += 1
print(count, lost)

PascalABC

var
    n, m, i, j, z, nb, t, count, lost, category, min: Integer;
    a: array [1..900, 1..3] of Integer;
    b: array [1..900, 1..2] of Integer;
    total, busy: array [0..1] of Integer;
    s: String;
    f: TEXT;
begin
    Assign(f, '26-119.txt');
    Reset(f);
    Readln(f, n, total[0], total[1]);
    busy[0] := 0;
    busy[1] := 0;
    for i := 1 to n do
    begin
        Readln(f, a[i, 1], a[i, 2], s);
        if s.Contains('A') then
            a[i, 3] := 0
        else
            a[i, 3] := 1
    end;
    for i := 1 to n - 1 do
    begin
        min := i;
        for j := i + 1 to n do
            if a[j, 1] < a[min, 1] 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;
    nb := 0;
    count := 0;
    lost := 0;
    for i := 1 to n do
    begin
        j := 1;
        while j <= nb do
            if b[j, 1] <= a[i, 1] then
            begin
                busy[b[j, 2]] := busy[b[j, 2]] - 1;
                for z := j + 1 to nb do
                begin
                    b[z - 1, 1] := b[z, 1];
                    b[z - 1, 2] := b[z, 2];
                end;
                nb := nb - 1
            end
            else
                j := j + 1;
        category := -1;
        if a[i, 3] = 0 then
        begin
            if total[0] > busy[0] then
                category := 0
            else if total[1] > busy[1] then
                category := 1;
        end
        else if total[1] > busy[1] then
            category := 1;
        if category <> -1 then
        begin
            nb := nb + 1;
            b[nb, 1] := a[i, 1] + a[i, 2];
            b[nb, 2] := category;
            busy[category] := busy[category] + 1;
            if a[i, 3] = 1 then
                count := count + 1;
        end
        else
            lost := lost + 1;
    end;
    Writeln(count, ' ', lost);
end.

C++

#include 
#include 
using namespace std;
int main()
{
    ifstream f;
    f.open("26-119.txt");
    int m, n;
    int total[2], busy[2] = {0, 0};
    int a[900][3], b[900][2];
    f >> n >> total[0] >> total[1];
    for (int i = 0; i < n; i++)
    {
        string s;
        f >> a[i][0] >> a[i][1] >> s;
        if (s == "A")
            a[i][2] = 0;
        else
            a[i][2] = 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])
                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 nb = 0, count = 0, lost = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < nb; j++)
            if (b[j][0] <= a[i][0])
            {
                busy[b[j][1]]--;
                for (int z = j + 1; z < nb; z++)
                {
                    b[z - 1][0] = b[z][0];
                    b[z - 1][1] = b[z][1];
                }
                nb--;
                j--;
            }
        int category = -1;
        if (a[i][2] == 0)
        {
            if (total[0] > busy[0])
                category = 0;
            else if (total[1] > busy[1])
                category = 1;
        }
        else if (total[1] > busy[1])
            category = 1;
        if (category != -1)
        {
            b[nb][0] = a[i][0] + a[i][1];
            b[nb][1] = category;
            nb++;
            busy[category]++;
            if (a[i][2] == 1)
                count++;
        }
        else
            lost++;
    }
    cout << count << " " << lost << endl;
}

Ответ

439 26

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

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

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

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