11308 - Bankrupt Baker

[sapnil]

/* 11308 */

I get wrong answer,can any one tell me whats wrong in my code:

Code: Select all

//Removed

Thanks
Keep posting
Sapnil

[sapnil]

Finally i got acc


Thanks
keep posting
Sapnil

[Lomir]

And why do you get WA at first?
I also got WA, but do not know why....

[lovemagic]

i dont know why i m getting WA. somebody help me?

Code: Select all

#pragma warning(disable:4786)
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <map>
#include <stdlib.h>
using namespace std;

struct Recipe{
	char name[105];
	char lower[105];
	int p;
}recipe[105];

int sort(const void *a,const void *b) { 
    Recipe aa=*(Recipe*)a,bb=*(Recipe*)b; 
    if(aa.p!=bb.p) 
        return aa.p-bb.p;  
    return strcmp(aa.lower,bb.lower); 
} 

void make_lower(int C){
    int i;
    for(i=0;i<strlen(recipe[C].name);i++){
		if(recipe[C].name[i]>='A' && recipe[C].name[i]<='Z')
			recipe[C].lower[i]=recipe[C].name[i]+32;
		else
			recipe[C].lower[i]=recipe[C].name[i];
    }
	recipe[C].lower[i]=NULL;
}

map<string,int>binder;
char title[105],faltu[5],ingredient[105],r_name[105];
int m,n,b,c,k,x,Cost;
int Count;

int main(){
	int T;
	int i,j;
	scanf("%d",&T);
	for(;T>0;T--){
		binder.clear();
		gets(faltu);
		gets(title);
		for(i=0;i<strlen(title);i++)
			if(title[i]>='a' && title[i]<='z')
				title[i]-=32;
		printf("%s\n",title);
		Count=0;
		scanf("%d %d %d",&m,&n,&b);
		for(i=0;i<m;i++){
			scanf("%s %d",ingredient,&c);
			binder[ingredient]=c;
		}
		for(i=0;i<n;i++){
			Cost=0;
			gets(faltu);
			gets(r_name);
			scanf("%d",&k);
			for(j=0;j<k;j++){
				scanf("%s %d",ingredient,&x);
				Cost+=(binder[ingredient]*x);
			}
			if(Cost<=b){
				strcpy(recipe[Count].name,r_name);
				make_lower(Count);
				recipe[Count].p=Cost;
				Count++;
			}
		}
		if(Count==0){
			printf("Too expensive!\n");
			continue;
		}
		qsort(recipe,Count,sizeof(recipe[0]),sort);
		for(i=0;i<Count;i++)
			printf("%s\n",recipe[i].name);
		printf("\n");
	}
	return 0;
}

[sclo]

I don't think it says to make the recipe lowercase.
Also, consider learning how to use c++ stl. It makes your code a little easier to read and much faster to type.

As an aside, there are functions toupper(int) and tolower(int) that converts to uppercase/lowercase defined already.

[sapnil]

To Lomir

I get WR first because i print \n between two binder.
But after that i print \n for each binder & get Acc.

I miss this line:

Code: Select all

Print a blank line after each binder.

Thanks
Keep posting
Sapnil

[Lomir]

To sapnil:
Thanks, I had the same bug ))
However I think it must be a presentation error, but not WA.

[lovemagic]

to sclo,

i used the make_lower function to compare lexicographically when the cost of more than one recipe are equal. as far as i know, in lexicographical order 'a' & 'A' are same.

thanx for ur reply. can u give me some test case or tell me if u see any wrong in my code?

[sclo]

to sclo,

i used the make_lower function to compare lexicographically when the cost of more than one recipe are equal. as far as i know, in lexicographical order 'a' & 'A' are same.

thanx for ur reply. can u give me some test case or tell me if u see any wrong in my code?

In all contest problem, the lex order of 'a' and 'A' are NOT the same unless they explicitly say so. Also, there could be nonalphabetic characters present, such as spaces, and they are also compared using their ASCII values.
So if you have a vector<pair<int,string> > a, then calling sort(a.begin(),a.end()) would sort a in the required order. So you only need to print the second part of each elements in a.
Also I would consider using 64bit integers here, since there is no bounds on the number of units of ingredient required by each recipe.

