GESP二级 - 购买文具：寻找最佳方案

GESP二级 - 购买文具：寻找最佳方案

时间限制： C/C++ 1000MS，其他语言 2000MS 内存限制： C/C++ 16MB，其他语言 32MB 难度： 中等

描述

新学年就要开始了，爸爸把N元钱给了小青，让他购买一批文具，并作了以下要求：只能买圆珠笔、铅笔和铅笔芯，并且每样至少买一支，总数要超过30支，而且钱要全部花完。

当小青去到文具店时，发现圆珠笔8角钱一支、铅笔2角钱一支、铅笔芯1角钱一支。小青怎么买才能符合爸爸的要求呢？请你编个程序帮他算出符合购买要求的所有方案总数。

输入描述

一个整数N，表示购买文具一共的元数。（1 <= N <= 50）

输出描述

一个整数，即符合购买要求的所有方案总数。

用例输入 1

8

用例输出 1

135

来源

思路：

根据题目要求，每样文具至少购买一支，总数要超过30支，且要花完所有的钱。

假设购买圆珠笔x支，铅笔y支，铅笔芯z支，则有以下约束条件：

1. x + y + z > 302. 8x + 2y + z <= N

其中，x，y，z为非负整数。

可以使用三层循环来枚举x，y，z的取值，然后判断是否满足约束条件。

**具体实现如下：**pythonN = int(input()) # 输入购买文具的元数

count = 0 # 符合购买要求的方案总数

for x in range(1, N//8 + 1): # 枚举圆珠笔的支数，至少1支 for y in range(1, (N-8x)//2 + 1): # 枚举铅笔的支数，至少1支 z = N - 8x - 2*y # 计算铅笔芯的支数 if z >= 1 and x + y + z > 30: # 判断是否满足约束条件 count += 1

print(count)

时间复杂度分析：

假设N为购买文具的元数，算法的时间复杂度为O(N^2)。