English · Original
Chinese · Translation
Formal · Original
One tradition of welcoming the New Year is launching fireworks into the sky. Usually a launched firework flies vertically upward for some period of time, then explodes, splitting into several parts flying in different directions. Sometimes those parts also explode after some period of time, splitting into even more parts, and so on.
Limak, who lives in an infinite grid, has a single firework. The behaviour of the firework is described with a recursion depth _n_ and a duration for each level of recursion _t_1, _t_2, ..., _t__n_. Once Limak launches the firework in some cell, the firework starts moving upward. After covering _t_1 cells (including the starting cell), it explodes and splits into two parts, each moving in the direction changed by 45 degrees (see the pictures below for clarification). So, one part moves in the top-left direction, while the other one moves in the top-right direction. Each part explodes again after covering _t_2 cells, splitting into two parts moving in directions again changed by 45 degrees. The process continues till the _n_\-th level of recursion, when all 2_n_ - 1 existing parts explode and disappear without creating new parts. After a few levels of recursion, it's possible that some parts will be at the same place and at the same time — it is allowed and such parts do not crash.
Before launching the firework, Limak must make sure that nobody stands in cells which will be visited at least once by the firework. Can you count the number of those cells?
## Input
The first line of the input contains a single integer _n_ (1 ≤ _n_ ≤ 30) — the total depth of the recursion.
The second line contains _n_ integers _t_1, _t_2, ..., _t__n_ (1 ≤ _t__i_ ≤ 5). On the _i_\-th level each of 2_i_ - 1 parts will cover _t__i_ cells before exploding.
## Output
Print one integer, denoting the number of cells which will be visited at least once by any part of the firework.
[samples]
## Note
For the first sample, the drawings below show the situation after each level of recursion. Limak launched the firework from the bottom-most red cell. It covered _t_1 = 4 cells (marked red), exploded and divided into two parts (their further movement is marked green). All explosions are marked with an '_X_' character. On the last drawing, there are 4 red, 4 green, 8 orange and 23 pink cells. So, the total number of visited cells is 4 + 4 + 8 + 23 = 39.
<center></center>For the second sample, the drawings below show the situation after levels 4, 5 and 6. The middle drawing shows directions of all parts that will move in the next level.
<center></center>
迎接新年的传统之一是向天空发射烟花。通常，一枚发射的烟花会垂直向上飞行一段时间，然后爆炸，分裂成多个向不同方向飞行的碎片。有时这些碎片在经过一段时间后也会再次爆炸，分裂成更多碎片，依此类推。
住在无限网格中的 Limak 拥有一枚烟花。这枚烟花的行为由递归深度 #cf_span[n] 和每一层递归的持续时间 #cf_span[t1, t2, ..., tn] 描述。当 Limak 在某个格子中发射烟花时，烟花开始向上移动。在覆盖 #cf_span[t1] 个格子（包括起始格子）后，它爆炸并分裂成两个部分，每个部分的移动方向相对于原来的方向改变了 #cf_span[45] 度（详见下方图示）。因此，一个部分向左上方向移动，另一个部分向右上方向移动。每个部分在覆盖 #cf_span[t2] 个格子后再次爆炸，分裂成两个部分，其方向再次改变 #cf_span[45] 度。该过程持续到第 #cf_span[n] 层递归，此时所有 #cf_span[2n - 1] 个现有部分爆炸并消失，不再产生新部分。经过若干层递归后，某些部分可能会出现在同一位置和同一时间——这是允许的，这些部分不会相互碰撞。
在发射烟花之前，Limak 必须确保没有人站在烟花的任何部分至少访问过一次的格子中。你能计算出这些格子的数量吗？
输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 30]) —— 递归的总深度。
第二行包含 #cf_span[n] 个整数 #cf_span[t1, t2, ..., tn] (#cf_span[1 ≤ ti ≤ 5])。在第 #cf_span[i] 层，每个 #cf_span[2i - 1] 个部分在爆炸前会覆盖 #cf_span[ti] 个格子。
请输出一个整数，表示被烟花任意部分至少访问过一次的格子总数。
对于第一个样例，下图展示了每次递归层级后的场景。Limak 从最下方的红色格子发射烟花。它覆盖了 #cf_span[t1 = 4] 个格子（标记为红色），爆炸后分裂成两个部分（它们后续的移动标记为绿色）。所有爆炸点用 '_X_' 字符标记。在最后一张图中，有 #cf_span[4] 个红色格子、#cf_span[4] 个绿色格子、#cf_span[8] 个橙色格子和 #cf_span[23] 个粉红色格子。因此，访问过的格子总数为 #cf_span[4 + 4 + 8 + 23 = 39]。
对于第二个样例，下图展示了第 #cf_span[4]、#cf_span[5] 和 #cf_span[6] 层后的场景。中间的图展示了下一层次所有部分的移动方向。
## Input
输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 30]) —— 递归的总深度。第二行包含 #cf_span[n] 个整数 #cf_span[t1, t2, ..., tn] (#cf_span[1 ≤ ti ≤ 5])。在第 #cf_span[i] 层，每个 #cf_span[2i - 1] 个部分在爆炸前会覆盖 #cf_span[ti] 个格子。
## Output
请输出一个整数，表示被烟花任意部分至少访问过一次的格子总数。
[samples]
## Note
对于第一个样例，下图展示了每次递归层级后的场景。Limak 从最下方的红色格子发射烟花。它覆盖了 #cf_span[t1 = 4] 个格子（标记为红色），爆炸后分裂成两个部分（它们后续的移动标记为绿色）。所有爆炸点用 '_X_' 字符标记。在最后一张图中，有 #cf_span[4] 个红色格子、#cf_span[4] 个绿色格子、#cf_span[8] 个橙色格子和 #cf_span[23] 个粉红色格子。因此，访问过的格子总数为 #cf_span[4 + 4 + 8 + 23 = 39]。对于第二个样例，下图展示了第 #cf_span[4]、#cf_span[5] 和 #cf_span[6] 层后的场景。中间的图展示了下一层次所有部分的移动方向。
**Definitions**
Let $ n \in \mathbb{Z} $ be the recursion depth, with $ 1 \leq n \leq 30 $.
Let $ t = (t_1, t_2, \dots, t_n) $ be a sequence of integers, where $ 1 \leq t_i \leq 5 $, representing the number of cells covered at level $ i $.
The firework starts at an initial cell $ (0,0) $, moving in direction $ \vec{d}_0 = (0,1) $ (up).
At level $ i \in \{1, \dots, n\} $, each active part moves in a direction $ \vec{d} \in D $, where $ D $ is the set of 8 cardinal and diagonal directions:
$$
D = \left\{ (\pm1,0), (0,\pm1), (\pm1,\pm1) \right\}
$$
Each part at level $ i $ moves $ t_i $ cells in its current direction, visiting $ t_i $ cells (including the starting cell of the segment), then splits into two parts, each turning $ \pm 45^\circ $ from its current direction.
**Constraints**
1. $ 1 \leq n \leq 30 $
2. $ 1 \leq t_i \leq 5 $ for all $ i \in \{1, \dots, n\} $
3. At level $ i $, there are $ 2^{i-1} $ parts.
4. The direction of each part evolves deterministically: from direction $ \vec{d} $, it splits into directions $ \vec{d}_{\text{left}} $ and $ \vec{d}_{\text{right}} $, obtained by rotating $ \vec{d} $ by $ \pm 45^\circ $ (clockwise/counter-clockwise) in the 8-direction grid.
**Objective**
Compute the cardinality of the set $ V $ of all unique grid cells visited by any part of the firework during its entire evolution:
$$
V = \bigcup_{i=1}^{n} \bigcup_{j=1}^{2^{i-1}} \text{Path}(i,j)
$$
where $ \text{Path}(i,j) $ is the set of $ t_i $ cells visited by the $ j $-th part at level $ i $.
Return $ |V| $.
API Response (JSON)
{
"problem": {
"name": "D. New Year and Fireworks",
"description": {
"content": "One tradition of welcoming the New Year is launching fireworks into the sky. Usually a launched firework flies vertically upward for some period of time, then explodes, splitting into several parts fl",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF750D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "One tradition of welcoming the New Year is launching fireworks into the sky. Usually a launched firework flies vertically upward for some period of time, then explodes, splitting into several parts fl...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "迎接新年的传统之一是向天空发射烟花。通常，一枚发射的烟花会垂直向上飞行一段时间，然后爆炸，分裂成多个向不同方向飞行的碎片。有时这些碎片在经过一段时间后也会再次爆炸，分裂成更多碎片，依此类推。\n\n住在无限网格中的 Limak 拥有一枚烟花。这枚烟花的行为由递归深度 #cf_span[n] 和每一层递归的持续时间 #cf_span[t1, t2, ..., tn] 描述。当 Limak 在某个格子中发...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the recursion depth, with $ 1 \\leq n \\leq 30 $. \nLet $ t = (t_1, t_2, \\dots, t_n) $ be a sequence of integers, where $ 1 \\leq t_i \\leq 5 $, representing ...",
"is_translate": false,
"language": "Formal"
}
]
}