В лесничестве саженцы сосны высадили параллельными рядами, которые пронумерованы идущими подряд натуральными числами. Растения в каждом ряду пронумерованы натуральными числами начиная с единицы.
По данным аэрофотосъёмки известно, в каких рядах и на каких местах растения не прижились. Найдите ряд с наибольшим номером, в котором есть ровно
Входные данные.
В первой строке входного файла находится число N — количество прижившихся саженцев сосны (натуральное число,
Выходные данные
Два целых неотрицательных числа: наибольший номер ряда и наименьший номер места в выбранной последовательности
Типовой пример организации входных данных:
7
40 3
40 7
60 33
50 125
50 129
50 68
50 72
Для приведённого примера, при условии, что необходимо
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Ответ:
1. Считаем все пары в двумерный массив, где первое число — номер ряда, второе — номер места. Номер места считаем как отрицательное значение, чтобы при сортировке места с меньшим номером (по данным из файла) были больше (в данных). Это существенно сократит поиск нужного места.
2. Отсортируем массив.
3. Найдем последний элемент в отсортированном массиве, который удовлетворяет условиям:
a) два занятых места находятся в одном ряду;
b) разница между проверяемым местом и предыдущим
Так как надо определить минимальный номер свободного места, добавим к номеру найденного места 1 (соседнее справа от минимального значения в паре занятых).
Приведём решение на языке Pascal.
var f: text;
n, i, r, m, a, b: integer;
nums: array of array of integer;
begin
setlength(nums, 0);
assign(f, 'C:\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] = 14 then begin
r := nums[i, 0];
m := -nums[i, 1] + 1;
end;
print(r, m);
end.
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 59966 50449.
Ответ: 59966 50449.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём другое решение на языке Python.
f = open("107_26.txt")
n = int(f.readline())
nums = list()
for i in f:
a, b = i.split()
a = int(a)
b = int(b)
nums.append([a, -b])
nums.sort()
r = 0
m = 0
for i in range(1, n):
if nums[i][0] == nums[i - 1][0]:
if nums[i][1] - nums[i - 1][1] == 14:
r = nums[i][0]
m = -nums[i][1] + 1
print(r, m)
Приведём решение Фефелова Сергея на языке Python.
f = open("107_26.txt")
n = int(f.readline())
nums = sorted([int(i) for i in x.split()] for x in f)
rmax = 0
for i in range(1, n):
r,m = nums[i-1]
if r == nums[i][0] and nums[i][1] - m == 14:
if r > rmax: rmax, mmin = r, m
print(rmax, mmin+1)
Приведём решение Юрия Лысакова на языке Python.
f = open("107_26.txt")
f.readline()
a = []
for i in f:
b = i.split()
a.append([int(b[0]), -int(b[1])])
a.sort()
a = a[::-1]
for j in range(len(a)-1):
if a[j][0] == a[j+1][0] and (a[j][1] - a[j+1][1]) == 14:
print(a[j][0],1 - a[j][1])
break
Приведём решение Юрия Красильникова на языке Python.
a=sorted([tuple(map(int,s.split())) for s in open('107_26.txt')][1:])
p=[(a[i][0],a[i-1][1]) for i in range(1,len(a)) if a[i][0]==a[i-1][0] and a[i][1]-a[i-1][1]==14]
maxrow=max(x[0] for x in p)
place=min(x[1] for x in p if x[0]==maxrow)
print(maxrow,place+1)