一、编程题
1、1.鸡兔同笼
一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。
时间限制：1000
内存限制：65536
输入
一行，一个正整数a (a < 32768)。
输出
一行，包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开。 如果没有满足要求的答案，则输出两个0，中间用一个空格分开。
样例输入
```
20
```
样例输出
```
5 10
```
参考答案：
略
解析：【喵呜刷题小喵解析】这个问题是一个经典的鸡兔同笼问题，可以通过数学方法来解决。首先，我们定义变量a为脚的总数。1. 最少动物数：* 假设笼子里的动物都是鸡，那么每只动物有2只脚，所以最少动物数就是脚的总数a除以2，即a/2。* 如果a是奇数，那么至少还有一只兔子，因为兔子有4只脚，所以最少动物数应该是a/2 + 1。2. 最多动物数：* 假设笼子里的动物都是兔子，那么每只动物有4只脚，所以最多动物数就是脚的总数a除以4再乘以2，即a/4 * 2。* 如果a是偶数，那么最多动物数就是a/4 * 2。* 如果a是奇数，那么最多动物数应该是a/4 * 2 + 1，因为至少还有一只鸡。最后，我们输出最少动物数和最多动物数。如果a小于2（即a/2或a/4的结果为0），则最少动物数和最多动物数都应该是1。
2、2.猴子吃桃
海滩上有一堆桃子，N只猴子来分。第一只猴子把这堆桃子平均分为N份，多了一个，这只猴子把多的一个扔入海中，拿走了一份。第二只猴子接着把剩下的桃子平均分成N份，又多了一个，它同样把多的一个扔入海中，拿走了一份。第三、第四、……，第N只猴子仍是最终剩下的桃子分成N份，扔掉多了的一个，并拿走一份。
编写程序，输入猴子的数量N，输出海滩上最少的桃子数，使得每只猴子都可吃到桃子。
时间限制：3000
内存限制：65536
输入
一个整数N。
输出
输出当猴子数量为N时海滩上最少的桃子数。结果保证在int型范围内。
样例输入
```
2
```
样例输出
```
7
```
参考答案：
略
解析：【喵呜刷题小喵解析】本题是一道经典的猴子吃桃问题，可以通过二分查找的方式求解。首先，我们设定一个区间[1, 10^9]，然后在这个区间内通过二分查找找到最小的桃子数。对于每一个中间值mid，我们可以判断如果(mid-1)%N == 0，则说明每只猴子都能分到桃子，此时我们缩小搜索范围为[left, mid]，否则我们扩大搜索范围为[mid+1, right]。最终，当left和right相等时，我们就找到了最小的桃子数。在Python中，我们可以定义一个函数min_peaches(N)来实现上述算法，然后在主函数中读入N，并输出最小的桃子数。
3、3.扩号匹配问题
在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.
时间限制：3000
内存限制：65536
输入
输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过100
输出
对每组输出数据，输出两行，第一行包含原始输入字符，第二行由"$","?"和空格组成，"$"和"?"表示与之对应的左括号和右括号不能匹配。
样例输入
```
((ABCD(x)
)(rttyy())sss)(
```
样例输出
```
((ABCD(x)
$$
)(rttyy())sss)(
? ?$
```
参考答案：
略
解析：【喵呜刷题小喵解析】：这个问题是一个经典的括号匹配问题，可以通过使用栈来解决。首先，我们定义一个空栈。然后，我们遍历输入的字符串。对于每个字符，如果它是左括号，我们就把它推入栈中。如果它是右括号，我们就检查栈是否为空。如果栈不为空，我们就从栈中弹出一个元素，表示找到了一个匹配的括号。如果栈为空，我们就找到了一个无法匹配的右括号，返回原始字符串和标记后的字符串。如果遍历完字符串后栈中还有元素，那就表示还有未匹配的左括号，返回原始字符串和全是空格的标记字符串。最后，如果没有未匹配的括号，就返回空字符串和全是"$"的标记字符串。在找到无法匹配的括号后，我们用"$"和"?"来标记它们，并输出原始字符串和标记后的字符串。在输入部分，我们使用了一个无限循环来读取输入，直到读到空字符串为止。这样可以处理多组输入数据。
4、4.上台阶
楼梯有n(100 > n > 0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。
时间限制：1000
内存限制：65536
输入
输入的每一行包括一组测试数据，即为台阶数n。最后一行为0，表示测试结束。
输出
每一行输出对应一行输入的结果，即为走法的数目。
样例输入
```
1
2
3
4
0
```
样例输出
```
1
2
4
7
```
参考答案：
略
解析：【喵呜刷题小喵解析】这是一个经典的动态规划问题，可以使用动态规划算法来解决。首先，我们定义一个数组dp，其中dp[i]表示上i阶台阶的不同走法数目。对于i=1, 2, 3，走法数目分别为1, 2, 4。对于i>=4，走法数目等于上i-1阶、i-2阶和i-3阶的走法数目之和。最后，我们遍历输入的台阶数，依次输出对应的走法数目即可。时间复杂度为O(n)，空间复杂度为O(n)。
5、5.田忌赛马
在田忌赛马的故事中，孙膑用自己的下等马对战对手的上等马，自己上等马对阵对手的中等马，自己的中等马对阵对手的下等马，从而赢得了胜利。现在即将进行的是N匹马的赛马比赛。双方队伍的马各分为N等。已知只有当我方马的等级比对方马等级高X等以上（包含X）时，我方才可以取得这场比赛的胜利。如果在N场比赛中我方的胜场数大于对方，则我方取得最终的胜利。现在已知对方这N场比赛的出战方案，请计算所有令我方最终获胜的出战方案。
时间限制：1000
内存限制：65536
输入
第一行两个整数，N和X。N≤9, 0 ≤ X < N。 第二行N个正整数，A(1)....A(N)。A(i)表示第i场比赛对方马的等级，1≤i≤N。等级越高越强
输出
按字典序输出所有我方最终获胜的方案，每个方案一行。每行是N个正整数，第i个数表示我方第i场比赛马的等级。
样例输入
```
样例1输入
3 1
3 2 1
样例2输入
3 0
3 1 2
```
样例输出
```
样例1输出
1 3 2
样例2输出
1 2 3
1 3 2
2 1 3
3 1 2
3 2 1
```
参考答案：
略
解析：【喵呜刷题小喵解析】这道题是一道经典的编程题，需要使用深度优先搜索（DFS）算法来解决。首先，我们读取输入数据，包括N和X，以及对方马的等级序列A。然后，我们定义一个dfs函数，用于递归地搜索所有可能的出战方案。在dfs函数中，我们维护两个参数：cur_index表示当前要匹配的马的等级，cur_score表示当前我方的胜场数。在dfs函数中，我们遍历从N到1的所有马的等级，如果当前马的等级比对方马的等级高X以上，并且当前马的等级比前一个马的等级强，那么我们就交换当前马和该马的位置，并递归地搜索下一个马的等级。在递归返回后，我们再将当前马和该马的位置交换回来，以便下一次循环。最后，当所有马的等级都匹配完毕后，如果当前我方的胜场数大于0，那么我们就将当前对方马的等级序列加入结果列表中。最后，我们将结果列表按照字典序排序，并输出所有最终获胜的方案。需要注意的是，由于题目要求按照字典序输出所有最终获胜的方案，因此在输出时需要将对方马的等级序列反转，以便按照字典序输出。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
