#P3187. Backward Digit Sums

    ID: 2188 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>组合数学递推杨辉三角形USACO 2006 February Gold & Silver

Backward Digit Sums

题目描述:

FJFJ 和他的奶牛们喜欢玩一个智力游戏。他们按某种顺序写下从 11N1N10N(1 ≤ N ≤ 10)的数字,然后将相邻的数字相加,得到一个新的、少一个数字的列表。他们重复这个过程,直到只剩下一个数字。例如,当 N=4N=4 时,游戏的一个可能过程如下:

3   1   2   4

  4   3   6

    7   9

     16

FJFJ 不知情的情况下,奶牛们开始玩一个更难的游戏:她们试图仅根据最终的总和以及数字 NN 来确定初始的排列顺序。可惜,这个游戏的难度超出了 FJFJ 的心算能力范围。

请编写一个程序来帮助 FJFJ 参与游戏,以便他能跟上奶牛们的思维。

输入:

第一行:两个用空格分隔的整数:NN 和最终的总和。

输出:

第一行:一个由整数 1..N1..N 组成的排列,该排列能得到给定的总和。如果存在多个解,选择字典序最小的那个,即先放置较小数字的排列。

输入数据1

4 16

输出数据1

3 1 2 4

提示:

样例解释: 存在其他可能的序列,例如 32143 2 1 4,但 31243 1 2 4 是字典序最小的。

来源:

美国计算机科学奥林匹克竞赛(USACO)2006 年 2 月 黄金级与白银级