結果

問題 No.158 奇妙なお使い
コンテスト
ユーザー Hachimori
提出日時 2015-03-04 00:31:08
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,440 bytes
コンパイル時間 909 ms
コンパイル使用メモリ 81,320 KB
実行使用メモリ 31,360 KB
最終ジャッジ日時 2024-06-24 01:19:29
合計ジャッジ時間 8,329 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 17 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;


class Data {
public:
    int n1000, n100, n1;
    Data(){}
    Data(int n1000, int n100, int n1):
        n1000(n1000), n100(n100), n1(n1){}

    bool operator< (const Data &opp) const {
        if (n1000 != opp.n1000) return n1000 < opp.n1000;
        if (n100 != opp.n100) return n100 < opp.n100;
        return n1 < opp.n1;
    }
};


Data init;
int payA, chgN1000A, chgN100A, chgN1A;
int payB, chgN1000B, chgN100B, chgN1B;

void read() {
    cin >> init.n1000 >> init.n100 >> init.n1;
    cin >> payA >> chgN1000A >> chgN100A >> chgN1A;
    cin >> payB >> chgN1000B >> chgN100B >> chgN1B;
}


Data doPay(int toPay, int chgN1000, int chgN100, int chgN1, Data curr) {
    int remain = toPay;
    int n;

    n = min(remain / 1000, curr.n1000);
    remain -= n * 1000;
    curr.n1000 -= n;

    n = min(remain / 100, curr.n100);
    remain -= n * 100;
    curr.n100 -= n;

    n = min(remain, curr.n1);
    remain -= n;
    curr.n1 -= n;
    
    if (remain == 0)
        return Data(curr.n1000 + chgN1000, curr.n100 + chgN100, curr.n1 + chgN1);
    else
        return Data(-1, -1, -1);
}


class mycmp {
public:
    int operator()(const Data &a, const Data &b) const {
        return (a.n1000 * 1000 + a.n100 * 100 + a.n1) -
               (b.n1000 * 1000 + b.n100 * 100 + b.n1);
    }
};

void work() {
    priority_queue<Data, vector<Data>, mycmp> Q;
    map<Data, int> d2cnt;
    
    Q.push(init);
    d2cnt[init] = 0;
    
    while (!Q.empty()) {
        Data curr = Q.top();
        Q.pop();
        
        Data next;

        // A
        next = doPay(payA, chgN1000A, chgN100A, chgN1A, curr);
        
        if (next.n1000 != -1) {
            if (!d2cnt.count(next) || d2cnt[next] < d2cnt[curr] + 1) {
                d2cnt[next] = d2cnt[curr] + 1;
                Q.push(next);
            }
        }
        
        // B
        next = doPay(payB, chgN1000B, chgN100B, chgN1B, curr);

        if (next.n1000 != -1) {
            if (!d2cnt.count(next) || d2cnt[next] < d2cnt[curr] + 1) {
                d2cnt[next] = d2cnt[curr] + 1;
                Q.push(next);
            }
        }
    }

    int ans = 0;
    for (map<Data, int>::iterator it = d2cnt.begin(); it != d2cnt.end(); ++it)
        ans = max(ans, it->second);
    cout << ans << endl;
}


int main() {
    read();
    work();
    return 0;
}
0