/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 475 点
問題文
座標空間上に一辺 7 の立方体を 3 つ、ちょうど 1,2,3 個の立方体に含まれる領域の体積がそれぞれ V_1,V_2,V_3 となるように配置したいです。
3 つの整数 a,b,c に対し、(a\leq x\leq a+7) \land (b\leq y\leq b+7) \land (c\leq z\leq c+7) で表される立方体領域を C(a,b,c) とおきます。
以下の条件を全て満たすような 9 つの整数 a_1,b_1,c_1,a_2,b_2,c_2,a_3,b_3,c_3 が存在するか判定し、存在するならば実際に 1 つ求めてください。
- |a_1|,|b_1|,|c_1|,|a_2|,|b_2|,|c_2|,|a_3|,|b_3|,|c_3| \leq 100
- C_i = C(a_i,b_i,c_i)\ (i=1,2,3) とおいたとき、
- C_1,C_2,C_3 のうちちょうど 1 個に含まれる領域の体積は V_1 である。
- C_1,C_2,C_3 のうちちょうど 2 個に含まれる領域の体積は V_2 である。
- C_1,C_2,C_3 の全てに含まれる領域の体積は V_3 である。
制約
- 0\leq V_1,V_2,V_3 \leq 3\times 7^3
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
V_1 V_2 V_3
出力
問題文中の条件を全て満たすような 9 つの整数 a_1,b_1,c_1,a_2,b_2,c_2,a_3,b_3,c_3 が存在しないならば No を出力し、存在するならば以下の形式で出力せよ。
複数存在する場合はそのどれを出力してもよい。
Yes a_1 b_1 c_1 a_2 b_2 c_2 a_3 b_3 c_3
入力例 1
840 84 7
出力例 1
Yes 0 0 0 0 6 0 6 0 0
(a_1,b_1,c_1,a_2,b_2,c_2,a_3,b_3,c_3)=(0,0,0,0,6,0,6,0,0) の場合を考えます。
この図は C_1,C_2,C_3 の位置関係を表したもので、それぞれ橙、水色、緑の立方体に対応しています。
このとき、
- |a_1|,|b_1|,|c_1|,|a_2|,|b_2|,|c_2|,|a_3|,|b_3|,|c_3| は全て 100 以下
- C_1,C_2,C_3 の全てに含まれる領域は (6\leq x\leq 7)\land (6\leq y\leq 7) \land (0\leq z\leq 7) であり、その体積は (7-6)\times(7-6)\times(7-0)=7
- C_1,C_2,C_3 のうちちょうど 2 個に含まれる領域は ((0\leq x < 6)\land (6\leq y\leq 7) \land (0\leq z\leq 7))\lor((6\leq x\leq 7)\land (0\leq y< 6) \land (0\leq z\leq 7)) であり、 その体積は (6-0)\times(7-6)\times(7-0)\times 2=84
- C_1,C_2,C_3 のうちちょうど 1 個に含まれる領域の体積は 840
であり、条件を全て満たします。
(a_1,b_1,c_1,a_2,b_2,c_2,a_3,b_3,c_3)=(-10, 0, 0, -10, 0, 6, -10, 6, 1) なども同様に条件を全て満たすため、正当な出力として判定されます。
入力例 2
343 34 3
出力例 2
No
条件を全て満たすような 9 つの整数 a_1,b_1,c_1,a_2,b_2,c_2,a_3,b_3,c_3 は存在しません。
Score: 475 points
Problem Statement
In a coordinate space, we want to place three cubes with a side length of 7 so that the volumes of the regions contained in exactly one, two, three cube(s) are V_1, V_2, V_3, respectively.
For three integers a, b, c, let C(a,b,c) denote the cubic region represented by (a\leq x\leq a+7) \land (b\leq y\leq b+7) \land (c\leq z\leq c+7).
Determine whether there are nine integers a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3 that satisfy all of the following conditions, and find one such tuple if it exists.
- |a_1|, |b_1|, |c_1|, |a_2|, |b_2|, |c_2|, |a_3|, |b_3|, |c_3| \leq 100
- Let C_i = C(a_i, b_i, c_i)\ (i=1,2,3).
- The volume of the region contained in exactly one of C_1, C_2, C_3 is V_1.
- The volume of the region contained in exactly two of C_1, C_2, C_3 is V_2.
- The volume of the region contained in all of C_1, C_2, C_3 is V_3.
Constraints
- 0 \leq V_1, V_2, V_3 \leq 3 \times 7^3
- All input values are integers.
Input
The input is given from Standard Input in the following format:
V_1 V_2 V_3
Output
If no nine integers a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3 satisfy all of the conditions in the problem statement, print No. Otherwise, print such integers in the following format. If multiple solutions exist, you may print any of them.
Yes a_1 b_1 c_1 a_2 b_2 c_2 a_3 b_3 c_3
Sample Input 1
840 84 7
Sample Output 1
Yes 0 0 0 0 6 0 6 0 0
Consider the case (a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3) = (0, 0, 0, 0, 6, 0, 6, 0, 0).
The figure represents the positional relationship of C_1, C_2, and C_3, corresponding to the orange, cyan, and green cubes, respectively.
Here,
- All of |a_1|, |b_1|, |c_1|, |a_2|, |b_2|, |c_2|, |a_3|, |b_3|, |c_3| are not greater than 100.
- The region contained in all of C_1, C_2, C_3 is (6\leq x\leq 7)\land (6\leq y\leq 7) \land (0\leq z\leq 7), with a volume of (7-6)\times(7-6)\times(7-0)=7.
- The region contained in exactly two of C_1, C_2, C_3 is ((0\leq x < 6)\land (6\leq y\leq 7) \land (0\leq z\leq 7))\lor((6\leq x\leq 7)\land (0\leq y < 6) \land (0\leq z\leq 7)), with a volume of (6-0)\times(7-6)\times(7-0)\times 2=84.
- The region contained in exactly one of C_1, C_2, C_3 has a volume of 840.
Thus, all conditions are satisfied.
(a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3) = (-10, 0, 0, -10, 0, 6, -10, 6, 1) also satisfies all conditions and would be a valid output.
Sample Input 2
343 34 3
Sample Output 2
No
No nine integers a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3 satisfy all of the conditions.