贪心找零的陷阱
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
贪心找零的陷阱
题目描述
在某个国家的货币系统中,流通着三种面额的硬币:(保证 )。 人们在日常找零钱时,通常习惯使用“贪心”策略:每次都优先拿出一枚不超过当前剩余金额的最大面额硬币,直到找完为止。
但这种直觉策略并不总是最优的。 例如在面额为 的系统中: 若需要找零 元:
- 贪心策略会先挑最大的一枚 元,剩下的 元只能用两枚 元,总共用了 枚();
- 但最优策略显然是挑两枚 元(),只需要 枚硬币! 在这里,金额 就是让贪心策略“失效”(使用的硬币数多于最少可能枚数)的最小正整数反例。
现在给出另外两枚硬币的面额 和 。
请你判断:该硬币系统对于所有正整数金额,贪心策略是否都能给出最少硬币数?
如果对于任意金额贪心策略都始终最优,输出 -1;
如果存在某些金额会导致贪心策略失效,请输出其中最小的正整数金额!
输入格式
一行两个整数 和 。
输出格式
若贪心始终最优输出 -1;否则输出最小的反例金额。
样例
3 4
6
2 4
-1
样例解释
- 样例 1:即题目描述中的情况,金额 6 为最小反例。
- 样例 2:面额为 时,每个大面额都是小面额的倍数,可以证明贪心对于任意金额都能找出最少硬币数,故输出
-1。
数据规模与提示
对于 的数据,满足 。 请使用 64 位整数。
「Attention Is All You Need」
- 状态
- 已结束
- 规则
- IOI
- 题目
- 9
- 开始于
- 2026-10-3 21:00
- 结束于
- 2026-10-7 21:00
- 持续时间
- 96 小时
- 主持人
- 参赛人数
- 21