#P3187. Backward Digit Sums
Backward Digit Sums
题目描述:
和他的奶牛们喜欢玩一个智力游戏。他们按某种顺序写下从 到 的数字,然后将相邻的数字相加,得到一个新的、少一个数字的列表。他们重复这个过程,直到只剩下一个数字。例如,当 时,游戏的一个可能过程如下:
3 1 2 4
4 3 6
7 9
16
在 不知情的情况下,奶牛们开始玩一个更难的游戏:她们试图仅根据最终的总和以及数字 来确定初始的排列顺序。可惜,这个游戏的难度超出了 的心算能力范围。
请编写一个程序来帮助 参与游戏,以便他能跟上奶牛们的思维。
输入:
第一行:两个用空格分隔的整数: 和最终的总和。
输出:
第一行:一个由整数 组成的排列,该排列能得到给定的总和。如果存在多个解,选择字典序最小的那个,即先放置较小数字的排列。
输入数据1
4 16
输出数据1
3 1 2 4
提示:
样例解释: 存在其他可能的序列,例如 ,但 是字典序最小的。
来源:
美国计算机科学奥林匹克竞赛(USACO)2006 年 2 月 黄金级与白银级