Изначально на карточке были записаны два натуральных числа. раз в минуту мистер робот берёт эту карточку и, если первое число было нечётным, пишет на доске второе число, в противном случае ничего не делает. после этого мистер робот выбрасывает старую карточку и делает новую, первым числом на которой является уменьшенное вдвое и округлённое до единицы вниз первое число с предыдущей карточки, а вторым - удвоенное второе число с предыдущей карточки. когда мистер робот получил карточку, первое число на которой равно нулю, он подсчитал сумму всех чисел, записанных на доске. что он получил? примечание к : можно относить как к теме инвариантов, так и к теме систем счисления.

он получил произведение исходных чисел.

за странным описанием процесса по сути скрывается описание алгоритма умножения в столбик двоичных чисел: на i-м шаге, если первое число нечетное (=если на i-м месте справа в первом числе стоит 1), к сумме прибавляется 2^(i - 1) * второе число (=если всё записано в двоичной системе счисления, умножение на степень двойки равносильно сдвигу числа влево).

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

сначала на примере, если на карточке записаны 5 и 7:

карточка: 5 и 7, сумма на доске: 0 карточка: 2 и 14, сумма на доске: 7 карточка: 1 и 28, сумма на доске: 7 карточка: 0 и 56, сумма на доске: 7 + 28 = 35

в общем случае: пусть перед текущим шагом на доске числа a и b, сумма чисел на доске s; значение суммы ab + s. есть два случая:

a = 2a'. тогда на следующем шаге на карточке будет a' и 2b, на доске ничего не изменится. значение суммы a' * 2b + s = 2a' * b + s = ab + s a = 2a' + 1. на следующем шаге на карточке a' и 2b, на доску добавится b. значение суммы a' * 2b + s + b = (2a' + 1) b + s = ab + s

изначально на доске выписаны числа суммой 0 (инвариант равен произведению чисел на карточке = p), в конце произведение чисел на карточке равно 0, тогда сумма выписанных чисел равна p.

Для хранения 32 значений цветов нам достаточно 5-бит, принимающие значения от 0 до 31. 2^5=32 цвета, а рисунок 20 на 80 занимает 20 * 80 = 1600 пикселей.

Итого нам понадобиться 1600 * 5 = 8000 бит = 1000 байт.

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