Что спрашивают
Известны координаты прижившихся сосен: номер ряда и номер места. Найдите ровно 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
| Ряд | Соседние деревья | Свободных / решение |
|---|---|---|
| 7 | 5 и 19 | 13; начало 6 |
| 9 | 2 и 16 | 13; начало 3 |
| 9 | 16 и 30 | 13; начало 17 |
| 10 | 1 и 16 | 14; не подходит |
В ряду 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))
<algorithm>
<iostream>
<utility>
<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 так, чтобы оба края непосредственно граничили с деревьями.
- Сравнить координаты из разных рядов
Последнее дерево одного ряда и первое следующего соседствуют в списке, но не образуют промежуток в лесничестве.