Пусть сумма всех элементов равна full_sum, а длина массива 2k.
Предлагаю организовать банальный перебор: выберем k индексов из 2k, посчитаем сумму соответствующих элементов. Будем искать максимальную сумму, которая не превосходит full_sum/2. При этом сумма невыбранных элементов будет не меньше full_sum/2, и будет отличаться от суммы выбранных элементов на минимально возможную величину.
Этот алгоритм работает быстро только для относительно небольших значений k. если нужно что-то быстрее, то придется придумывать что-то дополнительно.
Код (Python 3):
from random import randint
from itertools import combinations
k = 10
a = [randint(1, 100) for _ in range(2 * k)]
print(*a)
full_sum = sum(a)
half_sum = full_sum // 2
max_sum = -1
answer = None
for seq in combinations(range(2 * k), k):
s = sum(map(lambda ind: a[ind], seq))
if s <= half_sum and s > max_sum:
max_sum, answer = s, seq
if s == half_sum:
break
left = [a[i] for i in answer]
right = [el for i, el in enumerate(a) if i not in answer]
a = left + right
print(*a)
Пример вывода:
50 39 19 63 16 4 82 45 63 33 6 57 39 16 38 4 66 56 87 84
50 39 19 63 16 4 82 57 16 87 45 63 33 6 39 38 4 66 56 84
Шифр Цезаря один из наиболее древнейших известных шифров. Схема шифрования очень проста — используется сдвиг буквы алфавита на фиксированное число позиций. Используемое преобразование обычно обозначают как ROTN, где N — сдвиг, ROT — сокращение от слова ROTATE, в данном случае «циклический сдвиг».
Алфавит действительно зацикливается, то есть буквы в конце алфавита преобразуются в буквы начала алфавита. Например, обозначение ROT2 обозначает сдвиг на 2 позиции, то есть, «а» превращается в «в», «б» в «г», и так далее, и в конце «ю» превращается в «а» а «я» — в «б». Число разных преобразований конечно и зависит от длины алфавита. Для русского языка возможно 32 разных преобразования (преобразования ROT0 и ROT33 сохраняют исходный текст, а дальше начинаются уже повторения). В связи с этим шифр является крайне слабым и исходный текст можно восстановить просто проверив все возможные преобразования.
Калькулятор выдает таблицу всех возможных в шифре Цезаря преобразований введенного текста. Неалфавитные символы — знаки препинания, пробелы, цифры — не меняются.
