Что спрашивают
Из круглых коржей собирают башню. Каждый следующий корж должен быть меньше предыдущего хотя бы на 8 единиц. Нужно найти максимальное количество ярусов, затем максимально возможный диаметр верхнего, самого маленького коржа.
На входе N ≤ 10 000 и N диаметров от 1 до 10 000. Повторы допустимы; один корж можно использовать только один раз.
Приём решения
Отсортируйте диаметры по убыванию. Возьмите самый большой корж, затем каждый раз берите первый, который не больше предыдущего выбранного минус 8.
Жадный выбор безопасен: если вместо выбранного коржа поставить меньший на том же уровне, допустимых продолжений сверху больше не станет. Больший корж оставляет как минимум столько же места для каждого следующего. По индукции диаметр на каждом уровне жадной башни не меньше диаметра соответствующего уровня любой другой башни.
Отсюда следуют оба ответа. Если существует башня из k ярусов, жадная тоже сможет построить хотя бы k. Среди башен максимальной высоты её последний диаметр будет наибольшим. Начать с самого большого также безопасно: он может заменить любое основание.
Равенство разности восьми допускается. Время сортировки O(N log N), проход O(N), память O(N). В коде None означает, что пока не выбран ни один корж.
Разбор на примере
Ввод
6 44 59 27 51 35 43
Вывод
5 27
| Диаметр | Разность с выбранным | Действие |
|---|---|---|
| 59 | Основание | Берём |
| 51 | 8 | Берём |
| 44 | 7 | Пропускаем |
| 43 | 8 | Берём |
| 35 | 8 | Берём |
| 27 | 8 | Берём |
Из диаметров 59, 51, 44, 43, 35, 27 выбираем 59 и 51. Корж 44 не подходит: разность только 7. Следующий 43 подходит, затем берём 35 и 27. Получается пять ярусов; каждый переход даёт разность ровно 8.
Код на Python и C++
N натуральное, поэтому хотя бы один корж будет выбран. Ответом служит диаметр последнего выбранного, а не последнего просмотренного коржа.
В C++ вместо None — значение -1: диаметр не бывает отрицательным. Сортировка по убыванию — sort(diameters.begin(), diameters.end(), greater<int>()).
import sys
def solve(diameters):
count = 0
last = None
for diameter in sorted(diameters, reverse=True):
if last is None or last - diameter >= 8:
count += 1
last = diameter
return count, last
if __name__ == '__main__':
n, *diameters = map(int, sys.stdin.buffer.read().split())
print(*solve(diameters))
<algorithm>
<functional>
<iostream>
<vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> diameters(n);
for (int& diameter : diameters)
cin >> diameter;
sort(diameters.begin(), diameters.end(), greater<int>());
int count = 0, last = -1;
for (int diameter : diameters) {
if (last == -1 || last - diameter >= 8) {
count += 1;
last = diameter;
}
}
cout << count << ' ' << last << endl;
}
Типичные ошибки
- Начать с самого маленького
Если строить башню сверху — от самого маленького коржа, каждый раз беря наименьший из подходящих больших, — ярусов получится максимум, но верхним окажется самый маленький корж из всех. А второй критерий требует, чтобы верхний был как можно больше. Поэтому строят снизу, от самого большого.
- Брать самый маленький подходящий
Следующий корж должен быть меньше хотя бы на 8, но брать самый маленький из подходящих нельзя: он может укоротить башню. Из 20, 12, 10, 4 так получится 20 → 4, два яруса, а 20 → 12 → 4 даёт три. Берите самый большой из подходящих.
- Потребовать разность больше восьми
Коржи с разностью ровно 8 совместимы. Проверяется нестрогое неравенство.
- Сравнивать с предыдущим в списке
Пропущенные диаметры не входят в башню. Разность нужна с последним выбранным коржом.