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

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

Решение

Отсортируем исходные данные в двухмерном массиве 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

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