No.1988 Divisor Tiling
タグ : / 解いたユーザー数 94
作問者 :
riano
/ テスター :
magsta
milkcoffee
Problem Statement
You are given a perfect number $N$ and $1$ of its divisors, $H$. A positive integer $N$ is called a perfect number if the sum of all positive divisors of $N$ other than $N$ itself equals $N$.
Here, express this property using rectangles. That is, for each positive divisor of $N$ other than $N$ itself (call it $a$), freely choose $1$ rectangle with area $a$ whose height and width are both integers, and tile all of them without overlap to form a rectangle with height $H$ and area $N$.
If this is impossible, report that.
Input
$N\ \ H$
- $N$ is one of $6,28,496,8128$, the perfect numbers less than or equal to $10000$
- $H$ is a positive divisor of $N$
- All inputs are integers
Output
If the required construction is possible, output a total of $N$ numbers separated by spaces, arranged as a rectangle with $H$ rows (height) and $N/H$ columns (width), so that when the rectangles are tiled in the specified way, the area occupied by each rectangle is filled with the value of its area as an integer.
(Refer to the samples as needed.)
If the construction is impossible, output only -1.
Print a newline at the end.
Sample
Sample 1
Input
6 2
Output
2 2 1 3 3 3
When tiling with height $2$ and area $6$, a tiling such as the one in Figure $1$ can be considered.
The output corresponding to this figure is the one shown above.
On the other hand, a tiling such as the one in Figure $2$ is a wrong answer, because the shape with area $3$ is not a rectangle.
Sample 2
Input
28 1
Output
2 2 7 7 7 7 7 7 7 1 14 14 14 14 14 14 14 14 14 14 14 14 14 14 4 4 4 4
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。