[baodog]

64 bit integer is not needed here. 32 bits works.

[lovemagic]

finally got AC......
my q-sort function works well. ya,there's no need to check the "uppercase" & "lowercase" matter in this problem.Though the word "lexicographically" means "order in the dictionary" according to the POD.
The mistake was in the part

Code: Select all

      if(Count==0){ 
         printf("Too expensive!\n"); 
         continue; 
      } 

this should be

Code: Select all

      if(Count==0){ 
         printf("Too expensive!\n\n"); 
         continue; 
      } 

But i think this should reply a PE not WA.

[lovemagic]

finally got AC......
my q-sort function works well. ya,there's no need to check the "uppercase" & "lowercase" matter in this problem.Though the word "lexicographically" means "order in the dictionary" according to the POD.
The mistake was in the part

Code: Select all

      if(Count==0){ 
         printf("Too expensive!\n"); 
         continue; 
      } 

this should be

Code: Select all

      if(Count==0){ 
         printf("Too expensive!\n\n"); 
         continue; 
      } 

But i think this should reply a PE not WA.

[jjtse]

Can anyone tell me what's wrong with my code? It gets WA. I handled the potential integer overflow problem with unsigned long long. I concatenated the [cost,recipe] to represent the cost of each recipe. Then I sorted it using qsort. I believe this handles the lexicographical order.
Any ideas? Here's the code:

Code: Select all

#include <iostream>
#include <map>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

map <string, int> ingredients;

int t, k, m, n;
unsigned long long b;
unsigned long long cost;
bool affordable;
bool atLeastOne;

void print(vector<string> goodOnes){

	//sort
	sort (goodOnes.begin(), goodOnes.end());
	
	//print
	for (int i=0; i<goodOnes.size(); i++){
		string s = goodOnes.at(i);
		int num = s.find_first_of("::");
		cout << s.substr(num+2, s.length()-num-1) << endl;
		//cout << s << endl;
	}
}

int main(){
	cin >> t;
	int len;
	string line;
	string s;
	string recipe;
	int num;
	
	for (int i=0; i<t; i++){		//each binder
		getline(cin, line);			//'\n'
		getline(cin, line);
		len = line.length();
		for (int x=0; x<len; x++){
			line[x] = toupper(line[x]);
		}
		cout << line << endl;
		
		cin >> m >> n >> b;
		
		for (int j=0; j<m; j++){		//read ingredients
			cin >> s;
			cin >> ingredients[s];		
		}
		
		atLeastOne = false;
		vector<string> goodOnes;
		for (int j=0; j<n; j++){		//each recipe
			cost = 0;
			affordable = true;
			getline(cin, line);
			getline(cin, line);
			cin >> k;
			for (int x=0; x<k; x++){		//each requirement
				cin >> s;
				cin >> num;
				if (!affordable)
					continue;
				cost = cost + (ingredients[s] * num);
				if (cost > b){
					affordable = false;					
				}
			}
			if (affordable){
				stringstream ss;				
				ss << cost;
				string s;
				ss >> s;
				goodOnes.push_back(s + "::" + line);
				atLeastOne = true;
			}
		}
		
		if (atLeastOne)
			print(goodOnes);
		else
			cout << "Too expensive!"<<endl;
			
		cout << endl;
	}

	return 0;
}

[jamesy]

Can't work out what im doing wrong. I've been through this code so many times and its annoying the hell out of me. Can someone tell me where ive screwed up so i can move on -

Code: Select all

#include <iostream>
#include <map>
#include <string>
#include <algorithm>
#include <vector>

#define for0(abc,xyz) for(int abc=0; abc<xyz; abc++)
#define for1(abc,xyz) for(int abc=1; abc<=xyz; abc++)

using namespace std;

long long t, m, n, b;
string bindername;

map<string,long long> ingredients;
map<string,long long> recipe;

vector<string> recipename;

bool cmp(string r1, string r2){
	return recipe[r1] < recipe[r2] || (recipe[r1]==recipe[r2] && r1.compare(r2)<0);
}

