传统题 1000ms 256MiB

贪心找零的陷阱

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

贪心找零的陷阱

题目描述

在某个国家的货币系统中,流通着三种面额的硬币:{1,A,B}\{1, A, B\}(保证 1<A<B1 < A < B)。 人们在日常找零钱时,通常习惯使用“贪心”策略:每次都优先拿出一枚不超过当前剩余金额的最大面额硬币,直到找完为止。

但这种直觉策略并不总是最优的。 例如在面额为 {1,3,4}\{1, 3, 4\} 的系统中: 若需要找零 66 元:

  • 贪心策略会先挑最大的一枚 44 元,剩下的 22 元只能用两枚 11 元,总共用了 33 枚(4+1+14 + 1 + 1);
  • 但最优策略显然是挑两枚 33 元(3+33 + 3),只需要 22 枚硬币! 在这里,金额 66 就是让贪心策略“失效”(使用的硬币数多于最少可能枚数)的最小正整数反例。

现在给出另外两枚硬币的面额 AA 和 BB。 请你判断:该硬币系统对于所有正整数金额,贪心策略是否都能给出最少硬币数? 如果对于任意金额贪心策略都始终最优,输出 -1; 如果存在某些金额会导致贪心策略失效,请输出其中最小的正整数金额!

输入格式

一行两个整数 AA 和 BB。

输出格式

若贪心始终最优输出 -1;否则输出最小的反例金额。

样例

3 4
6
2 4
-1

样例解释

  • 样例 1:即题目描述中的情况,金额 6 为最小反例。
  • 样例 2:面额为 {1,2,4}\{1, 2, 4\} 时,每个大面额都是小面额的倍数,可以证明贪心对于任意金额都能找出最少硬币数,故输出 -1。

数据规模与提示

对于 100%100\% 的数据,满足 2≤A<B≤1092 \le A < B \le 10^9。 请使用 64 位整数。

「Attention Is All You Need」

未参加
状态
已结束
规则
IOI
题目
9
开始于
2026-10-3 21:00
结束于
2026-10-7 21:00
持续时间
96 小时
主持人
参赛人数
21