20250727

admin

斗地主大师今天有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”

admin

[C] 纯文本查看 复制代码

#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;

struct State {
    long long beans;
    int steps;
};

int minOperations(long long P, long long Q, long long X, int Y) {
    queue<State> q;
    unordered_set<long long> visited;
    
    q.push({P, 0});
    visited.insert(P);
    
    while (!q.empty()) {
        State current = q.front();
        q.pop();
        
        if (current.beans == Q) {
            return current.steps;
        }
        
        if (current.steps >= 52) {
            continue;
        }
        
        // 尝试乘法操作
        long long next = current.beans * Y;
        if (next <= Q * Y && visited.find(next) == visited.end()) {
            visited.insert(next);
            q.push({next, current.steps + 1});
        }
        
        // 尝试减法操作
        if (current.beans >= X) {
            next = current.beans - X;
            if (next >= 0 && visited.find(next) == visited.end()) {
                visited.insert(next);
                q.push({next, current.steps + 1});
            }
        }
    }
    
    return -1;
}

int main() {
    long long P, Q, X;
    int Y;
    cin >> P >> Q >> X >> Y;
    
    int result = minOperations(P, Q, X, Y);
    if (result != -1) {
        cout << result << endl;
    } else {
        cout << "Failed" << endl;
    }
    
    return 0;
}