Question

У Арсения есть n зверьков. Каждый из них обладает характером, поэтому, если в клетке, где находится i-й зверек, есть не больше ci зверьков, то его агрессивность будет ai, а если больше, то его агрессивность будет bi (ai≤bi). Также у Арсения есть клетка прочностью s, которая выдержит зверьков, суммарная агрессивность которых не больше s. Помогите Арсению выяснить, какое наибольшее число зверьков он может хранить в клетке одновременно. Входные данные В первой строке через пробел заданы два целых числа n и s (1≤n≤105,0≤s≤109). В следующих n строках задана характеристика животных числами ai, bi и ci (0≤ai≤bi≤109,1≤ci≤n). Выходные данные Выведите единственное число — наибольшее количество животных, которое Арсений может одновременно хранить в клетке. Примеры входные данные 2 6 2 4 1 2 4 2 выходные данные 2 входные данные 4 10 3 4 2 3 5 3 1 1 1 2 7 3 выходные данные 3

Answer 1

Код

• #include <iostream>
• #include <utility>
• #include <numeric>
• #include <vector>
• class Beast {
•    int trigger;
•    double aggression;
•    double rage_aggression;
• public:
•    Beast() = default;
•    Beast(int trigger, double aggression, double range_aggression)
•    : trigger(trigger), aggression(aggression), rage_aggression(range_aggression)
•    { }
•    Beast(const Beast&) = default;
•    Beast(Beast&&) = default;
•    Beast& operator=(const Beast&) = default;
•    Beast& operator=(Beast&&) = default;
•    [[nodiscard]] double calculate_aggression(unsigned long amount) const {
•        return amount > trigger ? rage_aggression : aggression;
•    }
•    void ReadFrom (std::istream& is) {
•        is >> aggression >> rage_aggression >> trigger;
•    }
•    void WriteTo(std::ostream &os) const {
•        os << aggression << " " << rage_aggression << " " << trigger;
•    }
• };
• std::istream& operator >>(std::istream &is, Beast &cls) {
•    cls.ReadFrom(is);
•    return is;
• }
• std::ostream& operator <<(std::ostream &os, const Beast &cls) {
•    cls.WriteTo(os);
•    return os;
• }
• class Cage {
•    double durability;
•    std::vector<Beast> container;
• public:
•    explicit Cage(double durability, std::vector<Beast> container)
•    : durability(durability), container(std::move(container))
•    { }
•    Cage(const Cage&) = default;
•    Cage(Cage&&) = default;
•    Cage& operator=(const Cage&) = default;
•    Cage& operator=(Cage&&) = default;
•    [[nodiscard]] double calculate_aggressive() const {
•        auto amount = container.size();
•        if (amount == 0) return 0;
•        return std::accumulate(container.begin(), container.end(), 0.0,
•        [amount](double total_aggressive, const Beast & beast){
•            return total_aggressive + beast.calculate_aggression(amount);
•        });
•    }
•    [[nodiscard]] bool is_it_normal() const {
•        auto aggressive = calculate_aggressive();
•        return aggressive <= durability;
•    }
•    [[nodiscard]] int get_capacity() const {
•        return container.size();
•    }
•    [[nodiscard]] double get_durability() const {
•        return durability;
•    }
• };
• template <typename T>
• void subsetsUtil(std::vector<T>& A, std::vector<std::vector<T> >& res,
•                 std::vector<T>& subset, int index)
• {
•    res.push_back(subset);
•    for (int i = index; i < A.size(); i++) {
•        // include the A[i] in subset.
•        subset.push_back(A[i]);
•        // move onto the next element.
•        subsetsUtil(A, res, subset, i + 1);
•        // exclude the A[i] from subset and triggers
•        // backtracking.
•        subset.pop_back();
•    }
• }
• template <typename T>
• std::vector<std::vector<T>> P(std::vector<T>& A)
• {
•    std::vector<T> subset;
•    std::vector<std::vector<T>> res;
•    int index = 0;
•    subsetsUtil(A, res, subset, index);
•    return res;
• }
• int main () {
•    int n, s;
•    Beast noname{};
•    std::vector<Beast> set_of_beasts;
•    std::cin >> n >> s;
•    for (auto i = 0; i < n; ++i) {
•        std::cin >> noname;
•        set_of_beasts.push_back(noname);
•    }
•    auto selections = P(set_of_beasts);
•    std::vector<Cage> variants;
•    std::transform(selections.begin(), selections.end(), std::back_inserter(variants), [s](std::vector<Beast> &selection){
•        return Cage(s, selection);
•    });
•    std::vector<Cage> true_variants;
•    std::copy_if(variants.begin(), variants.end(), std::back_inserter(true_variants), [](Cage& x) {return x.is_it_normal();});
•    auto the_best_of_the_best_variant = *std::max_element(true_variants.begin(), true_variants.end(), [](Cage & s1, Cage & s2){
•        return s1.get_capacity() < s2.get_capacity();
•    });
•    std::cout << the_best_of_the_best_variant.get_capacity();
•    return 0;
• }

Answer 2

Для решения данной задачи можно воспользоваться жадным методом. Основная идея заключается в том, чтобы сначала отсортировать зверьков по возрастанию значения a (агрессивность при малом количестве зверьков), а затем добавлять их по порядку в клетку, пока суммарная агрессивность не превысит предел s.

Вот алгоритм:

1. Считываем входные данные: количество зверьков n, прочность клетки s, и характеристики каждого зверька (ai, bi, ci).

2. Создаем список зверьков, каждый элемент которого будет содержать информацию о зверьке: ai, bi, ci.

3. Сортируем список зверьков по возрастанию ai.

4. Инициализируем переменную, обозначающую текущую суммарную агрессивность.

5. Инициализируем переменную, обозначающую количество зверьков в клетке.

6. Проходим по списку зверьков и для каждого зверька:

   a. Если текущая суммарная агрессивность плюс ai зверька не превышает прочность s, то добавляем его в клетку и увеличиваем текущую суммарную агрессивность на ai.

   b. Иначе, если суммарная агрессивность плюс bi зверька не превышает прочность s, то добавляем его в клетку и увеличиваем текущую суммарную агрессивность на bi.

   c. Иначе заканчиваем добавление зверьков в клетку.

7. Выводим количество зверьков, которые были добавлены в клетку.

Вот реализация данного алгоритма на Python:

pythonCopy code
n, s = map(int, input().split())
beasts = []

for _ in range(n):
    a, b, c = map(int, input().split())
    beasts.append((a, b, c))

beasts.sort()

total_aggressiveness = 0
count = 0

for a, b, c in beasts:
    if total_aggressiveness + a <= s:
        total_aggressiveness += a
        count += 1
    elif total_aggressiveness + b <= s:
        total_aggressiveness += b
        count += 1
    else:
        break

print(count)

Примеры, которые вы предоставили, можно использовать для проверки правильности работы алгоритма.