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

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

Решение

Самым простым решением является разделение данных по номерам приборов. Максимальный номер прибора во втором файле - 1000. Создадим массив, где для каждого прибора будем сохранять список переданных им показанием с указанием времени передачи. Для каждого прибора переберем все пары показаний и, если временной интервал между ними не менее k, проанализируем разность на максимальность.

Python

f = open("27-163b.txt")
n, k = map(int, f.readline().split())
a = [[] for i in range(1001)]
for i in range(1, n + 1):
    x, y = map(int, f.readline().split())
    a[x].append([i, y])
mx = 0
for z in a:
    for i in range(len(z) - 1):
        for j in range(i + 1, len(z)):
            if abs(z[i][0] - z[j][0]) >= k:
                mx = max(mx, abs(z[i][1] - z[j][1]))
print(mx)

PascalABC

type
    dataa = record
      time: Integer;
      val: Integer;
    end;
var
    n, k, max, i, j, x, y, z: Integer;
    d: dataa;
    a: array [1..1000] of array of dataa;
    f: TEXT;
begin
    for i := 1 to 1000 do
        a[i] := new dataa[0];
    Assign(f, '27-163b.txt');
    Reset(f);
    Readln(f, n, k);
    for i := 1 to n do
    begin
        Readln(f, x, y);
        d.time := i;
        d.val := y;
        a[x] := a[x] + Arr(d);
    end;
    max := 0;
    for z := 1 to 1000 do
        for i := 0 to a[z].Length - 2 do
            for j := i + 1 to a[z].Length - 1 do
                if abs(a[z][i].time - a[z][j].time) >= k then
                    if abs(a[z][i].val - a[z][j].val) > max then
                        max := abs(a[z][i].val - a[z][j].val);
    Writeln(max);
end.

C++

#include <iostream>
#include <fstream>
#include <vector>
struct dataa
{
    int time;
    int val;
};
using namespace std;
int main()
{
    ifstream f;
    f.open("27-163b.txt");
    int n, k;
    f >> n >> k;
    vector<dataa> a[1001];
    for (int i = 1; i <= n; i++)
    {
        int x;
        dataa t;
        t.time = i;
        f >> x >> t.val;
        a[x].push_back(t);
    }
    int max = 0;
    for (int z = 0; z <= 1000; z++)
        for (int i = 0; i < (int)a[z].size() - 1; i++)
            for (int j = i + 1; j < a[z].size(); j++)
                if (abs(a[z][i].time - a[z][j].time) >= k)
                    if (abs(a[z][i].val - a[z][j].val) >= max)
                        max = abs(a[z][i].val - a[z][j].val);
    cout << max << endl;
}

Можно обойтись и более простой структурой данных в виде двумерного массива, который отсортируем по номерам приборов (сортировка второго файла будет занимать некоторое время). Таким образом, показания одного прибора будут находится рядом. Последовательно просматривая данный массив, будем находить индексы самых первых и самых последних данных для каждого прибора, а потом так же перебирать все пары показаний одного прибора.

Python

f = open("27-163b.txt")
n, k = map(int, f.readline().split())
a = []
for i in range(1, n + 1):
    x, y = map(int, f.readline().split())
    a.append([x, i, y])
a.sort()
mx = 0
start = 0
finish = 0
while start != n:
    while finish < n and a[start][0] == a[finish][0]:
        finish += 1
    for i in range(start, finish - 1):
        for j in range(i + 1, finish):
            if abs(a[i][1] - a[j][1]) >= k:
                mx = max(mx, abs(a[i][2] - a[j][2]))
    start = finish
print(mx)

PascalABC

var
    n, k, max, min, start, finish, t, i, j: Integer;
    a: array [1..74190, 1..3] of Integer;
    f: TEXT;
begin
    Assign(f, '27-163b.txt');
    Reset(f);
    Readln(f, n, k);
    for i := 1 to n do
    begin
        a[i, 2] := i;
        Readln(f, a[i, 1], a[i, 3]);
    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;
    max := 0;
    start := 1;
    finish := 1;
    while start <= n do
    begin
        while (finish <= n) and (a[start, 1] = a[finish, 1]) do
            finish := finish + 1;
        for i := start to finish - 2 do
            for j := i + 1 to finish - 1 do
                if (abs(a[i, 2] - a[j, 2]) >= k) and  (abs(a[i, 3] - a[j, 3]) > max) then
                    max := abs(a[i, 3] - a[j, 3]);
        start := finish;
    end;
    Writeln(max);
end.

C++

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f;
    f.open("27-163b.txt");
    int n, k;
    f >> n >> k;
    int a[74190][3];
    for (int i = 1; i <= n; i++)
    {
        a[i][1] = i;
        f >> a[i][0] >> 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])
                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 max = 0, start = 0, finish = 0;
    while (start != n)
    {
        while (finish < n && a[start][0] == a[finish][0])
            finish++;
        for (int i = start; i < finish - 1; i++)
            for (int j = i + 1; j < finish; j++)
                if (abs(a[i][1] - a[j][1]) >= k && abs(a[i][2] - a[j][2]) >= max)
                    max = abs(a[i][2] - a[j][2]);
        start = finish;
    }
    cout << max << endl;
}

Ответ

900 98964798

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