En un array A se almacenan los precios de N artículos. Hay K cupones que reducen el precio de un artículo en X. Si se aplican t cupones a un artículo con precio a, su costo final será max(a - t*X, 0) (es decir, los cupones no pueden hacer que el precio de un artículo sea negativo. Es necesario devolver la cantidad mínima de dinero que se tendrá que gastar para comprar todos los artículos. A = 8, 3, 10, 5, 13 K = 4 X = 7 resultado=12 --- Se te da un array a, que consiste en n números enteros positivos. ¿Existen tres índices distintos i, j, k tales que la suma a[i]+a[j]+a[k] termina en el dígito m? Por ejemplo, para 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