最新华为OD机试真题-卢小姐的生日礼物(200分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
最新华为OD机试D卷目录,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测
最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
🍓 卢小姐的生日礼物
问题描述
卢小姐即将过生日,她的朋友们打算为她准备一份特别的生日礼物。他们决定购买一些小礼品,并将它们装在一个漂亮的礼物盒中。
每个小礼品都有一个价格标签,上面写着该礼品的价格。为了让礼物看起来更有意义,他们希望选择的礼品价格之和正好等于卢小姐的生日年龄。
例如,如果卢小姐今年25岁,他们可以购买价格分别为10元、11元和4元的三个小礼品,因为10+11+4=25。
你的任务是帮助他们找到一种购买方案,使得所选礼品的价格之和等于卢小姐的生日年龄,并且所选礼品的价格是连续的正整数。如果存在多种方案,请输出价格最小的那些礼品。如果找不到合适的方案,请输出"N"。
输入格式
输入一个正整数 ,表示卢小姐的生日年龄。
输出格式
如果存在合适的购买方案,请按照以下格式输出:
n=x_1+x_2+...+x_k
其中 是所选礼品的价格,且满足
,并且
。
如果不存在合适的方案,请输出"N"。
样例输入
21
样例输出
21=10+11
样例解释
21可以分解为以下几种形式:
- 21=10+11
- 21=1+2+3+4+5+6
- 21=6+7+8
其中,21=10+11是最短的分解序列。
数据范围
题解
我们可以利用数学方法来解决这个问题。设 为卢小姐的生日年龄,我们需要找到一个正整数
,使得
。这个等式表示
可以被分解为从
到
的连续正整数之和。
为了找到最小的 ,我们可以将等式两边同乘以
,得到
。这个等式的解可以通过求解一元二次方程
来获得。
如果该方程有整数解,那么我们就可以根据 的值输出对应的连续正整数序列。否则,我们输出"N"。
需要注意的是,由于 必须大于
,所以我们只需要考虑
的正整数解即可。
参考代码
- Python
n = int(input())
n2 = n * 2
for k in range(2, int(n2 ** 0.5 + 1)):
if n2 % k == 0:
a2 = n2 // k - k + 1
if a2 % 2 == 0:
a = a2 // 2
res = [str(a + i) for i in range(k)]
print(f"{n}={'+'.join(res)}")
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测