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

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

Решение

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

Python

f = open("27-162b.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 z[i][0] + z[j][0] >= k:
                mx = max(mx, 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-162b.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 a[z][i].val + a[z][j].val > max then
                        max := 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-162b.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 (a[z][i].val + a[z][j].val >= max)
                        max = a[z][i].val + a[z][j].val;
    cout << max << endl;
}

Возможно обойтись и более простой структурой данных в виде двухмерного массива/списка. Отсортируем данные по номерам приборов, что расположит данные одного прибора рядом. Учитывайте, что на сортировку данных большого файла потребуется некоторое время. Для каждого прибора найдем индекс самых первых данных и индекс самых последних и так же переберем все пары показаний.

Python

f = open("27-162b.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 a[i][1] + a[j][1] >= k:
                mx = max(mx, 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-162b.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  (a[i, 3] + a[j, 3] > max) then
                    max := 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-162b.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 && a[i][2] + a[j][2] >= max)
                    max = a[i][2] + a[j][2];
        start = finish;
    }
    cout << max << endl;
}

Ответ

1995 199895754

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