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

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

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

(PRO100-ЕГЭ) Входной файл содержит расписание показа фильмов во всех кинотеатрах Москвы за весь прошедший месяц. Определите суммарное время, в течение которого показывался хотя бы один фильм.

Входные данные представлены в файле 26-140.txt следующим образом. В первой строке входного файла находится натуральное число N (N ≤ 1000) – общее количество фильмов. Следующие N строк содержат пары натуральных чисел, обозначающих время начала и время окончания каждого фильма в минутах с начала месяца. Все числа не превосходят 44640.

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

Пример входного файла:
4
100 200
200 250
400 500
420 480

При таких исходных данных хотя бы один фильм показывался в промежутки времени [100; 250) и [400; 500). Суммарное время равно (250-100) + (500-400) = 250. Максимальный непрерывный отрезок времени, в течение которого показывался хотя бы один фильм равен 250-100 = 150. Ответ: 250 150.

Решение

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

Python

f = open('26-140.txt')
n = int(f.readline())
a = [[int(y) for y in x.split()] for x in f]
a.sort(key=lambda x: x[1], reverse=True) 
a.sort(key=lambda x: x[0]) 
start = 0
last = 0
total = 0
mx = 0
for i in a:
    if i[0] > last:
        start = i[0]
        last = i[0]
    if i[1] > last:
        total += i[1] - last
        last = i[1]
        mx = max(mx, last - start)
print(total, mx)

PascalABC

var
    n, start, total, max, last, min, i, j, t: Integer;
    a: array [1..10000, 1..2] of Integer;
    f: TEXT;
begin
    Assign(f, '26-140.txt');
    Reset(f);
    Readln(f, n);
    for i := 1 to n do
        Readln(f, a[i, 1], a[i, 2]);
    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]) 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;
        end;
    end;
    start := 0;
    last := 0;
    total := 0;
    max := 0;
    for i := 1 to n do
    begin
        if a[i, 1] > last then
        begin
            start := a[i, 1];
            last := a[i, 1];
        end;
        if a[i, 2] > last then
        begin
            total := total + a[i, 2] - last;
            last := a[i, 2];
            if last - start > max then
                max := last - start;
        end;
    end;
    Writeln(total, ' ', max);
end.

C++

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f;
    f.open("26-140.txt");
    int n;
    f >> n;
    int a[10000][2];
    for (int i = 0; i < n; i++)
        f >> a[i][0] >> a[i][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] || a[j][0] == a[min][0] && a[j][1] > a[min][1])
                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;
        }
    }
    int start = 0, last = 0, total = 0, max = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i][0] > last)
        {
            start = a[i][0];
            last = a[i][0];
        }
        if (a[i][1] > last)
        {
            total += a[i][1] - last;
            last = a[i][1];
            if (last - start > max)
                max = last - start;
        }
    }
    cout << total << " " << max << endl;
}

Ответ

38032 3014

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

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

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

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