3839. Продуктовый магазин

Кассир продуктового магазина, как оказалось, не умеет различать символы умножения и сложения. Для облегчения процесса оплаты, Вы хотите купить товары таким образом, чтобы произведение их цен равнялось их сумме.

Конечно, если Вы купите только один товар, то условие всегда верно. Покупка двух или трех товаров является довольно скучным занятием для Вас. Поэтому Вы заинтересовались в поиске возможных цен из четырех товаров таких, что сумма четырех цен равна их произведению. Цены следует рассматривать в € с двумя знаками после запятой. Отметим, что каждое изделие стоит по крайней мере один цент.

Вход. Содержит одно действительное число с двумя десятичными знаками – сумму S (5 ≤ S ≤ 25).

Выход. Вывести все решения, в которых сумма четырех изделий не более S €. Для каждого решения выведите в отдельной строке цены четырех изделий в неубывающем порядке, разделяя их одним пробелом. Решения следует выводить по возрастанию стоимости первого изделия. Если у нескольких решений стоимость первого изделия одинакова, то следует выводить их по возрастанию стоимости второго изделия. В случае равенства стоимости первого и второго изделий, следует выводить решения по возрастанию стоимости третьего изделия. Каждое решение следует выводить только один раз.

Пример входа	Пример выхода
6.7	1.00 1.75 1.90 2.00 1.10 1.50 2.00 2.00 1.25 1.25 1.92 2.21 1.25 1.40 1.86 2.00 1.25 1.60 1.75 1.84

РЕШЕНИЕ

перебор

Анализ алгоритма

Пусть a’, b’, c’, d’ – стоимости четырех изделий. Тогда необходимо найти все такие четверки (a’, b’, c’, d’), для которых a’ ≤ b’ ≤ c’ ≤ d’, a’ + b’ + c’ + d’ = a’ * b’ * c’ * d’, а также a’ + b’ + c’ + d’ ≤ S. Для избежания ошибок при работе с действительными числами, переведем исходную сумму S в копейки. Положим a = a’ * 100, b = b’ * 100, c = c’ * 100, d = d’ * 100. Соотношение a’ + b’ + c’ + d’ = a’ * b’ * c’ * d’ примет вид:

a / 100 + b / 100 + c / 100 + d / 100 = (a / 100) * (b / 100) * (c / 100) * (d / 100)

или то же самое что

100³ (a + b + c + d) = a * b * c * d

Остается перебрать значения a, b, c, d вплоть до копейки, для которых также выполняются соотношения a ≤ b ≤ c ≤ d и a + b + c + d ≤ 100 * S.

Реализация алгоритма

Читаем входную сумму ss. Переведем ее в копейки. Далее будем искать решения, в которых сумма четырех изделий не превышает maxPrice = 100 * ss копеек.

scanf("%lf",&ss); maxPrice = (int)(100*ss + 1e-7);

Поскольку a + b + c + d ≤ maxPrice, то a ≤ maxPrice / 4, b ≤ (maxPrice – a) / 3, c ≤ (maxPrice – a – b) / 2. Используем эти ограничения при переборе.

for (int a = 1; a <= maxPrice/4; a++)

for (int b = a; b <= (maxPrice - a) / 3; b++)

for (int c = b; c <= (maxPrice - a - b) / 2; c++)

{

Из соотношения 1000000 * (a + b + c + d) = a * b * c * d выразим d:

d = 1000000 * (a + b + c) / (a * b * c – 1000000)

Значение d должно быть неотрицательным и целым.

int s = 1000000 * (a + b + c), p = a * b * c - 1000000;

if (p <= 0 || s % p != 0) continue;

int d = s / p;

Должны выполняться соотношения c ≤ d и a + b + c + d ≤ maxPrice.

if (d < c || a + b + c + d > maxPrice) continue;

Выводим найденное решение – четверку (a’, b’, c’, d’) = (a / 100, b / 100, c / 100, d / 100).

printf("%.2f %.2f %.2f %.2f\n",a/100.0,b/100.0,c/100.0,d/100.0);

}