[UVA] 11308 - Bankrupt Baker＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2013-06-29 21:50:57| 人819| 回0 | 上一篇 | 下一篇

[UVA] 11308 - Bankrupt Baker

推 0 收藏 0 0 站台

Problem B

BANKRUPT BAKER

Wolfgang Puck has an extensive collection of cake recipes. They are separated into different binders depending on the type of cake. Although Wolfgang has restaurant franchises all over the world, he is in a period of hard times and is struggling to afford ingredients for his cakes. What cakes can he create with his small budget?

Input

On the first line you are given t (1 ≤ t ≤ 100), the number of binders. Each binder begins with title, the name of the binder, then on the next line m n b (1 ≤ m, n ≤ 100, 1 ≤ b ≤ 10⁶) where b is Wolfgang's budget in dollars. The next m lines are given as "ingredient c" (see sample input) where c (0 ≤ c ≤ 5000) is the price in dollars for one unit of ingredient.

Then follow n recipes. Each recipe begins with name on a line of its own, then on the very next line k (1 ≤ k ≤ 100). The following k lines are of the form "requirement x" (see sample input) where x is the number of units of the ingredient requirement used in the recipe name.

Output

For each binder, output the name of the binder in uppercase letters then on separate lines a list of recipes within Wolfgang's budget in increasing order of cost. If no such recipe exists, print "Too expensive!". If recipes have the same cost print them in lexicographical order. Print a blank line after each binder.

Sample Input

2 My Favourite Cheesecake 8 3 100 sugar 4 water 0 lemonjuice 3 creamcheese 20 vanilla 5 egg 5 cream 10 strawberry 5 Strawberry Whipped Cream 2 cream 5 strawberry 3 Scrumptious Caramel Topping 3 sugar 6 water 3 lemonjuice 1 Secret Cheesecake Base 5 creamcheese 3 sugar 5 vanilla 1 egg 6 cream 1 Million Dollar Cakes 3 1 999999 costlyflour 500 gold 4500 diamond 5000 Display Cake - Do Not Eat! 3 costlyflour 100 gold 100 diamond 100

Output for the Sample Input

MY FAVOURITE CHEESECAKE Scrumptious Caramel Topping Strawberry Whipped Cream MILLION DOLLAR CAKES Too expensive!

Sean McIntyre
Calgary Collegiate Programming Contest 2007

目描述：
一食的名, 面有一些蛋糕的食, 而手上有一些算, 同你每材料的,
接著告你每蛋糕分的材料量, 出可以做出的蛋糕, 出的候按照低到高,
相同的候按照蛋糕名的字典序出。

食的名一律成大。

#include <stdio.h>
#include <set>
#include <map>
#include <iostream>
using namespace std;
struct E {
    string name;
    int cost;
    bool operator<(const E & a) const {
        if(cost != a.cost)
            return cost < a.cost;
        return name.compare(a.name) < 0;
    }
};
int main() {
    int testcase;
    char name[105], foo[105], name2[105];
    scanf("%d", &testcase);
    while(getchar() != '\n');
    while(testcase--) {
        gets(name);
        int i;
        for(i = 0; name[i]; i++)
            if(name[i] >= 'a' && name[i] <= 'z')
                name[i] -= 32;
        puts(name);
        gets(foo);
        int n, m, cost, x, q;
        map<string, int> R;
        set<E> ret;
        E tmp;
        sscanf(foo, "%d %d %d", &n, &m, &cost);
        while(n--) {
            gets(foo);
            sscanf(foo, "%s %d", name, &x);
            R[name] = x;
        }
        while(m--) {
      &nbs;     gets(name);
            gets(foo);
            sscanf(foo, "%d", &q);
            int cc = 0;
            while(q--) {
                gets(foo);
                sscanf(foo, "%s %d", name2, &x);
                cc += R[name2]*x;
            }
            if(cc <= cost) {
                tmp.name = name;
                tmp.cost = cc;
                ret.insert(tmp);
            }
        }
        for(set<E>::iterator it = ret.begin();
            it != ret.end(); it++) {
            cout << it->name << endl;
        }
        if(ret.size() == 0)
            puts("Too expensive!");
        puts("");
    }
    return 0;
}