牛客题解 武藏牌牛奶促销

链接：https://ac.nowcoder.com/acm/problem/13592

来源：牛客网

题解

作者 岛田小雅

看到这一题我第一反应想直接模拟，看了下范围感觉可行，但是如果遇到无法判断的 INF 就会导致 TLE。

那么怎么科学地判断它能不能无限续杯呢？

首先，因为小萌老师手里一开始一定有一个瓶子，而且他不能空手套白狼，所以我们能很轻易地得出只要一个瓶子或者一个盖子能换一瓶牛奶，小萌老师就可以无限续杯。

这样交一发，得到一个 TLE。

然后我造了下面的这个数据：

2 2 100 100

用这组数据调试会发现，瓶子和盖子可以互补。只要小萌老师一次用瓶子，一次用盖子，他就可以无限续杯。这种怎么判断呢？我懒得想。因为本题数据范围很小，我们可以换种思路。一旦出现重复的盖子和瓶子数量组合，说明小萌老师可以无限续杯。那么我们可以直接记录当前组合有没有出现过。如果遇到之前出现过的组合，就直接输出 INF。记录可以用 map，也可以用二维 bool 数组。

AC 代码

作者 岛田小雅

#include <bits/stdc++.h>
using namespace std;

int x, y, a, b;
int ans;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    while(cin >> x >> y >> a >> b)
    {
        map<pair<int,int>,bool> mp; // 用map记录组合。如果用二维bool数组一定要每次循环清空它。
        if(x==1 || y==1) goto INF;
        ans = 0;
        while(a>=x || b>=y)
        {
            if(mp[pair<int,int>(a,b)]) goto INF;
            mp[pair<int,int>(a,b)] = true;
            ans++;
            a++, b++;
            if(a >= x) a -= x;
            else if(b >= y) b -= y;
        }
        cout << ans << '\n';
        continue;
        INF: cout << "INF\n";
    }
    return 0;
}