Матч 431, Сумма и произведение (SumAndProduct)

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

Список неотрицательных чисел называется удовлетворительным, если их сумма равна s, а произведение p. Найти удовлетворительный список с наименьшим количеством элементов и вернуть его длину. Если такого списка не существует, вернуть -1.

Класс: SumAndProduct

Метод: int smallestSet(int s, int p)

Ограничения: 1 £ s, p £ 10⁹.

Вход. Два числа s и p.

Выход. Наименьшее количество элементов в удовлетворительном списке. Если такого списка не существует, вернуть -1.

Пример входа

s	p
10	10
5	100
100	1000000000

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

1

-1

9

РЕШЕНИЕ

математика

В задаче следует найти наименьшее n, для которого существуют такие x₁, x₂, …, x_n, что

Рассмотрим, какие значения может принимать произведение x₁ * x₂ * … * x_n для заданных n и s. Если n = 1, то решением будет x₁ = s = p. При n = 2 сумма x₁ + x₂ = s, произведение равно x₁ * x₂ = x₁ * (s – x₁). Рассмотрим, какие значения может принимать произведение. Решим уравнение x * (s – x) = p или x² – s * x + p = 0. Дискриминант уравнения равен D = s² – 4 * p. Уравнение имеет решение при D ³ 0 или p £ s² / 4 . Если p ³ 0, то решения

x_1,2 =

будут неотрицательными. Таким образом, с помощью двух действительных чисел, сумма которых равна s, можно получить любое произведение от 0 до s² / 4. При этом наибольше произведение s² / 4 можно получить при x₁ = x₂ = s / 2.

Лемма. Если сумма n чисел равна s, то их максимально произведение равно (s / n)ⁿ и достигается при x₁ = x₂ = … = x_n = s / n.

Если предположить противное, то найдется наименьшее m = x_i и наибольшее M = x_j среди этих чисел. Заменим m и M на числа (m + M) / 2 и (m + M) / 2. В таком случае произведение x₁ * x₂ * … * x_n увеличится.

Доказательство. Докажем неравенство . Имеем: , , что верно так как по предположению m и M не равны между собой.

Теорема. Если сумма n чисел равна s, то их произведение может принимать любое значение от 0 до (s / n)ⁿ.

Согласно лемме, наибольшее значение (s / n)ⁿ достигается при x₁ = x₂ = … = x_n = s / n. Осталось показать, что достигается и любое другое произведение p, 0 £ p £ (s / n)ⁿ. Доказательство проведем конструктивно.

Возьмем b = p / (s / n)^n-2. Очевидно, что 0 £ b £ (s / n)². Исходя из выше доказанного, существуют такие x₁ и x₂, что x₁ + x₂ = 2 * s / n, x₁ * x₂ = b £ (2 * s / n)² / 4 = (s / n)². Добавим значения x₃ = x₄ = … = x_n = s / n чтобы получить требуемые n чисел: x₁ + x₂ + … + x_n = 2 * s / n + (n – 2) * s / n = s, x₁ * x₂ * … * x_n = b * (s / n)^n-2 = p.

Таким образом, алгоритм решения задачи состоит в следующем:

1. Если s = p, то вернуть 1.

2. Последовательно перебираем n = 2, 3, …, s. Как только станет p £ (s / n)ⁿ, возвращаем n.

3. Если на втором шаге решение не найдено, то возвращаем -1.

Пример. Найти n = 5 чисел, сумма которых равна s = 10, а произведение p = 30.

Такие числа существуют, так как p ≤ (s / n)ⁿ = (10 / 5)⁵ = 32. Выберем такие x₁ и x₂, что x₁ + x₂ = 2 * s / n = 2 * 10 / 5 = 4, а их произведение равно b = p / (s / n)^n-2 = 30 / (10 / 5)³ = 30 / 8 = 15 / 4. Такие числа существуют согласно лемме. Выберем x₃ = x₄ = x₅ = s / n = 10 / 5 = 2. Указанные пять чисел и будут являться ответом.

ПРОГРАММА

#include <stdio.h>

#include <math.h>

class SumAndProduct

{

public:

int smallestSet(int s, int p)

{

int n;

if (s == p) return 1;

for(n = 2; n <= s; n++)

if (pow(1.0 * s / n, 1.0 * n) >= p) return n;

return -1;

}

};