Problem H
Pascal's Hyper-Pyramids
We programmers know and love Pascal’s triangle: an array of numbers with $1$ at the top and whose entries are the sum of the two numbers directly above (except numbers at both ends, which are always $1$). For programming this generation rule, the triangle is best represented left-aligned; then the numbers on the left column and on the top row equal $1$ and every other is the sum of the numbers immediately above and to its left. The numbers highlighted in bold correspond to the base of Pascal’s triangle of height $5$:
\[ \begin{array}{|rrrrr} \hline 1 & 1 & 1 & 1 & \textbf{1}\\ 1 & 2 & 3 & \textbf{4} \\ 1 & 3 & \textbf{6} \\ 1 & \textbf{4} \\ \textbf{1} \end{array} \]Pascal’s hyper-pyramids generalize the triangle to higher dimensions. In $3$ dimensions, the value at position $(x, y, z)$ is the sum of up to three other values:
-
$(x, y, z-1)$, the value immediately below it if we are not on the bottom face ($z=0$);
-
$(x, y-1, z)$, the value immediately behind if we are not on the back face ($y=0$);
-
$(x-1, y, z)$, the value immediately to the left if we are not on the leftmost face ($x=0$).
All values at the bottom, back, and leftmost faces are $1$.
The following figure depicts Pascal’s 3D-pyramid of height $5$ as a series of plane cuts obtained by fixing the value of the $z$ coordinate.
|
$z = 0$ |
$z = 1$ |
$z = 2$ |
$z = 3$ |
$z = 4$ |
|
\[ \begin{array}{|rrrrr}
\hline 1 & 1 & 1 & 1 & \textbf{1} \\ 1
& 2 & 3 & \textbf{4} \\ 1 & 3 &
\textbf{6} \\ 1 & \textbf{4} \\ \textbf{1}
\end{array} \]
|
\[ \begin{array}{|rrrr}
\hline 1 & 2 & 3 & \textbf{4} \\ 2 & 6
& \textbf{12} \\ 3 & \textbf{12} \\ \textbf{4}
\end{array} \]
|
\[ \begin{array}{|rrr}
\hline 1 & 3 & \textbf{6} \\ 3 &
\textbf{12} \\ \textbf{6} & \end{array} \]
|
\[ \begin{array}{|rr}
\hline 1 & \textbf{4} \\ \textbf{4} \\ \end{array}
\]
|
\[ \begin{array}{|c}
\hline \textbf{1} \end{array} \]
|
For example, the number at position $x=1$, $y=2$, $z=1$ is the sum of the values at $(0, 2, 1)$, $(1, 1, 1)$ and $(1, 2, 0)$, namely, $6 + 3 + 3 = 12$. The base of the pyramid corresponds to a plane of positions such that $x+y+z = 4$ (highlighted in bold above).
The size of each layer grows quadratically with the height of the pyramid, but there are many repeated values due to symmetries: numbers at positions that are permutations of one another must be equal. For example, the numbers at positions $(0,1,2)$, $(1,2,0)$ and $(2,1,0)$ above are all equal to $3$.
Task
Write a program that, given the number of dimensions $D$ of the hyper-space and the height $H$ of a hyper-pyramid, computes the set of numbers at the base.
Input
A single line with two positive integers: the number of dimensions, $D$, and the height of the hyper-pyramid, $H$.
Constraints
|
$2$ |
$\leq $ |
$D$ |
$<$ |
$32$ |
Number of dimensions |
|
$1$ |
$\leq $ |
$H$ |
$<$ |
$32$ |
Height |
|
$D$ and $H$ are such that all numbers in the hyper-pyramid are less than $2^{63}$. |
|||||
Output
The set of numbers at the base of the hyper-pyramid, with no repetitions, one number per line, and in ascending order.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 5 |
1 4 6 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 5 |
1 4 6 12 |
