2013年8月10日

UVa 11308 - Bankrupt Baker

#include <cstdio>
#include <cctype>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;

struct Recipe {
  Recipe (char * name, int cost) : name(name), cost(cost) {}
  bool operator<(const Recipe & other) const {
    return (cost != other.cost) ? (cost < other.cost) : (name < other.name);
  }
  string name;
  int cost;
};

void prtUp(char * s) {
  char * p = s;
  while (*p) {
    putchar(toupper(*p++));
  }
  puts("");
}

int main() {
  char s[9999];
  gets(s);
  int t;
  sscanf(s, "%d", &t);
  while (t--) {
    gets(s);
    prtUp(s);
    gets(s);
    int m, n, b;
    sscanf(s, "%d%d%d", &m, &n, &b);
    map<string, int> price;
    while (m--) {
      gets(s);
      char name[99];
      int c;
      sscanf(s, "%s%d", name, &c);
      price[name] = c;
    }
    vector<Recipe> ans;
    while (n--) {
      char recipe[99];
      gets(recipe);
      gets(s);
      int k;
      sscanf(s, "%d", &k);
      int cost = 0;
      while (k--) {
        gets(s);
        char name[99];
        int x;
        sscanf(s, "%s%d", name, &x);
        cost += price[name] * x;
      }
      if (cost <= b) {
        ans.PB(Recipe(recipe, cost));
      }
    }
    sort(ans.begin(), ans.end());
    if (ans.size()) {
      for (int i = 0; i < ans.size(); i++) {
        puts(ans[i].name.c_str());
      }
    } else {
      puts("Too expensive!");
    }
    puts("");
  }
  return 0;
}

沒有留言:

張貼留言