РЕШУ ЕГЭ — информатика

Задания

В лесничестве саженцы сосны высадили параллельными рядами, которые пронумерованы идущими подряд натуральными числами. Растения в каждом ряду пронумерованы натуральными числами начиная с единицы.

По данным аэрофотосъёмки известно, в каких рядах и на каких местах растения не прижились. Найдите ряд с наибольшим номером, в котором есть ровно 13 идущих подряд свободных мест для посадки новых сосен, таких, что непосредственно слева и справа от них в том же ряду растут сосны. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: наибольший номер ряда и наименьший номер места для посадки из числа найденных в этом ряду подходящих последовательностей из 13 свободных мест.

Входные данные.

26.txt

В первой строке входного файла находится число N  — количество прижившихся саженцев сосны (натуральное число, не превышающее 20 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100 000: номер ряда и номер места в этом ряду, на котором растёт деревце.

Выходные данные

Два целых неотрицательных числа: наибольший номер ряда и наименьший номер места в выбранной последовательности из 13 мест, подходящих для посадки новых сосен.

Типовой пример организации входных данных:

40 3

40 7

60 33

50 125

50 129

50 68

50 72

Для приведённого примера, при условии, что необходимо 3 свободных места, ответом является пара чисел: 50; 69.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Ответ:

Решение. 1.  Считаем все пары в двумерный массив, где первое число  — номер ряда, второе  — номер места. Номер места считаем как отрицательное значение, чтобы при сортировке места с меньшим номером (по данным из файла) были больше (в данных). Это существенно сократит поиск нужного места.

2.  Отсортируем массив.

3.  Найдем последний элемент в отсортированном массиве, который удовлетворяет условиям:

a)  два занятых места находятся в одном ряду;

b)  разница между проверяемым местом и предыдущим равна 14.

Так как надо определить минимальный номер свободного места, добавим к номеру найденного места 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)

№ п/п	№ задания	Ответ
1	45260	59966 50449

Ключ