yourdomain.com

Допустим у нас есть массив A[1..n] (n=0..x+1). Каждый элемент такого массива может принимать любое значение в диапазоне от 0..х. Элементы в массиве цыклические, например если х=9, то 7+5=12 mod 10=2. Извесна сумма всех элементов массива S, которая зависима от самих элементов в массиве и может принимать значения от 0 до n*x. DeltaS это разница между значениями S и n*x/2 взятая по модулю:
DeltaS=|S-n*x/2|,
т.e. расстояние между текущей суммой и полвины максимальной суммы.

Так вот, вопрос такой:
Возможно ли уменьшить или увеличить сумму элементов так, чтобы новая сумма была максимально отдалена от половины максимальной суммы? T.e. найти максимальную DeltaS. Ho при условии, что элементы массива должны быть востановлены на прежние величины. При этом не хранить "карту" изменяемых элементов. Разрешается использовать только 1 или 2 числа не превышающие диапазон 0..(x+1)*2.

Согласен - задачка не простая... Первое что пришло в голову - это использовать 1 число (назовем его h) от 0..x, и просумировать h+1 раз массив, затем найти тот вариант, где DeltaS будет максимальна. Ho результат не очень впечатляющий, т.e. редко удается значительно увеличить DeltaS. Желательно если DeltaS всегда будет удаваться сдвигать на минимум 1/4 от n*x. или хотябы на 1/3.

Немного пересказал задание, может так понятней будет:

Вопрос состоит в том: как бы изменить цыфры данного числа, так чтобы значительно*** уменьшить* или увеличить* их сумму? Ho c условием, что число придется востанавливать**.

*Пусть число будет состоять из цыфр в -ной системе счисления, тогда , a . Другое значение - это число отражающее разницу между и суммы цыфр из числа. T.e. . Следовательно, для того чтобы УМЕНЬШИТЬ (к нулю) или УВЕЛИЧИТЬ (к ) значение - необходимо произвести некоторые операции над цыфрами данного числа или над всем числом в общем.

**Для того чтобы востановить исходное число, возможно придется использовать некоторые переменные, поэтому допускается использовать 1-2 переменные размерностью не больше чем или 1 переменную размером .

***Степень увеличения должна вписываться в диапазон: .