string touppercase(string str){
	string temp="";
	for0(i,str.length()){
		temp += (char)toupper(str[i]);
	}
	return temp;
}

int main(){

	int ntest;
	cin >> ntest;

	for1(t,ntest){
		ingredients.clear();
		recipe.clear();
		recipename.clear();
		cin >> ws;
		getline(cin, bindername);
		cin>>ws;
		cin >> m >> n >> b;
		

		for0(i,m){
			string name;
			long long cost;

			cin >> ws;
			cin >> name >> cost;

			ingredients[name] = cost;
		}

		for0(j,n){
			string name;
			long long k;
			cin>>ws;
			getline(cin,name);
			recipename.push_back(name);

			cin >> k;
			long long recipecost=0;

			for0(l,k){
				string ingr;
				long long nof;
				cin>>ws;
				cin >> ingr;

				cin >> nof;

				recipecost+=nof*ingredients[ingr];

			}
			recipe[name] = recipecost;
		}

		sort(recipename.begin(),recipename.end(),cmp);

		cout << touppercase(bindername) << endl;

		if( recipe[recipename[0]] > b )
			cout << "Too expensive!"<<endl;
		else{

			long long total = 0;

			for(int i =0; i<recipename.size() && (total+recipe[recipename[i]])<=b; i++){
				cout << recipename[i]<<endl;
				total+=recipe[recipename[i]];
			}
			
		}
		cout<<endl;
	}
}

[Devil_Bird]

I Dont Know why I get WA can any one give me some test cases?
Thanks In Advance

Code: Select all

#include<iostream>
#include<map>
#include<string>
#include<set>
#include<stack>
using namespace std;

int main()
{
	map<string,int> ing;
	map<string,int> sum;
	multimap<int,string> sort;
	map<string,int>::iterator it;
	long long int money;
	int binder_some,binder_ing_list,rec_some;
	string binder_name,t;
	int temp;
	bool alaki=false;

	cin>>binder_some;
	getline(cin,binder_name);
		
		for(int i=0;i<binder_some;i++)
		{
			if(alaki)
				cout<<endl;
			alaki=true;

			getline(cin,binder_name);
			cin>>binder_ing_list>>rec_some>>money;
			getline(cin,t);
			
			for(int j=0;j<binder_ing_list;j++)
			{
				cin>>t>>temp;
				ing[t]=temp;
			}

			for(int j=0;j<rec_some;j++)
			{
				int rec_req_some;
				getline(cin,t);
				getline(cin,t);
				sum[t]=0;
				string t2;
				cin>>rec_req_some;
				for(int k=0;k<rec_req_some;k++)
				{
					cin>>t2;
					cin>>temp;
					sum[t]+=(ing.find(t2)->second) * temp;
				}
			}
		
			for(int p=0;p<binder_name.length();p++)
				if(binder_name[p]>96 && binder_name[p]<123)
					binder_name[p]-=32;
			cout<<binder_name<<endl;

		for(it=sum.begin();it!=sum.end();++it)
				sort.insert(pair<int,string>(it->second,it->first));
		    
		    map<string,int> m;
			stack<string> sta;
			multimap<int,string>::reverse_iterator it2,itt1,itt;
			for(it2=sort.rbegin();it2!=sort.rend();)
			{
				m[it2->second]=0;
				itt=itt1=it2++;
				if(++itt1==sort.rend())
					goto go;
				if(it2->first==itt->first)
					m[it2->second]=0;
				else
				{
					go:;
					map<string,int>::reverse_iterator its;
					for(its=m.rbegin();its!=m.rend();its++)
						sta.push(its->first);
					m.clear();
				}

			}
			bool b=true;
			while(!sta.empty())
			{
				if(sum[sta.top()]<=money)
					{
						cout<<sta.top()<<endl;
						b=false;
					}
				else
					if(b)
					cout<<"Too expensive!"<<endl;
				sta.pop();
				
			}
			
			binder_name.clear();
			sum.clear();
			ing.clear();
			sort.clear();
			m.clear();
			getline(cin,binder_name);
		}
		cout<<endl;
}