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

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

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

(А. Богданов) Проводится вычислительный эксперимент для определения необходимого количества самокатов на разных парковках города в начальный момент времени. Всего есть M парковок с номерами от 1 до М. Поступило всего N заявок на аренду самокатов. В каждой заявке указано время начала аренды в минутах от начала суток, продолжительность аренды, а также номера парковок старта и финиша. Определите сколько всего нужно самокатов, чтобы все заявки были выполнены, и какое наибольшее число самокатов в какой-то момент будут в аренде одновременно. Будем считать, что заряда самоката хватает на весь день и самокат может быть арендован со следующей минуты после окончания предыдущей аренды.

Входные данные представлены в файле 26-123.txt следующим образом. Первая строка входного файла содержит два натуральных числа, записанных через пробел: M (1 ≤ M ≤ 100) – количество парковок, и N (1 ≤ N ≤ 106) – количество заявок. Каждая из N последующих строк описывает содержит четыре целых числа: время начала аренды в минутах от начала суток, длительность аренды в минутах, номер парковки старта и номер парковки финиша.

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

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

При таких исходных данных нужно три самоката: два в начале размещаются на парковке 1 и один – на парковке 2. Одновременно в аренде находятся максимум два самоката (с 3-й по 8-ю минуту включительно). Ответ: 3 2.

Решение

Считываем исходные данные в массив/список и сортируем их по времени заказа. Создадим массив/список available, где будет хранится количество самокатов на каждой стоянке, в динамическом массиве/списке/векторе way будем хранить информацию о самокатах, которые находятся в пути. В переменной total будем подсчитывать необходимое количество самокатов. Последовательно обрабатываем заявки. Сначала удаляем из way все записи о самокатах, прибывших в пункты назначения до заказа обрабатываемой заявки, увеличивая счетчики стоянок прибытия. Если на стоянке отправления есть самокаты, то уменьшаем счетчик на единицу. Если доступных самокатов нет, то увеличиваем total на единицу. После этого добавляем заявку в way. Размер данного набора данных будет количеством самокатов в аренде в данный момент. Анализируем это значение на максимальность, помещая результат в переменную max (mx).

Python

f = open('26-123.txt')
m, n = map(int, f.readline().split())
a = [[int(y) for y in x.split()] for x in f]
a.sort()
available = [0] * (m + 1)
total = 0
way = []
mx = 0
for i in a:
    j = 0
    while j < len(way):
        if way[j][0] + way[j][1] <= i[0]:
            available[way[j][3]] += 1
            del way[j]
        else:
            j += 1
    if available[i[2]] > 0:
        available[i[2]] -= 1
    else:
        total += 1
    way.append(i)
    mx = max(mx, len(way))
print(total, mx)

PascalABC

type
    Rec = record
        start: Integer;
        time: Integer;
        pfrom: Integer;
        pto: Integer;
    end;
var
    n, m, max, min, total, i, j: Integer;
    a: array [1..1000] of Rec;
    available: array[1..20] of Integer;
    way: array of Rec = new Rec[0];
    t: Rec;
    f: TEXT;
begin
    Assign(f, '26-123.txt');
    Reset(f);
    Readln(f, m, n);
    for i := 1 to n do
        Readln(f, a[i].start, a[i].time, a[i].pfrom, a[i].pto);
    for i := 1 to n - 1 do
    begin
        min := i;
        for j := i + 1 to n do
            if a[j].start < a[min].start then
                min := j;
        if min <> i then
        begin
            t := a[i];
            a[i] := a[min];
            a[min] := t;
        end;
    end;
    for i := 1 to m do
        available[i] := 0;
    total := 0;
    max := 0;
    foreach t in a do
    begin
        i := 0;
        while i < way.Length do
            if way[i].start + way[i].time <= t.start then
            begin
                available[way[i].pto] := available[way[i].pto] + 1;
                way := way[:i] + way[i + 1:];
            end
            else
                i := i + 1;
        if available[t.pfrom] > 0 then
            available[t.pfrom] := available[t.pfrom] - 1
        else
            total := total + 1;
        way := way + Arr(t);
        if way.Length > max then
            max := way.Length;
    end;
    Writeln(total, ' ', max);
end.

C++

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
struct rec
{
    int start;
    int time;
    int pfrom;
    int pto;
};
int main()
{
    ifstream f;
    f.open("26-123.txt");
    int n, m;
    f >> m >> n;
    rec a[1000];
    for (int i = 0; i < n; i++)
        f >> a[i].start >> a[i].time >> a[i].pfrom >> a[i].pto;
    for (int i = 0; i < n - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (a[j].start < a[min].start)
                min = j;
        if (min != i)
        {
            rec t = a[i];
            a[i] = a[min];
            a[min] = t;
        }
    }
    int available[21];
    vector<rec> way;
    for (int i = 0; i <= m; i++)
        available[i] = 0;
    int max = 0, total = 0;
    for (rec t : a)
    {
        int i = 0;
        while (i < way.size())
            if (way[i].start + way[i].time <= t.start)
            {
                available[way[i].pto]++;
                way.erase(way.begin() + i);
            }
            else
                i++;
        if (available[t.pfrom] > 0)
            available[t.pfrom]--;
        else
            total++;
        way.push_back(t);
        if (way.size() > max)
            max = way.size();
    }
    cout << total << " " << max << endl;
}

Ответ

192 86

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

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

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

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