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

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

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

(К. Багдасарян) Администрация торговой площадки составила список зарегистрированных у нее N компаний с указанием их порядкового номера и рейтинга. Расстоянием между двумя компаниями будем считать разницу их порядковых номеров. Необходимо определить максимальное расстояние между двумя компаниями с номерами i, j (i < j), такими, что выполняются следующие условия:

  1. рейтинг компании с номером j больше рейтинга компании с номером i;
  2. между номерами i и j не существует компании, у которой рейтинг выше, чем у компании с номером i.

Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке число N (1 ≤ N ≤ 10 000 000) – количество компаний.

Каждая из следующих N строк содержит два натуральных числа: порядковый номер (не превышающее 10000000) и рейтинг компании (не превышающее 10000000).

Пример входного файла:
5
1 4
2 10
3 8
4 7
5 15

При таких исходных данных правильным ответом будет расстояние между компаниями с номерами 2 и 5: рейтинг компании № 5 больше рейтинга компании № 2, и между компаниями № 2 и № 5 нет компании с рейтингом, большим чем 10 (рейтинг компании № 2). Ответ: 3. В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

Решение

Загружаем исходные данные в массив. Просматривая массив с конца, ищем максимальный элемент, а от этого элемента ищем элемент, удовлетворяющий условию задачи, фиксируя максимальное расстояние. Переменные:
mxn - индекс максимального элемента с конца;
max (mx) - максимальное расстояние между парой, удовлетворяющей условию, т.е. ответ на задачу;
mxr - максимальный рейтинг, зафиксированный перед элементом с индексом mxn.

Python

f = open("27-126b.txt")
n = int(f.readline())
m = [[int(y) for y in x.split()] for x in f.readlines()]
mxn = n - 1
mx = 0;
mxr = 0
for i in range(n-2, -1, -1):
    if m[i][1] < m[mxn][1] and m[i][1] >= mxr:
        mx = max(mx, m[mxn][0] - m[i][0])
    mxr = max(mxr, m[i][1])
    if m[i][1] >= m[mxn][1]:
        mxn = i
        mxr = 0
print(mx)

PascalABC

var
    n, i, mxn, mx, mxr: Integer;
    m: array [1..100000, 1..2] of Integer;
    f: TEXT;
begin
    Assign(f, '27-126b.txt');
    Reset(f);
    Readln(f, n);
    for i := 1 to n do
        readln(f, m[i, 1], m[i, 2]);
    mxn := n;
    mx := 0;
    mxr := 0;
    for i := n - 1 downto 1 do
    begin
        if (m[i, 2] < m[mxn, 2]) and (m[i, 2] >= mxr) then
            if m[mxn, 1] - m[i, 1] > mx then
                mx := m[mxn, 1] - m[i, 1];
        if m[i, 2] > mxr then
            mxr := m[i, 2];
        if m[i, 2] >= m[mxn, 2] then
        begin
            mxn := i;
            mxr := 0;
        end;
    end;
    writeln(mx);
end.

C++

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f;
    f.open("27-126b.txt");
    int n;
    f >> n;
    int m[100000][2];
    for (int i = 0; i < n; i++)
        f >> m[i][0] >> m[i][1];
    int mxn = n - 1, max = 0, mxr = 0;
    for (int i = n - 2; i >= 0; i--)
    {
        if (m[i][1] < m[mxn][1] && m[i][1] >= mxr)
            if (max < m[mxn][0] - m[i][0])
                max = m[mxn][0] - m[i][0];
        if (mxr < m[i][1])
            mxr = m[i][1];
        if (m[i][1] >= m[mxn][1])
        {
            mxn = i;
            mxr = 0;
        }
    }
    cout << max;
}

Ответ

253 725

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

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

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

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