полное математическое решение, за спам бан Шифрование представлено следующим образом: к порядковому
номеру
каждой
буквы
прибавлялось
значение
многочлена
f(x) = x5 + 2x4 + x3 + 5x2 – 44x + 37, вычисленное либо при x1, либо при x2,
либо при x3, либо при x4, где x1, x2 – корни уравнения x
2 +2x – 5 = 0, а x3,
x4 – корни уравнения x
2 + x + 7 = 0 Затем полученное число заменялось
соответствующей ему буквой. Известно, что каждому символу русского
алфавита (33 буквы) присвоен номер: А = 1, Б = 2,…, Я = 33, пробел = 34
Расшифруйте сообщение: С П С В Ё К Б Д Б Г Е Ф Ц

Вот тебе в паскале

program ryad_chisel;

var N, t:integer;

begin

read(N);

t:=(N*(N+1))div 2;

if t mod 2 =1 then writeln('IMPOSSIBLE')

else begin

     if N mod 2 =0 then begin

                        t:=N div 4;

                        repeat

                        write('+');

                        t:=t-1;

                        until t=0;

                        t:=N div 2;

                        repeat

                        write('-');

                        t:=t-1;

                        until t=0;

                        t:=N div 4;

                        repeat

                        write('+');

                        t:=t-1;

                        until t=0;

                        end

     else begin

          t:=((N+1) div 4)-1;

          repeat

          write('+');

          t:=t-1;

          until t=0;

          t:=((N-1) div 2)+1;

          repeat

          write('-');

          t:=t-1;

          until t=0;

          t:=(N+1) div 4;

          repeat

          write('+');

          t:=t-1;

          until t=0;

          end

     end    

end.

Алгоритм. Отсортируем массив за O(nlogn). Запустим цикл по всем k, в теле цикла будем искать индексы i <= j, такие, что A[i] + A[j] = -A[k]. Понятно, что этот поиск надо делать за O(n), чтобы общее время работы было квадратичным.

Искать будем с двух указателей. Рассмотрим кусок массива, в котором ищем ответ A[l..r] (первоначально l = 1, r = n). Посмотрим на A[l] + A[r]. Если эта сумма больше, чем нужно, уменьшим на 1 число r, если меньше - увеличим на 1 число l, если равно -A[k] - победа, выводим ответ (l, r, k). Будем повторять это в цикле, пока l не станет больше r.

Если после выполнения цикла по k искомая тройка так и не нашлась, пишем "нет".

Корректность. Пусть в какой-то момент A[l] + A[r] < -A[k]. Тогда, чтобы иметь возможность получить A[i] + A[j] = -A[k], надо сумму увеличить. A[l] оказалось настолько мало, что даже если прибавить к нему самое большое возможное число (а это как раз A[r] - массив-то отсортирован!), то всё равно получается слишком мало. Значит, A[l] в ответе не будет, и можно безбоязненно выкинуть его из рассмотрения. Аналогично будет и в случае, когда A[l] + A[r] > -A[k].
Осталось показать, что если такая тройка индексов существует, то наш алгоритм не выдаст неверный ответ "нет". Но это очевидно: если ответ (I, J, K), то уж при k = K алгоритм что-нибудь да найдёт.

Время работы. Внутренний цикл выдает ответ не более чем за линейное время: всякий раз размер массива уменьшается на 1, всего элементов в массиве n, а на каждом шаге тратится константное время; пусть время выполнения внутреннего цикла T'(n) < an. Тогда все n проходов внешнего цикла затратят время T1(n) <= n T'(n) < an^2.
Сортировку можно сделать за время T2(n) < b nlogn < bn^2
Общее время работы T(n) = T1(n) + T2(n) < an^2 + bn^2 = cn^2