Задача 6799. Источник: Поляков. Задание КИМ 27
(ЕГЭ-2023) Менеджер по работе с персоналом присваивает рейтинговый балл каждому из N кандидатов, резюме которых он изучает. Он хочет нанять двух специалистов с суммарным рейтингом не менее К баллов. Требуется по имеющимся данным о баллах N кандидатов определить, сколько различных пар кандидатов можно выбрать так, чтобы их суммарный рейтинговый балл составлял не менее К. Две пары кандидатов считаются различными, если хотя бы один из членов пары не присутствует в другой паре. Запишите в ответе найденное количество пар.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число N (1 < N ≤ 10 000 000) – количество кандидатов, и натуральное число К (1 < K ≤ 10 000 000) – ограничение на суммарный рейтинг двух кандидатов в баллах. В каждой из следующих N строк находится одно число: рейтинговый балл соответствующего кандидата.
Пример входного файла:
5 100
20
50
50
100
200
При таких исходных данных искомая величина равна 8. Первый кандидат может составлять пары с двумя последними; второй кандидат с рейтингом 50 может быть в паре с третьим, четвёртым или пятым; третий имеет такой же рейтинг, как второй, и может составлять пару с четвёртым или пятым кандидатом, которые, в свою очередь, образуют допустимую пару друг с другом. Ответ: 8.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Обратите внимание, что получение ответа для второго файла требует использования 64-разрядной целой переменной. Так же в решении учитывается, что данные в файле уже отсортированы. Считываем данные из файла в массив/список. Для каждого элемента находим величину минимального парного рейтинга p и, если такой рейтинг имеется, с помощью алгоритма правого бинарного поиска находим индекс первого элемента следующего за обрабатываемым с рейтингом равным или больше парного. Все элементы с найденного индекса образуют пары. Такое решение проще, но требует много памяти и для обработки второго файла требует времени (на Python требуется около минуты).
Python
f = open("27-169b.txt")
n, k = map(int, f.readline().split())
a = [int(x) for x in f]
count = 0
for i in range(n - 1):
p = k - a[i]
if a[-1] >= p:
left = i
right = n - 1
while left != right - 1:
center = (left + right) // 2
if a[center] < p:
left = center
else:
right = center
count += n - right;
print(count)
PascalABC
var
n, k, p, left, right, center, i: Integer;
count: Int64;
a: array [1..4999697] of Integer;
f: TEXT;
begin
Assign(f, '27-169b.txt');
Reset(f);
Readln(f, n, k);
for i := 1 to n do
Readln(f, a[i]);
for i := 1 to n - 1 do
begin
p := k - a[i];
if a[n] >= p then
begin
left := i;
right := n;
while left <> right - 1 do
begin
center := (left + right) div 2;
if a[center] < p then
left := center
else
right := center;
end;
count := count + n - right + 1;
end;
end;
Writeln(count);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("27-169b.txt");
int n, k;
f >> n >> k;
int* a = new int[n];
for (int i = 0; i < n; i++)
f >> a[i];
long long count = 0;
for (int i = 0; i < n - 1; i++)
{
int p = k - a[i];
if (a[n - 1] >= p)
{
int left = i, right = n - 1;
while (left != right - 1)
{
int center = (left + right) / 2;
if (a[center] < p)
left = center;
else
right = center;
}
count += n - right;
}
}
cout << count << endl;
delete[] a;
}
Более эффективное решение, как по времени, так и по расходуемой памяти основано на подсчете количества людей с различным рейтингом и обработка этих данных на основе комбинаторики. MX - максимальное значение рейтинга в файле данных. Считывая данные, в массиве/списке r подсчитываем количество кандидатов с каждым рейтингом. В массиве/списке rs посчитаем количество людей с рейтингом равным и больше индекса элемента. Каждый кандидат с рейтингом i образует пару с каждым кандидатом с рейтингом k - i > i. Если i >= k / 2, то каждый кандидат с рейтингом i образует пару с любым другим кандидатом с таким же рейтингом. Такое решение на Python обрабатывает второй файл всего несколько секунд, но большая часть этого времени тратится на считывание 30 МБ файла данных.
Python
f = open("27-169b.txt")
n, k = map(int, f.readline().split())
MX = 11168
r = [0] * (MX + 1)
for i in f:
r[int(i)] += 1
rs = [0] * (MX + 1)
rs[MX] = r[MX]
for i in range(MX - 1, k - MX - 1, -1):
rs[i] = r[i] + rs[i + 1]
count = 0
for i in range(k - MX, MX + 1):
z = k - i
if z > i:
count += r[i] * rs[z]
elif i != MX:
count += r[i] * (r[i] - 1) // 2 + r[i] * rs[i + 1]
else:
count += r[i] * (r[i] - 1) // 2
print(count)
PascalABC
const
MX = 11168;
var
n, k, i, z: Integer;
count: Int64;
r, rs: array [100..MX] of Integer;
f: TEXT;
begin
Assign(f, '27-169b.txt');
Reset(f);
Readln(f, n, k);
for i := 100 to MX do
r[i] := 0;
for i := 1 to n do
begin
Readln(f, z);
r[z] := r[z] + 1;
end;
rs[MX] := r[MX];
for i := MX - 1 downto k - MX do
rs[i] := r[i] + rs[i + 1];
count := 0;
for i := k - MX to MX do
begin
z := k - i;
if z > i then
count := count + r[i] * rs[z]
else if i <> MX then
count := count + r[i] * (r[i] - 1) div 2 + r[i] * rs[i + 1]
else
count := count + r[i] * (r[i] - 1) div 2;
end;
Writeln(count);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("27-169b.txt");
int n, k;
f >> n >> k;
const int MX = 11168;
int r[MX + 1];
for (int i = 0; i <= MX; i++)
r[i] = 0;
for (int i = 0; i < n; i++)
{
int x;
f >> x;
r[x]++;
}
int rs[MX + 1];
rs[MX] = r[MX];
for (int i = MX - 1; i >= k - MX; i--)
rs[i] = r[i] + rs[i + 1];
long long count = 0;
for (int i = k - MX; i <= MX; i++)
{
int z = k - i;
if (z > i)
count += r[i] * rs[z];
else if (i != MX)
count += r[i] * (r[i] - 1) / 2 + r[i] * rs[i + 1];
else
count += r[i] * (r[i] - 1) / 2;
}
cout << count << endl;
}
Ответ
43666 1303810249487