問題一覧 > 通常問題

No.1988 Divisor Tiling

レベル : / AI推定難易度 : 1225 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 94
作問者 : riano / テスター : tokusakurai magsta milkcoffee
お気に入りにしたユーザー ProblemId : 7954 / 自分の提出
問題文最終更新日: 2022-06-05 23:15:25
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 349 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。