LG#P1118. 【GESP强化 六级】逆向数字和

提交1 通过1
通过率100%
时间限制1000ms
内存限制128MiB
    ID: 10247 传统题 1000ms 128MiB 尝试: 1 已通过: 1 难度: 普及 上传者: 标签>GESPGESP强化C++c++编程题洛谷公开题搜索2006USACO枚举深度优先搜索 DFS深度优先搜索2星

题目描述

小婷老师和同学们在做一个数字推演游戏。先把 11NNNN 个整数按某种顺序写成一行,然后把每两个相邻数字相加,得到少一个数字的新一行;对新一行继续做同样的操作,直到最后只剩下一个数。

例如,当 N=4N=4 时,某次推演过程可能是:

3   1   2   4
  4   3   6
    7   9
      16

现在只知道整数 NN 和最后得到的总和。请还原一种可能的初始排列。如果存在多种排列,应选择字典序最小的一种,也就是尽量让较小的数字出现在前面。

输入格式

输入一行,包含两个用空格分隔的整数 NNSS,分别表示初始数字的个数和最后得到的总和。

输出格式

输出一行,包含 11NN 的一个排列。该排列经过不断合并相邻数字后,最终结果应为 SS;若有多种答案,输出字典序最小的一种。

4 16
3 1 2 4
1 1
1
2 3
1 2

数据范围与约定

  • 对于 40%40\% 的数据,1N71\le N\le 7
  • 对于 80%80\% 的数据,1N101\le N\le 10
  • 对于 100%100\% 的数据,1N121\le N\le 121S123451\le S\le 12345

输入保证至少存在一种符合要求的排列。