← 返回题目列表

Codeforces · 1854/F

F. 马克和宇宙飞船

中文机器翻译题面 查看原题

马克喜欢快速行动。所以他制造了一艘在 $$$4$$$ 维空间中工作的宇宙飞船。

他想利用飞船尽快完成任务。在每次任务中,宇宙飞船从 $$$(0, 0, 0, 0)$$$ 开始,并需要在 $$$(a, b, c, d)$$$ 结束。为此,他指示飞船的计算机执行一系列移动,其中每个移动都是八个基本方向之一的一个单位步骤:$$$(\pm 1, 0, 0, 0)$$$, $$$(0, \pm 1, 0, 0)$$$, $$$(0, 0, \pm 1, 0)$$$, $$$(0, 0, 0, \pm 1)$$$。

不幸的是,他在建造飞船时动作也很快,所以飞船的代码出现了一个bug。第一个动作将执行一次,第二个动作将执行两次,第三个动作将执行三次,依此类推。一般来说,第 $$$i$$$ 步将被执行 $$$i$$$ 次。

对于任意四个整数 $$$a, b, c, d$$$,令 $$$f(a, b, c, d)$$$ 为最终到达 $$$(a, b, c, d)$$$ 的任务的最小移动次数。计算所有点(具有整数坐标)的 $$$f(a, b, c, d)$$$ 之和,使得 $$$-A\le a\le A$$$、$$$-B\le b\le B$$$、$$$-C\le c\le C$$$、$$$-D\le d\le D$$$。

输入

输入的唯一行包含四个整数 $$$A, B, C, D$$$ ($$$0\le A,B,C,D\le 1000$$$)。

输出

打印语句中描述的点集 $$$f(a, b, c, d)$$$ 的总和。

示例

输入 #1

1 0 0 0

输出 #1

2

输入 #2

1 1 0 1

输出 #2

82

输入 #3

3 2 4 1

输出 #3

4616

注意

在第一个示例中,必须计算 $$$f(-1, 0, 0, 0)+f(0, 0, 0, 0) + f(1, 0, 0, 0) = 1 + 0 + 1 = 2$$$。

在第二个示例中,必须计算 $$$27$$$ 不同点 $$$(a, b, c, d)$$$ 上 $$$f(a, b, c, d)$$$ 的总和。让我们描述其中一些的 $$$f(a, b, c, d)$$$ 的值:

- 它保持 $$$f(-1, 0, 0, -1)=3$$$ 并且可以通过以下移动序列来实现(箭头 $$$\xrightarrow{\pm i}$$$ 表示在第 $$$i$$$ 坐标上执行移动): $$$$$$(0, 0, 0, 0) \xrightarrow{-1} (-1, 0, 0, 0) \xrightarrow{+4} (-1, 0, 0, 2) \xrightarrow{-4} (-1, 0, 0, -1).$$$$$$
- 它持有 $$$f(1, 1, 0, 1) = 5$$$,并且可以通过以下移动序列来实现: $$$$$$(0, 0, 0, 0) \xrightarrow{+1} (1, 0, 0, 0) \xrightarrow{-2} (1, -2, 0, 0) \xrightarrow{+2} (1, 1, 0, 0) \xrightarrow{-4} (1, 1, 0, -4) \xrightarrow{+4} (1, 1, 0, 1).$$$$$$

在第三个示例中,必须计算 $$$f(a, b, c, d)$$$ 在 $$$7\cdot5\cdot 9\cdot 3$$$ 点上的总和。其中之一是 $$$(3, 2, 4, 1)$$$。它持有 $$$f(3, 2, 4, 1) = 4$$$,并且可以通过以下移动序列来实现: $$$$$$(0, 0, 0, 0) \xrightarrow{+4} (0, 0, 0, 1) \xrightarrow{+2} (0, 2, 0, 1) \xrightarrow{+1} (3, 2, 0, 1) \xrightarrow{+3} (3, 2, 4, 1).$$$$$$