341002 - 百鸡百钱
Time Limit : 1 秒
Memory Limit : 128 MB
百鸡百钱问题是我国古代数学家张丘建在《算经》一书中提出的数学问题,原问题是这样:鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一。百钱买百鸡,问鸡翁、鸡母、鸡雏各几何? 用我们现在的话说,即公鸡5元一只,母鸡3元一只,小鸡1元三只,问100元钱买100只鸡, 公鸡、母鸡、小鸡各多少只?
现在我们的问题是这样,用x元买x只鸡,问公鸡、母鸡、小鸡各多少只?
Input
一行一个整数x(0 < x ≤ 500),表示需要用x元买x只鸡。
Output
一行空格隔开的三个大于0的整数,依次为公鸡、母鸡、小鸡的数量。如果有多种情况, 则输出公鸡数量最多的情况;公鸡数量相同,母鸡和小鸡有多种情况的,则输出母鸡数量最多的。如果给定的x元买不到x只鸡,则输出no。
Examples
Input
100
Output
12 4 84
Input
20
Output
no
Hint
根据题意,我们只要穷举公鸡、母鸡和小鸡的数量i、j、k,因为要买X只鸡,而且三种鸡的数量要大于0,所以我们可以界定i、j、k的穷举范围都是1-X,然后我们判定鸡的总数i + j + k是否为x只,花费的钱i5+j3+k/3是否为x元,同时,小鸡的数量是否为3的倍数,如果满足这几个条件,那么就是一个可行解。
但要注意的是,题目要求在所有可行解中,要求公鸡的数量最多,公鸡数量相同时,母鸡的数量最多,所以我们可以把公鸡、母鸡的穷举顺序从1到x的递增,转换为从x到1的递减,这样找到的第一个解就是所求解。