GESP二级：买鸡问题 - 优化你的购物计划

桐桐去购物：买鸡问题

桐桐周末陪妈妈到市场购物。她和妈妈来到一个买鸡的摊位，发现鸡的价格有三种：公鸡每只5元钱，母鸡每只3元钱，小鸡3只1元钱。妈妈就给桐桐出了一道计算题：如果用n元钱买m只鸡，问公鸡、母鸡和小鸡可以各买多少只？注意：必须把n元钱正好用完，且买的各种鸡的只数为大于等于0的整数。桐桐回到家里便拿起笔来认真计算，算了好久还没得出答案。聪明的你通过编写程序帮助桐桐找出结果好吗？

输入描述

只有1行，两个数n和m ( 0<n,m<=20000 )。

输出描述

有若干行，每行三个数，分别为公鸡、母鸡和小鸡的只数，用空格隔开，按照公鸡只数升序排列。

用例输入 1

100 100

用例输出 1

0 25 754 18 788 11 8112 4 84

解法一：暴力穷举

思路：遍历公鸡的数量x，母鸡的数量y，计算小鸡的数量z，判断是否满足条件，满足则输出。

时间复杂度：O(n^2)

空间复杂度：O(1)cpp#include using namespace std;

int main() { int n, m; cin >> n >> m; for (int x = 0; x <= n/5; x++) { for (int y = 0; y <= n/3; y++) { int z = m - x - y; if (x5 + y3 + z/3 == n && z%3 == 0 && z >= 0) { cout << x << ' ' << y << ' ' << z << endl; } } } return 0;}

解法二：数学推导

思路：根据题目中给的条件，可以得出以下几个方程：

1. 5x + 3y + z/3 = n2. x + y + z = m

其中，x表示公鸡的数量，y表示母鸡的数量，z表示小鸡的数量。

通过变量替换和方程约束，可以得出以下结果：

x = (7n - 4m) / 2y = (3m - n) / 2z = (4m - 7n) / 2

然后遍历x的范围，根据x的值计算出y和z，并判断是否满足条件输出。

时间复杂度：O(n)

空间复杂度：O(1)cpp#include using namespace std;

int main() { int n, m; cin >> n >> m; for (int x = 0; x <= n/5; x++) { int y = (3m - n) / 2 - x; int z = (4m - 7*n) / 2 + x; if (y >= 0 && z >= 0 && z%3 == 0) { cout << x << ' ' << y << ' ' << z << endl; } } return 0;