B - Tetrahedral Number Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 150 点

問題文

整数 N が与えられます。

非負整数の組 (x,y,z) であって x+y+z\leq N を満たすものを辞書順で小さい方から順に全て出力してください。

非負整数の組の辞書順とは？

非負整数の組 (x,y,z) が (x',y',z') より辞書順で小さいとは、下記のいずれかが成り立つことを言います。

  • x < x' である
  • x=x' かつ y< y' である
  • x=x' かつ y=y' かつ z< z' である

制約

  • 0 \leq N \leq 21
  • N は整数である

入力

入力は以下の形式で標準入力から与えられる。

N

出力

非負整数の組 (x,y,z) であって x+y+z\leq N を満たすものを、1 行に 1 組ずつ x,y,z を空白区切りで、辞書順で小さい方から順に全て出力せよ。

入力例 1

3

出力例 1

0 0 0
0 0 1
0 0 2
0 0 3
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 3 0
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 2 0
2 0 0
2 0 1
2 1 0
3 0 0

入力例 2

4

出力例 2

0 0 0
0 0 1
0 0 2
0 0 3
0 0 4
0 1 0
0 1 1
0 1 2
0 1 3
0 2 0
0 2 1
0 2 2
0 3 0
0 3 1
0 4 0
1 0 0
1 0 1
1 0 2
1 0 3
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 3 0
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 2 0
3 0 0
3 0 1
3 1 0
4 0 0

Score : 150 points

Problem Statement

You are given an integer N.

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order.

What is lexicographical order for non-negative integer triples?

A triple of non-negative integers (x,y,z) is said to be lexicographically smaller than (x',y',z') if and only if one of the following holds:

  • x < x';
  • x=x' and y< y';
  • x=x' and y=y' and z< z'.

Constraints

  • 0 \leq N \leq 21
  • N is an integer.

Input

The input is given from Standard Input in the following format:

N

Output

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order, with x,y,z separated by spaces, one triple per line.

Sample Input 1

3

Sample Output 1

0 0 0
0 0 1
0 0 2
0 0 3
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 3 0
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 2 0
2 0 0
2 0 1
2 1 0
3 0 0

Sample Input 2

4

Sample Output 2

0 0 0
0 0 1
0 0 2
0 0 3
0 0 4
0 1 0
0 1 1
0 1 2
0 1 3
0 2 0
0 2 1
0 2 2
0 3 0
0 3 1
0 4 0
1 0 0
1 0 1
1 0 2
1 0 3
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 3 0
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 2 0
3 0 0
3 0 1
3 1 0
4 0 0