【思维】Marjar Cola

Marjar Cola is on sale now! In order to attract more customers, Edward, the boss of Marjar Company, decides to launch a promotion: If a customer returns x empty cola bottles or y cola bottle caps to the company, he can get a full bottle of Marjar Cola for free!

Now, Alice has a empty cola bottles and b cola bottle caps, and she wants to drink as many bottles of cola as possible. Do you know how many full bottles of Marjar Cola she can drink?

Note that a bottle of cola consists of one cola bottle and one bottle cap.

Input
There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 100), indicating the number of test cases. For each test case:

The first and only line contains four integers x, y, a, b (1 ≤ x, y, a, b ≤ 100). Their meanings are described above.

Output
For each test case, print one line containing one integer, indicating the number of bottles of cola Alice can drink. If Alice can drink an infinite number of bottles of cola, print “INF” (without the quotes) instead.

Sample Input
2
1 3 1 1
4 3 6 4
Sample Output
INF
4
Hint
For the second test case, Alice has 6 empty bottles and 4 bottle caps in hand. She can return 4 bottles and 3 caps to the company to get 2 full bottles of cola. Then she will have 4 empty bottles and 3 caps in hand. She can return them to the company again and get another 2 full bottles of cola. This time she has 2 bottles and 2 caps in hand, but they are not enough to make the exchange. So the answer is 4.

x个空瓶子或者y个瓶盖可以换一个饮料(该饮料产出一个瓶盖和一个瓶子),一开始有a个瓶子和b个瓶盖,问最多能换多少。

分析:先考虑无限兑换的情况:

1.只需要一个瓶子或者瓶盖就可以换一个(因为a,b>=1)所以无限兑换。

2.每次需要两个瓶盖或者两个瓶子进行兑换,这样的话,只要(a,b>=2)然后每两个作为一组便可以完成无限兑换。

对于一般情况:进行模拟即可。

AC代码:

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int main()
{
  int t = 0;
  cin >> t;
  while (t--)
  {
    int x, y, a, b;
    cin >> x >> y >> a >> b;
    if (x==1||y==1||x==2&&y==2&&(a>=2||b>=2))
    {
      cout << "INF" << endl;
      continue;
    }
    long long ans = 0;
    while (true)
    {
      if (a < x&&b < y)
        break;
      int consum_a = a / x;//向下取整
      int consum_b = b / y;
      ans += consum_a + consum_b;
      a = a - consum_a * x + consum_a + consum_b;
      b = b - consum_b * y + consum_a + consum_b;
    }
    cout<<ans<<endl;
  }
  return 0;
}

 

发表评论

电子邮件地址不会被公开。