В лесничестве саженцы сосны высадили параллельными рядами, которые
Условие
В лесничестве саженцы сосны высадили параллельными рядами, которые пронумерованы идущими подряд натуральными числами. Растения в каждом ряду пронумерованы натуральными числами начиная с единицы.
По данным аэрофотосъёмки известно, в каких рядах и на каких местах растения не прижились. Найдите ряд с наибольшим номером, в котором есть ровно 13 идущих подряд свободных мест для посадки новых сосен, таких, что непосредственно слева и справа от них в том же ряду растут сосны. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: наибольший номер ряда и наименьший номер места для посадки из числа найденных в этом ряду подходящих последовательностей из 13 свободных мест.
Входные данные.26.txtВ первой строке входного файла находится число N — количество прижившихся саженцев сосны (натуральное число, не превышающее 20 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100 000: номер ряда и номер места в этом ряду, на котором растёт деревце.
Выходные данныеДва целых неотрицательных числа: наибольший номер ряда и наименьший номер места в выбранной последовательности из 13 мест, подходящих для посадки новых сосен.
Типовой пример организации входных данных:740 340 760 3350 12550 12950 6850 72Для приведённого примера, при условии, что необходимо 3 свободных места, ответом является пара чисел: 50; 69.Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов. Ответ:
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Как рассуждать
Считаем все пары в двумерный массив, где первое число — номер ряда, второе — номер места. Номер места считаем как отрицательное значение, чтобы при сортировке места с меньшим номером (по данным из файла) были больше (в данных). Это существенно сократит поиск нужного места.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
Осталось ещё 1 шаг
Примечание. Путь к файлу необходимо указать…
Бесплатно · займёт минуту