E - 7x7x7

Contest Duration: 2024-03-02(Sat) 12:00 - 2024-03-02(Sat) 13:40 (local time) (100 minutes) Back to Home

E - 7x7x7 Editorial

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$

入力例 1Copy

Copy

840 84 7

出力例 1Copy

Copy

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)$ なども同様に条件を全て満たすため、正当な出力として判定されます。

入力例 2Copy

Copy

343 34 3

出力例 2Copy

Copy

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 1Copy

Copy

840 84 7

Sample Output 1Copy

Copy

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 2Copy

Copy

343 34 3

Sample Output 2Copy

Copy

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.