题目思路

dfs搜索，可以发现这道题直接dfs会超时，所以可以限制数组单调递增，可以很好地优化时间.

根据题意，先初始化每个包装有一个积木，然后将剩余的积木进行搜索，为保证单调，只有当前积木的个数大于等于上一个包装的积木是才继续搜索。

最后将搜索出来的结果进行判断价格是否符合p，记录答案并每次比较得最小字典序的答案。

代码

题目内容

塔子哥是一名玩具店老板，他经营的玩具店以木制小玩具为主要商品。

最近，他准备将 $N$ 个小玩具分装到 $M$ 个小包装内，并将这些小包装出售。为了使商品价格具有竞争力，他希望限制小包装的总价值不超过 $P$，但也不希望价格太低以至于亏本。

单个小包装的价值为包装内部玩具数量的平方。

因此，他需要找到一种分装方案，使得所有小包装的价值之和恰好为 $P$，而且如果存在多种方案，他希望选择字典序最小的那一个。

对于两种不同方案 ${a_1,a_2,…,a_M}$ 与 ${b_1,b_2,...,b_M}$若对于 $1\le i\le t$ 的均有 $a_i=b_i$,且 $a_{t+1} \lt b_{t+1}$ ,那么认为方案 $a$ 的字典序小于方案 $b$ 。

注意：当 $t=0$ 时，没有合法的$i$ 存在， $1\le i\le t$ 只是限制 $i$ 的范围。

例如，对于 $M=3,N=4$ 的情况下， ${1,1,2}$ 的字典序小于 ${2,1,1}$ （对应 $t=0$ 的情况）、 ${1,2,1}$ （对应 $t=1$ 的情况）。

输入描述

第一行三个正整数 $N,M,P$ ，含义如题面。 对于所有数据， $1\le M\le N\le 12$ ， $0\le P\le 10^9$

输出描述

若不存在任何方案，输出 $-1$ ， 否则输出 $M$ 个数表示每个小包装内应分的的小玩具数量。

样例

样例一

输入

4 3 6

输出

1 1 2

样例二

输入

4 3 5

输出

-1

样例解释

不存在方案使得分割后价格和为 $5$ 。