Задача по информатике 10 класс В велокроссе участвуют 513 спортсменов.Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша,записывая его номер с использованием минимально возможного кол-ва бит,одинакового для каждого спортсмена.Какой информацинный объем в байтах сообщения,записанного устройством,после того как промежуточный финиш спортсменов
Пусть сумма всех элементов равна 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
1. Растровая
2. Векторная
3. 3D графика
5. Фрактальная
Объяснение:
1. Видим обычное изображение, снятое на камеру. Сплошное, образованное набором пикселей. Растровая графика
2. Видим изображение, образованное набором геометрических примитив (фигур). Выглядит как логотип. Векторная графика
3. Видим изображение трехмерных объектов. Скорее всего использовалась 3D графика для описания объектов и источников света, а затем был произведен рендер на плоскость изображения.
4. Видим рекурсивный узор, построенный с фрактала. Фрактальная графика