Что спрашивают

Известны координаты прижившихся сосен: номер ряда и номер места. Найдите ровно 13 подряд свободных мест, непосредственно слева и справа от которых растут сосны.

Выберите наибольший номер ряда, а в нём наименьшее начало такой группы. N ≤ 20 000, номера ≤ 100 000. Координаты различны, подходящий промежуток существует.

Приём решения

Отсортируйте пары (ряд, место). Занятые места одного ряда окажутся рядом, по возрастанию номера места. Рассматривать нужно соседние занятые места: между несоседними есть ещё дерево.

Между местами a и b ровно b - a - 1 свободных мест. Для 13 свободных нужна разность b - a == 14. Первое свободное место имеет номер a + 1. Пары из разных рядов пропускаются.

При каждом совпадении сравните ряд с лучшим. Больший ряд заменяет ответ, при равных рядах выбирается меньшее начало. Порядок критериев нельзя переставлять. При сортировке по возрастанию можно также обновлять ответ только при переходе к большему подходящему ряду.

Перебирать все возможные ряды и места не нужно: достаточно N известных деревьев. Время O(N log N), память O(N).

Разбор на примере

Ввод

7
10 16
9 30
7 19
9 2
10 1
9 16
7 5

Вывод

9 3
Разбор примера по шагам
РядСоседние деревьяСвободных / решение
75 и 1913; начало 6
92 и 1613; начало 3
916 и 3013; начало 17
101 и 1614; не подходит

В ряду 10 между 1 и 16 свободны 14 мест, поэтому он не подходит. В ряду 9 между 2 и 16 свободны места 3–15, а между 16 и 30 — 17–29. Выбираем начало 3. В ряду 7 тоже есть подходящий промежуток, но номер ряда меньше.

Код на Python и C++

По условию координаты различны, поэтому set не требуется. Соседство проверяется после сортировки, а не в исходном порядке строк.

В C++ пары (ряд, место) хранятся в vector<pair<int, int>>, и sort упорядочивает их так же: по ряду, затем по месту.

import sys


def solve(trees):
    trees = sorted(trees)
    best_row = best_start = 0
    for (row, a), (other_row, b) in zip(trees, trees[1:]):
        if row != other_row or b - a != 14:
            continue
        start = a + 1
        if row > best_row or row == best_row and start < best_start:
            best_row, best_start = row, start
    return best_row, best_start


if __name__ == '__main__':
    data = list(map(int, sys.stdin.buffer.read().split()))
    trees = list(zip(data[1::2], data[2::2]))
    print(*solve(trees))
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> trees(n);
    for (auto& [row, place] : trees)
        cin >> row >> place;
    sort(trees.begin(), trees.end());
    int best_row = 0, best_start = 0;
    for (int i = 0; i + 1 < n; i++) {
        auto [row, a] = trees[i];
        auto [other_row, b] = trees[i + 1];
        if (row != other_row || b - a != 14)
            continue;
        int start = a + 1;
        if (row > best_row || (row == best_row && start < best_start)) {
            best_row = row;
            best_start = start;
        }
    }
    cout << best_row << ' ' << best_start << endl;
}

Типичные ошибки

  • Проверить разность 13

    Деревья по краям заняты. Число свободных мест на единицу меньше разности их номеров.

  • Принять любой длинный промежуток

    Нужно ровно 13 свободных мест между деревьями. В группе из 14 мест нельзя выбрать 13 так, чтобы оба края непосредственно граничили с деревьями.

  • Сравнить координаты из разных рядов

    Последнее дерево одного ряда и первое следующего соседствуют в списке, но не образуют промежуток в лесничестве.