結果

問題 No.158 奇妙なお使い
ユーザー HachimoriHachimori
提出日時 2015-03-04 00:37:20
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 619 ms / 5,000 ms
コード長 2,441 bytes
コンパイル時間 2,146 ms
コンパイル使用メモリ 81,472 KB
実行使用メモリ 31,232 KB
最終ジャッジ日時 2024-06-28 22:31:51
合計ジャッジ時間 2,225 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 619 ms
31,232 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 AC 1 ms
6,940 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 3 ms
6,940 KB
testcase_16 AC 1 ms
6,940 KB
testcase_17 AC 6 ms
6,944 KB
testcase_18 AC 59 ms
7,424 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 2 ms
6,944 KB
testcase_21 AC 17 ms
6,944 KB
testcase_22 AC 18 ms
6,940 KB
testcase_23 AC 2 ms
6,940 KB
testcase_24 AC 2 ms
6,940 KB
testcase_25 AC 1 ms
6,940 KB
testcase_26 AC 1 ms
6,940 KB
testcase_27 AC 1 ms
6,940 KB
testcase_28 AC 2 ms
6,944 KB
testcase_29 AC 1 ms
6,940 KB
testcase_30 AC 4 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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:
    bool operator()(const Data &a, const Data &b) const {
        return (b.n1000 * 1000 + b.n100 * 100 + b.n1) >
               (a.n1000 * 1000 + a.n100 * 100 + a.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