LG#P2089. 烤鸡
烤鸡
P2089 烤鸡
题目描述
猪猪 Hanke 特别喜欢吃烤鸡。他吃鸡的方式很特别:他有 种配料,每种配料可以放 到 克,一只烤鸡的美味程度定义为所有配料的质量之和。
现在给定一个美味程度 ,请你输出这 种配料的所有搭配方案。
字典序:从两个序列的第一个元素开始逐个比较,直到找到第一个不同的位置,通过比较这个位置元素的大小得出两个序列的大小,称为字典序比较。
输入格式
输入一行一个整数 代表美味程度。
输出格式
第一行输出一个整数,代表满足要求的方案总数。
此后每行输出 个整数,依次代表这 种配料的质量,相邻两个整数之间用一个空格隔开。所有方案按字典序排列。
如果不存在满足要求的方案,则只输出一个 ,不需要输出其他内容。
测试样例
11
10
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 2 1 1 1 1
1 1 1 1 2 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1
1 1 2 1 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1
样例 1 解释
每种配料至少放 克, 种配料的下界之和为 。要凑出 ,只能是其中恰好一种配料放 克、其余九种各放 克,而放 克的那一种配料有 种选择,因此方案总数为 。
这 种方案依次对应「放 克」的位置从最后一种到第一种,恰好按字典序排列。
31
0
样例 2 解释
每种配料至多放 克, 种配料的上界之和为 ,因此美味程度不可能达到 ,方案总数为 。
提示
对于 的数据,。
每种配料的质量只能是 、 或 ,因此只有当 时方案总数才不为 ,且方案总数不超过 。