Hide

Problem B
Pascal's Hyper-Pyramids

/problems/hyperpyramids/file/statement/en/img-0001.jpg

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

Please log in to submit a solution to this problem

Log in