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

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

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

(Л. Шастин) В отеле есть K жилых номеров, предназначенных для размещения туристов. Все номера пронумерованы, начиная с единицы. Известно время, в которое каждая группа туристов заселяются в номера; время, в которое они планируют их освободить, а также количество номеров, которое потребуется для того, чтобы разместить всю группу туристов сразу. Каждая группа туристов заселяется в свободные номера с наименьшими номерами. Если несколько групп туристов пришли одновременно, то прежде всего обслуживаются группы, которые планируют уйти раньше и для размещения которых требуется меньшее количество номеров. На заселение и выселение туристов уходит одна минута. Со следующей минуты можно заселять в освободившийся номер других туристов. Если группа туристов пришла, но необходимого количества (которого достаточно для заселения их всех) свободных номеров нет – вся группа уходит, потому что заселиться не может.

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

Входные данные представлены в файле 26-137.txt следующим образом. В первой строке входного файла находится число K – количество жилых номеров в отеле (натуральное число, не превышающее 1000). Во второй строке находится число N – количество групп туристов, которые собираются заселиться в номера. В каждой из следующих N строках находятся три значения:
– минута заселения группы туристов;
– минута, до которой группа туристов планирует проживать в номерах;
– количество номеров, которое потребуется для размещения всей группы.

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

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

Пример входного файла:
10
5
30 60 5
40 1110 2
30 60 3
60 120 1
120 1440 2

При таких исходных данных первая, вторая, третья и пятая группа туристов смогут заселиться в номера. В первые 29 минут от начала дня все номера были свободны, далее до 40 минуты были свободны 2 номера. С 40-й и до 60-й минуты все номера были заняты на протяжении 21-й минуты, а затем до конца дня хотя бы один из номеров всегда был свободен. Значит, суммарное время, в которое хотя бы один из номеров был свободен, равно 1440 - (60 - 40 + 1) = 1440 - 21 = 1419. Ответ: 4 1419.

Решение

Данные сортируем в порядке возрастания по всем полям. В переменной count будем подсчитывать количество размещенных групп, alltime - общее время, когда все номера были заняты, free - текущее количество свободных номеров, allstart - начальное время, когда были заняты все номера (если все номера не были заняты, то значение -1). Так же в списке/массиве/векторе busy будем хранить информацию о занятых номерах. Каждый элемент будет содержать время освобождения и количество освобождаемых номеров.

Последовательно обрабатываем отсортированные данные. Из busy удаляем информацию о номерах, которые освободились к моменту заселения рассматриваемой группы. При удалении увеличиваем free на количество освобождаемых номеров, , а так же находим минимальное время, когда освободился какой-то номер mintime. Ели ранее у нас были заняты все номера (allstart имеет положительное значение) и какие-то номера освободились, то добавляем к alltime интервал от mintime до allstart включительно (в этом промежутке были заняты все номера). Если количество свободных номеров позволяет разместить рассматриваемую группу, то увеличиваем count, уменьшаем free на количество занятых номеров и добавляем информацию о занятых номерах в busy. Если с заселением данной группы были заняты все номера, обновляем значение allstart. После обработки всех групп выводим count и разницу между 1440 (количество минут в сутках) и alltime (в течение этого времени был свободен хотя бы один номер).

Python

f = open('26-137.txt')
k = int(f.readline())
n = int(f.readline())
a = [[int(y) for y in x.split()] for x in f]
a.sort()
count = 0
alltime = 0
allstart = -1
free = k
busy = []
for i in a:
    mintime = 10000
    j = 0
    while j < len(busy):
        if busy[j][0] < i[0]:
            mintime = min(mintime, busy[j][0])
            free += busy[j][1]
            del busy[j]
        else:
            j += 1
    if allstart != -1 and free != 0:
        alltime += mintime - allstart + 1
        allstart = -1
    if free >= i[2]:
        count += 1
        free -= i[2]
        busy.append(i[1:])
        if free == 0:
            allstart = i[0]
print(count, 1440 - alltime)

PascalABC

type
    Rec = record
        time: Integer;
        count: Integer;
    end;
var
    n, k, count, alltime, mintime, allstart, free, min, i, j, t: Integer;
    a: array [1..1000, 1..3] of Integer;
    busy: array of Rec  = new Rec[0];
    tmp: Rec;
    f: TEXT;
begin
    Assign(f, '26-137.txt');
    Reset(f);
    Readln(f, k, n);
    for i := 1 to n do
        Readln(f, a[i, 1], a[i, 2], a[i, 3]);
    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])or
               (a[j, 1] = a[min, 1]) and (a[j, 2] = a[min, 2]) and (a[j, 3] < a[min, 3]) 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;
    count := 0;
    alltime := 0;
    allstart := -1;
    free := k;
    for i := 1 to n do
    begin
        mintime := 10000;
        j := 0;
        while j < busy.Length do
            if busy[j].time < a[i, 1] then
            begin
                if busy[j].time < mintime then
                    mintime := busy[j].time;
                free := free + busy[j].count;
                if j < busy.Length - 1 then
                    busy := busy[:j] + busy[j + 1:]
                else
                    busy := busy[:j];
            end
            else
                j := j + 1;
        if (allstart <> -1) and (free <> 0) then
        begin
            alltime := alltime + mintime - allstart + 1;
            allstart := -1;
        end;
        if free >= a[i, 3] then
        begin
            count := count + 1;
            free := free - a[i, 3];
            tmp.time := a[i, 2];
            tmp.count := a[i, 3];
            busy := busy + Arr(tmp);
            if free = 0 then
                allstart := a[i][1];
        end;
    end;
    Writeln(count, ' ', 1440 - alltime);
end.

C++

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
struct rec
{
    int time;
    int count;
};
int main()
{
    ifstream f;
    f.open("26-137.txt");
    int n, k;
    f >> k >> n;
    int a[1000][3];
    for (int i = 0; i < n; i++)
        f >> a[i][0] >> a[i][1] >> a[i][2];
    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] ||
                a[j][0] == a[min][0] && a[j][1] == a[min][1] && a[j][2] < a[min][2])
                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 count = 0, alltime = 0, allstart = -1, free = k;
    vector<rec> busy;
    for (int i = 0; i < n; i++)
    {
        int mintime = 10000, j = 0;
        while (j < busy.size())
            if (busy[j].time < a[i][0])
            {
                if (busy[j].time < mintime)
                    mintime = busy[j].time;
                free += busy[j].count;
                busy.erase(busy.begin() + j);
            }
            else
                j++;
        if (allstart != -1 && free != 0)
        {
            alltime += mintime - allstart + 1;
            allstart = -1;
        }
        if (free >= a[i][2])
        {
            count++;
            free -= a[i][2];
            rec tmp;
            tmp.time = a[i][1];
            tmp.count = a[i][2];
            busy.push_back(tmp);
            if (free == 0)
                allstart = a[i][0];
        }
    }
    cout << count << " " << 1440 - alltime << endl;
}

Ответ

291 1077

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

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

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

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