← 返回题目列表

AtCoder · joi2006ho_c

C. JOI 2006年最终问题3

中文机器翻译题面 查看原题

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

JOI 2006 本選 問題3 - 原题 PDF 第 1 页
原题PDF第1页
可复制的 PDF 提取文本
3   同じ大きさの正方形の紙がn 枚ある.これらの紙の下部を水平に揃えて何列

かに並べる.ただし,隣り合う列は左側が右側より低くならないように並べなけれ
ばならない.例えば, n = 5 のときは,次のような7 通りの並べ方が可能である.

  ■
  ■ ■
  ■ ■  ■  ■
  ■ ■  ■■ ■   ■■  ■
  ■ ■■ ■■ ■■■ ■■■ ■■■■ ■■■■■

 これらを,各列に並んだ正方形の個数の列で表すことにする.例えば,n = 5 の

ときは,それぞれ,

           (5)   (4, 1)   (3, 2)   (3, 1, 1)   (2, 2, 1)   (2, 1, 1, 1)   (1, 1, 1, 1, 1)


と表わされる.
  n を入力したとき,辞書式順序で全て出力するプログラムを作成せよ.n ≦30
とする.ただし, 辞書式順序とは2つの並べ方(a1, a2, ..., as) が並べ方(b1, b2, ..., bt)
に対して, a1 > b1 または, ある整数i > 1 が存在してa1 = b1, ..., ai−1 = bi−1 かつ
ai > bi が成り立つとき(a1, a2, ..., as) が(b1, b2, ..., bt) より先に出力されるように並
べることである.
 入力ファイルのファイル名は“input.txt” である.“input.txt” は1 行からなり,
1 行目にn が書かれている.
 出力ファイルのファイル名は“output.txt” である.“output.txt” には並べ方を
辞書式順序で1 行に1通りずつ書き最後に改行を入れること. 並べ方は(a1, a2, ..., as)
の出力は整数a1, a2, . . . , as をこの順番に空白で区切って出力すること.

入力例
5


出力例
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1


                        問題3-1