В массиве A хранятся цены на N предметов. Есть K купонов, которые уменьшают цену предмета на X. Если применить t купонов на предмет с ценой a, то его итоговая стоимость будет max(a - t*X, 0) (то есть купоны не могут сделать цену предмета отрицательной. Необходимо вернуть минимальное количество денег, которое придется потратить, чтобы купить все предметы. A = 8, 3, 10, 5, 13 K = 4 X = 7 result=12 --- Вам дан массив a, состоящий из n положительных целых чисел. Существуют ли три различных индекса i, j, k таких, что сумма a[i]+a[j]+a[k] заканчивается цифрой m? Например, для m = 3 solve([20, 22, 19, 84]) = > true // 20 + 84 + 19 = 123 solve([1,2,3]) => false

Задача состоит из двух частей, решим их по очереди.

---

Часть 1: Минимальная сумма с купонами

Дано: массив цен A, количество купонов K, каждый купон уменьшает цену на X.

Идея решения:

• Чтобы минимизировать итоговую сумму, нужно максимально использовать купоны на самые дорогие предметы.
• Сортируем массив цен по убыванию.
• Распределяем купоны начиная с самого дорогого предмета, применяя максимально возможное количество купонов (до тех пор, пока цена не станет 0 или не закончатся купоны).

Пример на C#:

int MinCost(int[] A, int K, int X) {
    Array.Sort(A);
    Array.Reverse(A);
    int totalCost = 0;
    foreach (var price in A) {
        int couponsToUse = Math.Min(K, price / X);
        K -= couponsToUse;
        int finalPrice = price - couponsToUse * X;
        totalCost += finalPrice;
    }
    return totalCost;
}

// Для A = [8,3,10,5,13], K=4, X=7
// Результат будет 12

---

Часть 2: Проверка существования трех индексов i,j,k, сумма которых заканчивается на m

Идея:

• Рассмотрим остатки элементов массива по модулю 10 (т.к. нас интересует последняя цифра суммы).
• Переберем все тройки остатков и проверим, есть ли в массиве соответствующие элементы.

Пример на C#:

bool Solve(int[] a, int m) {
    int n = a.Length;
    int[] modCount = new int[10];
    foreach (var val in a) modCount[val % 10]++;

    for (int i = 0; i < 10; i++) {
        for (int j = i; j < 10; j++) {
            for (int k = j; k < 10; k++) {
                if ((i + j + k) % 10 == m) {
                    // Проверяем, достаточно ли элементов для выбора трех разных индексов
                    int needed = 1;
                    if (i == j) needed++;
                    if (j == k) needed++;
                    if (i == k) needed++;
                    
                    int count = 0;
                    count += modCount[i];
                    if (j != i) count += modCount[j];
                    if (k != i && k != j) count += modCount[k];

                    // Более точная проверка количества элементов для уникальных индексов
                    int totalNeeded = 3;
                    int[] counts = new int[10];
                    counts[i]++; counts[j]++; counts[k]++;
                    bool enough = true;
                    for (int x = 0; x < 10; x++) {
                        if (counts[x] > modCount[x]) {
                            enough = false;
                            break;
                        }
                    }
                    if (enough) return true;
                }
            }
        }
    }
    return false;
}

Пример:

• solve([20, 22, 19, 84], 3) => true (20+84+19=123)
• solve([1,2,3], 3) => false