Тема 26. Обработка целочисленной информации с использованием сортировки

26.05 Поиск мест на поле (билеты, саженцы, матрицы)

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела обработка целочисленной информации с использованием сортировки
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#26693

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

Через какое-то время осуществляется аэросъемка, в результате которой определяется, какие саженцы прижились. Необходимо определить ряд с максимальным номером, в котором есть подряд ровно 7  неприжившихся саженцев, при условии, что справа и слева от них саженцы прижились. В ответе запишите сначала наибольший номер ряда, затем наименьший номер из неприжившихся мест.

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

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

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

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

Пример входного файла:

7

40 30

40 34

50 125

50 129

50 64

50 68

50 70

Ответ для примера (при поиске 3  подряд идущих неприжившихся саженцах): 50 65

Вложения к задаче
Показать ответ и решение

Решение 1 (Excel/LibreOffice)
Откроем текстовый документ. Запомним первое число и удалим его. Скопируем все числа в Excel. В разделе Главная      ⇒ Сортировка и фильтр ⇒ Настраиваемая сортировка делаем сортировку столбцов:

PIC

В ячейке D2  записываем формулу =ЕСЛИ(И(A2=A1;B2=B1+8);"НАШЁЛ";0) и растягиваем её на диапазоне [D2 : D10000]  . Наводим курсор на столбец D  , нажимаем на Главная ⇒ Сортировка и фильтр ⇒ Фильтр. Сортируем столбец D  по критерию "НАШЁЛ". Получаем единственный номер ряда — 1536  и наименьший номер неприжившегося саженца — 141− 7 = 134  .

Решение 2 (Python)

f = open(’Задание_26__o4nj__rs6l.txt’)
n = int(f.readline())

a = [] # список координат прижившихся саженцев
for i in range(n):
    x, y = [int(_) for _ in f.readline().split()] # считывание текущей строки
    a.append([x, y])
a.sort()

ans = [0, 0]

for i in range(n - 1): # проход по всем координатам прижившихся саженцев
    # если ряд двух рядом стоящих в списке саженцев совпадает и при этом между ними есть 7 свободных мест
    if a[i][0] == a[i + 1][0] and a[i][1] == a[i + 1][1] - 8:
        row = a[i][0] # вычисляем ряд
        place = a[i][1] + 1 # вычисляем минимальное свободное место между двумя саженцами
        if row > ans[0]:
            ans[0] = row
            ans[1] = place

print(*ans)

Ответ: 1536 134

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!