Нужен алгоритм решения

[Алекс77]

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

Дано разложение числа с на простые множители.
$c={\alpha_1}^b \alpha_2 ... \alpha_n$

Если первый множитель в разложении равен 2, то b=3, в противном случае b=1.

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

Просьба перебор не предлагать.

[Dandan]

выложите ограничения на числа $n$ и $a_n$. В задачах по программированию это важно.
Но вообще жадный алгоритм по идее должен подойти.

[Алекс77]

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

Я думаю о решении этой задачи посредством преобразования ее в задачу о ранце посредством назначения каждому множителю стоимости 1 и назначением целой части квадратного корня из с: $\sqrt c$ в качестве ограничения.
Но в этом случае при n > 10 уже могу вылететь за временные ограничения.

[Dandan]

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

[Алекс77]

Не думаю, что жадный алгоритм здесь приемлем.
К тому же вопрос с произвольным разбиением на множества приводит к необходимости перебора, а это уже $2^{n-1}$ вариантов.
Просто приведу 2 примера:
{3,5,7,11} -> {3,11} и {5,7}
{3,5,7,109} -> {3,5,7} и {109}

[maxal]

Другими словами нужно представить $c$ в виде произведения двух сомножителей с минимальной разностью.
Если эта разность небольшая - то можно организовать перебор ее значений. Дело в том, что если $c=xy$, то $4c=(x+y)^2-(x-y)^2.$ Таким образом, задача эквивалентна поиску такого минимального натурального числа $d$, что $4c+d^2$ является полным квадратом.

[VAL]

Алекс77 писал(а):

Не думаю, что жадный алгоритм здесь приемлем.
К тому же вопрос с произвольным разбиением на множества приводит к необходимости перебора, а это уже $2^{n-1}$ вариантов.
Просто приведу 2 примера:
{3,5,7,11} -> {3,11} и {5,7}
{3,5,7,109} -> {3,5,7} и {109}

Пусть $a_i$ упорядочены по возрастанию.
Предлагаю сначала найти величину $\frac{\sqrt{a_1^ba_2\dots a_n}}{a_n}$, а затем приближаться к ней, перемножая остальные $a_i$, начиная с самого большого, поиском в глубину.

PS: Удивительные совпадения бывают.
Сегодня вел кружок у школьников (по математике, а не по информатике) и просто так, из головы предложил им такую задачку: разбить цифры от 1 до 9 на две группы так, чтобы произведения чисел в группах отличались на минимально возможную величину.

[Алекс77]

maxal писал(а):

Другими словами нужно представить $c$ в виде произведения двух сомножителей с минимальной разностью.
Если эта разность небольшая - то можно организовать перебор ее значений. Дело в том, что если $c=xy$, то $4c=(x+y)^2-(x-y)^2.$ Таким образом, задача эквивалентна поиску такого минимального натурального числа $d$, что $4c+d^2$ является полным квадратом.

Спасибо maxal, очень интересное наблюдение.
А есть какие-нибудь математические выкладки на тему ускорения поиска числа d?
Просто при n>10 уже вроде за 1 миллион произведение перескакивает даже при минимальных множителях, а там квадраты перебирать может долго получиться...

[worm2]

maxal писал(а):

Таким образом, задача эквивалентна поиску такого минимального натурального числа $d$, что $4c+d^2$ является полным квадратом.

Гениально! Но тогда эффективнее искать такое натуральное $f$, что $\left(\lfloor2\sqrt{c}\rfloor+f\right)^2-4c$ является полным квадратом.
По крайней мере, применительно к задаче VAL этот способ находит решение уже при $f=2$, тогда как $d=54$.

[VAL]

maxal писал(а):

Другими словами нужно представить $c$ в виде произведения двух сомножителей с минимальной разностью.
Если эта разность небольшая - то можно организовать перебор ее значений. Дело в том, что если $c=xy$, то $4c=(x+y)^2-(x-y)^2.$ Таким образом, задача эквивалентна поиску такого минимального натурального числа $d$, что $4c+d^2$ является полным квадратом.

Идеи Ферма живут и побеждают? Симпатично!

Однако при малых n (или большом различии между $a_i$) моим способом быстрее получается.
Впрочем, при малых n не сложно и вручную решить

[Алекс77]

VAL писал(а):

Однако при малых n (или большом различии между $a_i$) моим способом быстрее получается.
Впрочем, при малых n не сложно и вручную решить

Одна просьба, можно чуть-чуть поподробней описать алгоритм, скажем так, для чайника?

Заранее спасибо!

[VAL]

Алекс77 писал(а):

VAL писал(а):

Однако при малых n (или большом различии между $a_i$) моим способом быстрее получается.
Впрочем, при малых n не сложно и вручную решить

Одна просьба, можно чуть-чуть поподробней описать алгоритм, скажем так, для чайника?

А зачем?
Насчет того, что моим методом будет считаться быстрее, чем у maxalа, я шутил.
Впрочем, мне не жалко. Вот код на Maple (на другом в последнее время не пишу )

 mindiff := proc(L)
local n, m, p, pr, s, i, j, c, st, St;
    n := nops(L);
    pr := mul(L[j], j = 1 .. n);
    c := evalf(sqrt(pr));
    m := pr;
    St := [[L[1], 2]];
    do
        st := St[-1];
        s := st[1];
        i := st[2];
        if c < s or n < i then
            if abs(s - c) < m then m := abs(s - c); p := s
            end if;
            St := [St[j] $ (j = 1 .. nops(St) - 1)];
            if St = [] then break end if;
            St[-1][2] := St[-1][2] + 1;
            s := St[-1][1];
            if c - s < m then m := c - s; p := s end if
        else St := [op(St), [s*L[i], i + 1]]
        end if
    end do;
    [pr/p, p]
end proc

А вот пример обращения (восьмерка, пркедставляется в виде произведения четверки и двойки):

mindiff([37,17,11,7,5,4,3,2]);
                             [2380, 2442]

[Алекс77]

Огромное спасибо всем - очень помогли,
Владимиру - особенные респекты!