Описание задачи
Дан массив цен участков. Нужно купить максимальное количество на бюджет A. Порядок не важен — можно покупать вразнобой.
Типы запросов
? A— простая покупка (сортируем цены, берём дешёвые)? A B C— покупка с прогрессивным налогом:- Первые C участков — по номиналу
- Участок C+1 стоит: Цена + 1×B
- Участок C+k стоит: Цена + k×B
Формат входных данных
> Prices:
price1 price2 price3 ...
> Query:
? budget [tax_increment tax_free_count]
Пример
Условие
Prices: 10 20 30 15 25
Query: ? 50
Count: 3
Сортируем: 10, 15, 20, 25, 30. Покупаем: 10+15+20=45 ≤ 50. Следующий (25) не влезает.
Query: ? 100 10 2
Count: 4
Первые 2 без налога: 10+15=25.
Участок 3: 20 + 1×10 = 30. Итого: 55.
Участок 4: 25 + 2×10 = 45. Итого: 100.
Участок 5: 30 + 3×10 = 60 → не влезает.
Ключевые моменты
- Жадный алгоритм: сортируем цены по возрастанию
- Учитываем налог: effective_price = base_price + max(0, i - C) × B
- Используйте
long long— большие числа!