塔子哥是一名玩具店老板,他经营的玩具店以木制小玩具为主要商品。
最近,他准备将 N 个小玩具分装到 M 个小包装内,并将这些小包装出售。为了使商品价格具有竞争力,他希望限制小包装的总价值不超过 P,但也不希望价格太低以至于亏本。
单个小包装的价值为包装内部玩具数量的平方。
因此,他需要找到一种分装方案,使得所有小包装的价值之和恰好为 P,而且如果存在多种方案,他希望选择字典序最小的那一个。
对于两种不同方案 a1,a2,…,aM 与 b1,b2,...,bM若对于 1≤i≤t 的均有 ai=bi,且 at+1<bt+1 ,那么认为方案 a 的字典序小于方案 b 。
注意:当 t=0 时,没有合法的i 存在, 1≤i≤t 只是限制 i 的范围。
例如,对于 M=3,N=4 的情况下, 1,1,2 的字典序小于 2,1,1 (对应 t=0 的情况)、 1,2,1 (对应 t=1 的情况)。
第一行三个正整数 N,M,P ,含义如题面。 对于所有数据, 1≤M≤N≤12 , 0≤P≤109
若不存在任何方案,输出 −1 , 否则输出 M 个数表示每个小包装内应分的的小玩具数量。
输入
4 3 6
输出
1 1 2
输入
4 3 5
输出
-1
样例解释
不存在方案使得分割后价格和为 5 。
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.