Задача 7011. Источник: Поляков. Задание КИМ 26
(Л. Шастин) Во дворце спорта идёт активная продажа билетов на предстоящий баскетбольный матч. Имеется информация об уже распределенных между болельщиками местах. При этом точно известно, что первое и последнее место в каждом из рядов занято. Хорошим называется такое место, что слева и справа от него есть ровно по 5 свободных мест. Найдите ряд с наибольшим номером, в котором есть хотя бы одно хорошее место, а также общее количество хороших мест во всех рядах.
Входные данные представлены в файле 26-135.txt следующим образом. В первой строке входного файла находится число N – количество занятых мест (натуральное число, не превышающее 100 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000: номер ряда и номер занятого места.
Запишите в ответе два целых неотрицательных числа: наибольший номер ряда, в котором есть хотя бы одно хорошее место, и общее количество хороших мест.
Пример входного файла:
11
5 1
20 30
5 7
20 18
5 30
20 1
20 4
20 16
5 13
20 10
20 24
Для данного примера подходит ряд 5, в котором слева и справа от 7 места есть ровно по 5 свободных мест, и ряд 20, в котором подходят 10-е и 24-е места. В ответ пойдёт ряд с наибольшим номером, содержащий хорошие места, и общее количество хороших мест. Ответ: 20 3.
Решение
Считываем данные в список/массив и сортируем по обоим полям в порядке возрастания. Анализируем элементы от второго до предпоследнего. Если номер ряда элемента совпадает с соседними, а разница номеров мест с соседними равна 6, то увеличиваем счетчик хороших мест и обновляем значение максимального ряда, где такое место нашлось.
Python
f = open('26-135.txt')
n = int(f.readline())
a = [[int(y) for y in x.split()] for x in f]
a.sort()
mx = 0
k = 0
for i in range(1, n - 1):
if (a[i - 1][0] == a[i][0] and a[i][0] == a[i + 1][0] and
a[i][1] - a[i - 1][1] == 6 and a[i + 1][1] - a[i][1] == 6):
k += 1
mx = a[i][0]
print(mx, k)
PascalABC
var
n, k, max, min, i, j, t: Integer;
a: array [1..100000, 1..2] of Integer;
f: TEXT;
begin
Assign(f, '26-135.txt');
Reset(f);
Readln(f, n);
for i := 1 to n do
Readln(f, a[i, 1], a[i, 2]);
for i := 1 to n - 1 do
begin
min := i;
for j := i + 1 to n do
if (a[j, 1] < a[min, 1]) or (a[j, 1] = a[min, 1]) and (a[j, 2] < a[min, 2]) 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;
end;
end;
for i := 2 to n - 1 do
if (a[i - 1, 1] = a[i, 1]) and (a[i, 1] = a[i + 1, 1]) and
(a[i, 2] - a[i - 1, 2] = 6) and (a[i + 1, 2] - a[i, 2] = 6) then
begin
k := k + 1;
max := a[i, 1];
end;
Writeln(max, ' ', k);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-135.txt");
int n;
f >> n;
int a[100000][2];
for (int i = 0; i < n; i++)
f >> a[i][0] >> a[i][1];
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] || a[j][0] == a[min][0] && a[j][1] < a[min][1])
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;
}
}
int k = 0, max = 0;
for (int i = 1; i < n - 1; i++)
if (a[i - 1][0] == a[i][0] && a[i][0] == a[i + 1][0] &&
a[i][1] - a[i - 1][1] == 6 && a[i + 1][1] - a[i][1] == 6)
{
k++;
max = a[i][0];
}
cout << max << " " << k << endl;
}
Ответ
4896 17