A40957. 斗地主大师
填空题
困难
知识点
题目描述
斗地主大师
题目描述
斗地主大师今天有P个欢乐豆，他夜观天象，算出了一个幸运数字Q，如果他能有恰好Q个欢乐豆，就可以轻松完成程设大作业了。
斗地主大师显然是斗地主大师，可以在斗地主的时候轻松操控游戏的输赢。
1.他可以轻松赢一把，让自己的欢乐豆变成原来的Y倍
2.他也可以故意输一把，损失X个欢乐豆(注意欢乐豆显然不能变成负数，所以如果手里没有X个豆就不能用这个能力)
而斗地主大师还有一种怪癖，扑克除去大小王只有52张，所以他一天之内最多只会打52把斗地主。
斗地主大师希望你能告诉他，为了把P个欢乐豆变成Q个，他至少要打多少把斗地主？
输入
第一行4个正整数 P,Q,X,Y 0< P,X,Q <= 2^31, 1< Y <= 225
输出
输出一个数表示斗地主大师至少要用多少次能力 如果打了52次斗地主也不能把P个欢乐豆变成Q个，请输出一行 “Failed”
样例输入
输入样例1：
2 2333 666 8
输入样例2：
1264574 285855522 26746122 3
样例输出
输出样例1：
Failed
输出样例2：
33
提示
可以考虑深搜 要用long long
参考答案
#include<bits/stdc++.h>
using namespace std;
class Solution {
private:
int P;
int Q;
int X;
int Y;
int min_ok_play_count; //最少需要打多少次牌
int max_play_count; //打牌的最大次数
//t：当前有多少个欢乐豆
void dfs(int step, long long t){
if(step > 52) return;
//剪枝，如果t大于Q的时候再翻Y倍，那么后面全是X操作都没用
if(t > Q + (52 - step) * X) return;
if(t == Q) {
min_ok_play_count = min(min_ok_play_count, step);
return;
}
dfs(step + 1, t * Y);
if(t > X) dfs(step + 1, t - X);
}
public:
void load(int max_play_count){
scanf("%d%d%d%d", &P, &Q, &X, &Y);
//printf("%d %d %d %d ", P, Q, X, Y);
this->max_play_count = max_play_count;
}
void play_count(){
//设置比52大，用来判断52次内P变成Q是否可行
min_ok_play_count = max_play_count + 100;
dfs(0, P);
if(min_ok_play_count == max_play_count + 100){
printf("Failed");
}else{
printf("%d", min_ok_play_count);
}
}
};
int main(){
#ifdef LOCAL
freopen("202209_5_2.in", "r", stdin);
#endif
Solution s;
s.load(52);
s.play_count();
return 0;
}
上一题
下一题