turuo

27.01.2021 07:19

Информатика

Есть ответ 👍

Одной из популярных традиций встречи нового года является запуск в небо фейерверков. обычно фейерверк взлетает вертикально вверх в течение некоторого времени, после чего взрывается и разделяется на несколько частей, летящих в разных направлениях. иногда эти части через некоторое время снова взрываются, также разделяясь на несколько частей и так далее. лимак живёт на бесконечном клетчатом поле и у него есть один фейерверк. поведение этого фейерверка после запуска описывается рекурсией глубины n и продолжительностью каждого из уровней рекурсии t1, t2, tn. как только лимак запустит фейерверк в какой-нибудь клетке поля, тот начнёт двигаться вверх. после прохождения t1 клеток (включая стартовую) он взрывается и разделяется на две части, каждая из которых двигается в направлении, изменённом на 45 градусов (для лучшего понимания посмотрите картинки ниже). таким образом, одна часть будет двигаться в направлении вверх и влево, а другая в направлении вверх и вправо. каждая из этих частей пройдёт t2 клеток, после чего также разделится на две части, каждая из которых также изменит траекторию на 45 градусов. процесс будет продолжаться до n-го уровня рекурсии, после чего все 2n - 1 частей взорвутся и исчезнут не создавая новых частей. после нескольких уровней рекурсивного разделения частей фейерверка может так оказаться, что две или более частей находятся в одной и той же клетке в один и тот же момент времени — такая ситуация разрешена и эти части не сталкиваются. перед тем как запустить данный фейерверк лимак хочет убедиться в безопасности этого запуска. сможете ли вы посчитать количество клеток, которые хотя бы один раз будут посещены какой-либо частью фейерверка? входные данные: 4 4 2 2 3 выход 39