#P1118. [USACO06FEB] Backward Digit Sums G/S

    ID: 118 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>搜索2006USACO枚举,暴力深度优先搜索,DFS

[USACO06FEB] Backward Digit Sums G/S

Description

FJ 和他的奶牛们喜欢玩一个心算游戏。他们将数字从 11N(1N12)N(1 \le N \le 12) 按某种顺序写下来,然后将相邻的数字相加,得到一个数字更少的新列表。他们重复这个过程,直到只剩下一个数字。例如,游戏的一种情况(当 N=4N=4 时)可能是这样的:

    3   1   2   4
      4   3   6
        7   9
         16

FJ 背后,奶牛们开始玩一个更难的游戏,她们试图从最终的总和和数字 NN 中确定起始序列。不幸的是,这个游戏有点超出了 FJ 的心算能力。

编写一个程序来帮助 FJ 玩这个游戏,并跟上奶牛们的步伐。

Input Format

共一行两个正整数 n,sumn,sum

Output Format

输出包括一行,为字典序最小的那个答案。

当无解的时候,请什么也不输出。

4 16
3 1 2 4

Hint

  • 对于 40%40\% 的数据,1N71\le N\le 7
  • 对于 80%80\% 的数据,1N101\le N \le 10
  • 对于 100%100\% 的数据,1N121\le N \le 121sum123451\le sum\le 12345。 (由 ChatGPT 4o 翻译)