Kamelotka

22.02.2022 08:07 •  Информатика

Вася и петя играют в «голодную змейку»: по клетчатой доске 100100 х 100100 клеток перемещается «змея» (положение головы змеи в каждый момент времени описывается одной клеткой), при этом за один ход голова перемещается на одну из соседних восьми клеток (соседние по общей грани и по диагоналям), если для данного перемещения есть свободное пространство (змея не может выходить за края доски). также следует отметить, что размер змеи всегда составляет ровно одну клетку, т.к. на доске отсутствуют «яблоки» для пропитания и увеличения размера змеи. необходимо описать положение змеи на доске в 55 последовательных моментов времени (55 клеток). вася для кодирования каждой клетки использовал две координаты (номер клетки по горизонтали и вертикали), в результате для кодирования пяти клеток ему необходимо xx бит. петя также использовал две координаты (номер клетки по горизонтали и вертикали) для хранения первой клетки в последовательности ходов, но для следующих четырех шагов змеи петя кодировал номер одной из восьми соседних клеток, куда был сделан ход по отношению к предыдущей клетке. в результате пете потребовалось yy бит для кодирования пути змеи. определите, какой кодирования (васин или петин) наиболее эффективен. в ответе укажите целое число бит, равное «x-yx−y» (например, если вася использует 55 бит, а петя – 2020 бит, ответ: -15−15).
примечание: для кодирования клетки (каждой из двух координат) используется одинаковое минимально возможное количество бит. для кодирования номера одной из восьми соседних клеток также используется одинаковое минимально возможное количество бит.​