Матч 334, Скидка в супермаркете (SupermarketDiscount)

Дивизион 2, Уровень 1

Три девочки пришли в супермаркет. На кассе они увидели рекламу: “Купите товара на 50$ и получите скидку в 10$”. Девочки поняли, что иногда выгодно объединить их покупки, нежели платить отдельно. Например, если суммы их покупок составляют соответственно 46$, 62$ и 9$, то объединив товары в две покупки за 55$ и 62$, они получат скидку в 20$.

Массив goods содержит стоимости покупок трех девочек. Необходимо определить наименьшую сумму, которой они могут рассчитаться за товар.

Класс: SupermarketDiscount

Метод: int minAmount(vector<int> goods)

Ограничения: goods содержит в точности 3 числа от 1 до 99.

Вход. Массив goods из 3 натуральных чисел.

Выход. Наименьшая сумма, которую могут заплатить девочки за приобретаемый товар, кооперируясь между собой при его оплате.

Пример входа

goods

{46, 62, 9}

{50, 62, 93}

{5, 3, 15}

Пример выхода

97

175

23

РЕШЕНИЕ

полный перебор

Функция disc возвращает стоимость товара со скидкой. Кооперироваться при оплате девочки могут одним из следующих образов:

1. За весь товар платит одна девочка.

2. Двое девочек объединяют товар в одну покупку, а третья платит за себя.

3. Все три девочки платят отдельно.

Перебрав все описанные варианты и посчитав сумму оплаты, возвращаем вариант с наименьшей суммой.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

int disc(int n)

{

return (n >= 50) ? n - 10 : n;

}

class SupermarketDiscount

{

public:

int minAmount(vector<int> goods)

{

int res = disc(goods[0]) + disc(goods[1]) + disc(goods[2]);

res = min(res,disc(goods[0] + goods[1]) + disc(goods[2]));

res = min(res,disc(goods[0] + goods[2]) + disc(goods[1]));

res = min(res,disc(goods[1] + goods[2]) + disc(goods[0]));

res = min(res,disc(goods[0] + goods[1] + goods[2]));

return res;

}

};