KEDA#P0843. 换可乐

题目描述

Marjar 可乐现在有促销活动！为了吸引更多的顾客，Marjar公司的老板Edward决定推出一项促销活动：顾客向公司退回x个空可乐瓶或y个可乐瓶盖，即可免费获得一整瓶Marjar可乐！ 现在，Alice 有a个空的可乐瓶和b 个可乐瓶盖，她想喝尽可能多的可乐瓶。你知道她能喝多少满瓶的Marjar可乐吗？

请注意，一瓶可乐由一个可乐瓶和一个瓶盖组成。

输入

只有一行，包含四个整数x , y , a , b 。它们的含义如上所述。

输出

一个整数，表示 Alice 可以喝的可乐瓶数。如果可以喝无数瓶可乐，请打印“INF”（不带引号）。

样例

输入数据 1

1 3 1 1

输出数据 1

INF

输入数据 2

4 3 6 4

输出数据 2

4

数据规模与约定

测试点：10个测试点，每个测试点得10分。

测试限制：每个测试点时间限制1s，内存限制128M。

数据规模

对于 100% 的数据： (1 ≤ x , y , a , b ≤ 100)

思路

对于这题我们要注意两点：

1.0

当x=1&&a>=1或y=1&&b>=1，只要这两点满足一点，就可以喝无数瓶，直接输出“INF”；

2.0

当x=2&&y=2&&a>=2&&b>=1，或反过来也可以喝无数瓶；

代码

#include<bits/stdc++.h>
using namespace std;
long long x,y,a,b,sum=0;
void dfs(){
	if(a<x&&b<y)return;//如果瓶子瓶盖都不能换的话直接返回
	if(a>=x){
		a-=x,sum++,a++,b++;
		dfs();
	}
	if(b>=y){
		b-=y,sum++,a++,b++;
		dfs();
	}
}
int main(){
	cin>>x>>y>>a>>b;
	if((x==1&&a>=1)||(y==1&&b>=1)){
		cout<<"INF";
		return 0;
	}
	if((x==2&&a>=2)||(y==2&&b>=2)){
		cout<<"INF";
		return 0;
	}
	if((x==1&&a==0&&b>=y)||(y==1&&b==0&&a>=x)){
		cout<<"INF";
		return 0;
	}
	dfs();//递归
	cout<<sum;
	return 0;
}