Задача 6673. Источник: Поляков. Задание КИМ 27
(PRO100 ЕГЭ) По каналу связи передаются данные измерений группы приборов: номер прибора, время измерения (в секундах с начала суток) и показание прибора. Определите максимальную разницу показаний одного прибора, между моментами передачи которых прошло не менее K минут.
Примечание: разница – это модуль разности двух значений.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число N (2 ≤ N ≤ 10 000 000) – количество строк с данными, и натуральное число K (1 ≤ K ≤ N) – минимальный интервал времени между двумя показаниями одного прибора. Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000 000: номер прибора, время измерений и результат измерений.
Пример входного файла:
5 3
1 1 15
2 2 10
2 3 35
1 4 0
2 5 30
При таких исходных данных максимально возможная разница равна 20 – это разница показаний прибора 2 на второй и пятой минутах. Ответ: 20.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Самое простое решение: разделить данные по номерам приборов. Для меньшего расхода памяти лучше всего использовать ассоциативные массивы, но во втором файле максимальный номер прибора - 10000, а потому гораздо проще использовать обычный массив по числу приборов, где для прибора будет хранится информация о переданных показаниях. После этого перебираем для каждого прибора все возможные пары показаний и, если интервал времени больше k, анализируем разность на максимальное значение.
Python
f = open("27-164b.txt")
n, k = map(int, f.readline().split())
a = [[] for i in range(10001)]
for i in f:
x, y, z = map(int, i.split())
a[x].append([y, z])
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..10000] of array of dataa;
f: TEXT;
begin
for i := 1 to 10000 do
a[i] := new dataa[0];
Assign(f, '27-164b.txt');
Reset(f);
Readln(f, n, k);
for i := 1 to n do
begin
Readln(f, x, y, z);
d.time := y;
d.val := z;
a[x] := a[x] + Arr(d);
end;
max := 0;
for z := 1 to 10000 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-164b.txt");
int n, k;
f >> n >> k;
vector<dataa> a[10001];
for (int i = 0; i < n; i++)
{
int x;
dataa t;
f >> x >> t.time >> t.val;
a[x].push_back(t);
}
int max = 0;
for (int z = 0; z <= 10000; 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-164b.txt")
n, k = map(int, f.readline().split())
a = [[int(y) for y in x.split()] for x in f]
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..45135, 1..3] of Integer;
f: TEXT;
begin
Assign(f, '27-164b.txt');
Reset(f);
Readln(f, n, k);
for i := 1 to n do
Readln(f, a[i, 1], a[i, 2], a[i, 3]);
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-164b.txt");
int n, k;
f >> n >> k;
int a[45135][3];
for (int i = 0; i < n; i++)
f >> a[i][0] >> a[i][1] >> 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;
}
Ответ
898 98526430