11308 - Bankrupt Baker

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

11308 - Bankrupt Baker

Post by sapnil » Sun Oct 07, 2007 5:15 pm

/* 11308 */

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

Code: Select all


//Removed

Thanks
Keep posting
Sapnil

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Sun Oct 07, 2007 7:46 pm

Finally i got acc


Thanks
keep posting
Sapnil

Lomir
New poster
Posts: 19
Joined: Mon Sep 17, 2007 10:05 pm
Contact:

Post by Lomir » Sun Oct 07, 2007 8:26 pm

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

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

Post by lovemagic » Mon Oct 08, 2007 10:22 am

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;
}

khobaib

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Oct 08, 2007 10:58 am

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.
Last edited by sclo on Mon Oct 08, 2007 11:09 am, edited 3 times in total.

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Mon Oct 08, 2007 11:01 am

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
New poster
Posts: 19
Joined: Mon Sep 17, 2007 10:05 pm
Contact:

Post by Lomir » Mon Oct 08, 2007 1:49 pm

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

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

Post by lovemagic » Mon Oct 08, 2007 4:16 pm

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?
khobaib

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Oct 08, 2007 8:20 pm

lovemagic wrote: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
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by baodog » Mon Oct 08, 2007 10:29 pm

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

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

Post by lovemagic » Tue Oct 09, 2007 8:23 pm

finally got AC...... :D
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.
khobaib

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

Post by lovemagic » Tue Oct 09, 2007 8:25 pm

finally got AC...... :D
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.
khobaib

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

WA

Post by jjtse » Mon Dec 17, 2007 6:30 am

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
New poster
Posts: 1
Joined: Thu Jun 23, 2011 10:57 am

Re: 11308 - Bankrupt Baker

Post by jamesy » Thu Jun 23, 2011 11:05 am

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
New poster
Posts: 10
Joined: Sun Mar 17, 2013 12:02 am

Re: 11308 - Bankrupt Baker

Post by Devil_Bird » Thu Mar 21, 2013 7:57 pm

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;
}

Post Reply

Return to “Volume 113 (11300-11399)”