Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий условию. В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.
Входные данные.
В первой строке входного файла находится одно число: N — количество занятых мест (натуральное число,
В ответе запишите два целых числа: сначала максимальный номер ряда, где нашлись обозначенные в задаче места и минимальный номер места.
Пример входного файла:
6
50 12
50 15
60 157
60 160
60 22
60 25
Для данного примера ответом будет являться пара
Ответ:
1. Считаем все пары в двумерный массив, где первое число — номер ряда, второе — номер места.
a. Номер места считаем как отрицательное значение, чтобы при сортировке места с меньшим номером (по данным из файла) были больше (в данных). Это существенно сократит поиск нужного места.
2. Отсортируем массив.
3. Найдем последний элемент в отсортированном массиве, который удовлетворяет условию.
a. Два занятых места находятся в одном ряду.
b. Разница между проверяемым местом и предыдущим
c. Так как надо определить минимальный номер свободного места, добавим к номеру найденного места 1 (соседнее справа от минимального значения в паре занятых).
| Паскаль |
|---|
var f: text; n, i, r, m, a, b: integer; nums: array of array of integer; begin setlength(nums, 0); assign(f, '26.txt'); reset(f); readln(f, n); loop n do begin readln(f, a, b); nums := nums + ||a, -b||; end; Sort(nums, (x, y) -> ((x[0] < y[0]) or (x[0] = y[0]) and (x[1] < y[1]))); r := 0; m := 0; for i := 1 to nums.Length – 1 do if nums[i, 0] = nums[i-1, 0] then if nums[i, 1] – nums[i-1, 1] = 3 then begin r := nums[i, 0]; m := -nums[i, 1] + 1; end; print(r, m); end. |
| Python |
f = open('26.txt’) n = int(f.readline()) nums = [] for _ in range(n): pair = list(map(int, f.readline().split())) pair[1] = -pair[1] nums += [pair] nums.sort() r, m = 0, 0 for i in range(1, len(nums)): if nums[i][0] == nums[i-1][0]: if nums[i][1] – nums[i-1][1] == 3: r = nums[i][0] m = -nums[i][1] + 1 print(r, m) |
| С++ |
#include <iostream> #include <algorithm> #include <fstream> #include <vector> using namespace std; int main(){ ifstream f("26.txt"); int n, a, b, r, m; f >> n; vector <vector <int>> nums; for(int i=1; i<=n; i++){ f >> a >> b; vector<int> temp = {a, -b}; nums.push_back(temp); } sort(nums.begin(), nums.end()); r = 0; m = 0; for(int i=1; i < nums.size(); i++) if(nums[i][0] == nums[i-1][0]) if(nums[i][1] - nums[i-1][1] == 3){ r = nums[i][0]; m = -nums[i][1] + 1; } cout << r << " " << m; } |
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 8631 7311.
Ответ: 8631 7311.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Юрия Красильникова на языке Python.
a = sorted([list(map(int,s.split())) for s in open('26.txt')][1:])
lefts = [a[i] for i in range(len(a) - 1) if a[i][0] == a[i+1][0] and a[i+1][1] - a[i][1] == 3]
lefts.sort(key = lambda x: (x[0],-x[1]))
print(lefts[-1][0],lefts[-1][1] + 1)

