Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
1 辺の長さが N の立方体を,1 辺の長さが 1 の立方体 N^3 個に分割し,そこから K 個選びます. 立方体の面に垂直な 3 方向のうちどの方向から見ても,選んだ K 個の立方体がすべて見え,なおかつ同じ形で見えるような選び方を 1 つ構成してください.
問題を厳密に定式化するために,分割後の各立方体を整数の 3 つ組 (x_i, y_i, z_i) に対応させます.
以下の条件を満たす K 個の整数の 3 つ組 (x_i, y_i, z_i) を 1 つ構成し,出力してください.
- 0 \leq x_i, y_i, z_i < N
- \left\lbrace (x_i, y_i) \, \middle| \, 1 \le i \le K \right\rbrace = \left\lbrace (y_i, z_i) \, \middle| \, 1 \le i \le K \right\rbrace = \left\lbrace (z_i, x_i) \, \middle| \, 1 \le i \le K \right\rbrace
- 前項の集合は K 個の要素を持つ.つまり,i \neq j に対し (x_i, y_i) \neq (x_j, y_j) となる.
なお,制約を満たす任意の入力に対して,条件を満たす答えが存在することが示せます.
制約
- 入力される数値は全て整数
- 1 \leq N \leq 500
- 1 \leq K \leq N^2
入力
入力は以下の形式で標準入力から与えられる.
N K
出力
答えを以下の形式で出力せよ.
x_1 y_1 z_1 x_2 y_2 z_2 \vdots x_K y_K z_K
解が複数存在する場合,どれを出力しても正解とみなされる.
入力例 1
3 3
出力例 1
0 0 0 1 1 1 2 2 2
入力例 2
2 4
出力例 2
0 0 1 0 1 0 1 0 0 1 1 1
入力例 3
1 1
出力例 3
0 0 0
Score: 800 points
Problem Statement
Divide a cube with a side length of N into N^3 smaller cubes, each with a side length of 1, and select K of these smaller cubes. Construct one way to select them so that, when viewed from any of the three directions perpendicular to the faces of the cubes, all K selected cubes are visible and appear in the same shape.
To formulate the problem precisely, we associate each smaller cube after division with a triple of integers (x_i, y_i, z_i).
Construct and print one set of K triples of integers (x_i, y_i, z_i) that satisfy the following conditions.
- 0 \leq x_i, y_i, z_i < N
- \left\lbrace (x_i, y_i) \, \middle| \, 1 \le i \le K \right\rbrace = \left\lbrace (y_i, z_i) \, \middle| \, 1 \le i \le K \right\rbrace = \left\lbrace (z_i, x_i) \, \middle| \, 1 \le i \le K \right\rbrace
- The set mentioned in the previous item has K elements. That is, (x_i, y_i) \neq (x_j, y_j) for i \neq j.
It can be shown that a solution exists for any input satisfying the constraints.
Constraints
- All input values are integers.
- 1 \leq N \leq 500
- 1 \leq K \leq N^2
Input
The input is given from Standard Input in the following format:
N K
Output
Print your answer in the following format:
x_1 y_1 z_1 x_2 y_2 z_2 \vdots x_K y_K z_K
If multiple solutions exist, any of them will be accepted.
Sample Input 1
3 3
Sample Output 1
0 0 0 1 1 1 2 2 2
Sample Input 2
2 4
Sample Output 2
0 0 1 0 1 0 1 0 0 1 1 1
Sample Input 3
1 1
Sample Output 3
0 0 0