Page 1 of 3

10141 - Request for Proposal

Posted: Sat Jan 18, 2003 3:56 am
by stcheung
Is 10141 supposed to be very easy? But doesn't look like it from submission stats. Anyways, this is what I do. I basically ignored the names of all requirements required or met, and just focus on the number met and the price of each proposal. So basically I just try to see which proposal has highest number of "proposal mets". If there's a tie, I then simply take the one with lowest price. But if so, then the problem is really stupid and I don't think any contest problem is THAT stupid. So tell me what's wrong with my reasonsing, or my code (THANKS):


[cpp]#include <iostream.h>
#include <stdlib.h>
#include <string>

int main()
{
int numreq, numcomp, nummet, counter=0;
string temp, tempinput;
while(true)
{
counter++;
cin >> numreq >> numcomp;
getline(cin, tempinput);
string names[numcomp];
double prices[numcomp];
int nummet[numcomp];
if(numreq + numcomp <= 0)
break;
for(int i=0; i<numreq; i++)
getline(cin, tempinput);
if(numcomp == 0)
continue;
for(int j=0; j<numcomp; j++)
{
cin >> names[j];
getline(cin, tempinput);
cin >> prices[j];
cin >> nummet[j];
getline(cin, tempinput);
// cout << "name: " << names[j] << "\t";
// cout << "price: " << prices[j] << "\t";
// cout << "nummet: " << nummet[j] << "\n";
for(int k=0; k<nummet[j]; k++)
getline(cin, temp);
}
int highestcompliant=nummet[0];
double lowestprice=prices[0];
string winner = names[0];
for(int m=1; m<numcomp; m++)
{
if(nummet[m] >= highestcompliant)
{
if(nummet[m] > highestcompliant)
{
highestcompliant = nummet[m];
lowestprice = prices[m];
winner = names[m];
}
else if(prices[m] < lowestprice)
{
lowestprice = prices[m];
winner = names[m];
}
}
}
cout << "RFP #" << counter << "\n" << winner << "\n\n";
}

return 0;
}[/cpp]

Posted: Mon Jan 20, 2003 1:10 pm
by SMBfromRU
Your code looks correct at first glance. But why you use arrays?
In this problem you only need to store maximum complient number, corresponding proposal name and minimal price, i.e. 2 integers and 1 string through all cycle.
And what you can try to do besides: init value for "compliance" should be negative, in case when there is only 1 proposal with 0 reqs met.

Best regards

10141 Always got TLE !! help !!!

Posted: Sat Jan 31, 2004 6:08 pm
by Anson
my problem work on well on my own computer .
should i use some other kind of form to represent the input when n=0 p=0

here is my code .. any one can help me? thanks a lot

Code: Select all

#include<iostream.h>
#include<string.h>
#include<stdio.h>

int main()
{
	int n,p,r,maxr=0,num=0,i,j,serial=0;
	float d,mind=0;
	char name[81],proposal[81];
	while(cin>>n>>p)
	{
		serial++;
		if (n==0&&p==0)break;
		for(i=0;i<n;i++)
		{
			gets(name);
		}
		for(i=0;i<p;i++)
		{
			for(j=0;j<81;j++)name[i]='\0';
			gets(name);
			cin>>d;
			cin>>r;
			if(r>maxr)
			{
				maxr=r;
				mind=d;
				strcpy(proposal,name);
			}
			if(r==maxr)
			{
				if(d<mind)
				{
					mind=d;
				    strcpy(proposal,name);
				}
			}
			for(j=0;j<r;j++)
				gets(name);
		}
		cout<<"RFP #"<<serial<<endl;
		cout<<proposal<<endl;
		cout<<endl;
		maxr=0;
		mind=0;
		for(i=0;i<81;i++)
			{
				name[i]='\0';
				proposal[i]='\0';
			}

	}
	return 0;
}
[/cpp]

Posted: Tue Feb 03, 2004 7:37 pm
by Morning
U can't use gets() after cin.It's strange but the gets() will absorb the second variable :wink:
see my post:
http://online-judge.uva.es/board/viewto ... 0923#20923

10141 Why Time Limit Exceeded?

Posted: Mon Jan 24, 2005 5:13 pm
by Jadecarp
I am a beginner, but I think this is a reduced code.
Why is it still time limit exceed? Thank you for your help.

Code: Select all

#include <stdio.h>
#include <stdlib.h>

void RFP(int NP[]);
void reset(char Com[]);
int count=0;

int main()
{
  int np[2];
     
  scanf("%d%d",&np[0],&np[1]);     
  while(np[0]!=0 || np[1]!=0){
      count++;
      RFP(np);
      scanf("%d%d",&np[0],&np[1]);      
  }
  return 0;
}
void RFP(int NP[])
{
  int i,j;
  double d,holdd=0.0;
  int r,holdr=0;
  char com[80]={0};  
  char holdcom[80]={0};
      
  for(i=0;i<=NP[0];i++){
      while(getchar()!='\n');
  }
  for(j=0;j<NP[1];j++){
     reset(com);
     scanf("%s%lf%d",com,&d,&r);   
     if(holdr<r || (holdr==r && holdd>d)){        
        holdd=d;
        holdr=r;
        reset(holdcom);
        sscanf(com,"%s",holdcom);
     }            
     for(i=0;i<=r;i++){
         while(getchar()!='\n');
     }     
  }
  printf("RFP #%d\n%s\n",count,holdcom);
  holdd=0.0; d=0.0; holdr=0; r=0; reset(holdcom);       
}
void reset(char Com[])
{
  int i;
  for(i=0;i<80;i++){
      Com[i]='\0';
  }    
}        

10141

Posted: Fri Feb 25, 2005 3:10 pm
by ally01202

Code: Select all

/*10141*/
#include<stdlib.h>
#include<stdio.h>
int main(void)
{
 int flag=0,n,p,i,j,item,price,pmin=10000000,imax=0,ans;
 char store[1002][82],stuff[82],data[82],c;
 while(scanf("%d %d",&n,&p)!=EOF)
 {
   pmin=10000000;imax=0;
   flag++;
   if(n==0 && p==0)
     break;
     scanf("%c",&c);
   for(i=0;i<n;)
   {
     scanf("%c",&c);
     if(c==10)
       i=i+1;
   }
   for(i=0;i<p;i++)
   {
     scanf("%s",store[i]);
     scanf("%f",&price);
     scanf("%d",&item);
     if(item>imax)
     {
       imax=item;
       pmin=price;
       ans=i;
     }
     if(item==imax)
     {
       if(price<pmin)
       {
         pmin=price;
         ans=i;
       }
     }
     scanf("%c",&c);
     for(j=0;j<item;)
     {
        scanf("%c",&c);
        if(c==10)
          j=j+1;
     }
   }
   
   printf("RFP #%d\n%s\n\n",flag,store[ans]);
 }
 return 0;
}
I have run out of my ropes...

Posted: Wed Jun 01, 2005 9:29 am
by Homeway
I have the same problem about TLE.
I don't know where the mistake is .....
Can anyone help me?

Code: Select all

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

using namespace std;

class Req{
  public:
  string company;    
  double money;
  int item;    
};

inline bool my_sort(const Req& a,const Req& b){
   return (a.item == b.item) ? (a.money < b.money) : (a.item > b.item);
}

int main(void){
  int n,p;
  int i;
  int number = 0;
  Req m_item;
  Req m_gooditem;
  string m_tmp;

  while(1){
    cin >> n >> p;
    if (n == 0 && p == 0) break;

    number++;
    
    for(i = 0;i < n;i++)
    cin >> m_tmp;

    for(i = 0;i < p;i++){
      cin >> m_item.company >> m_item.money >> m_item.item;
      int j;
      for (j = 0;j < m_item.item;j++)
      cin >> m_tmp;

       if (i == 0)
          m_gooditem = m_item;
       else
          if (!my_sort(m_gooditem,m_item) )
            m_gooditem = m_item;
    }           
    cout << "RFP #" << number << '\n' << m_gooditem.company << '\n' << endl;
   
  } 

  return 0;    
}

Posted: Wed Jun 01, 2005 10:07 am
by Homeway
Ohh, I have found my fault .....
I am stupid ....

Posted: Fri Jun 03, 2005 12:46 pm
by Shaka_RDR
can any body give me some sample I/O ? i got WA here... :(
i read Steven Halim's guide but i still get WA.... help :(

10141 Need test case!

Posted: Sun Sep 25, 2005 9:35 am
by Salman
I need some test case for this easy problem . Can anyone help?

Salman

10141 - Request for Proposal

Posted: Tue Oct 11, 2005 9:46 am
by Roby
Hello, everyone...

I've rewrite my codes so many times and still get WA. I followed the algorithm in Steven Halim's website and also still get WA.

Can anyone explain to me, how's the algorithm or the method to solve this problem? Thanx... :(
"Before God, we are all equally wise and equally foolish"

Posted: Tue Nov 29, 2005 8:31 am
by Roby
Forget it...
AC already...
Just wrong and silly approach...

10141 TLE, HELP plzzzzzzz.

Posted: Thu Jun 22, 2006 8:12 pm
by deena sultana
Hello friends,
i got TLE 10141. :(
is there any suggestion?
plzzzzzzzzz help.

here is my code:

Code: Select all

#include<iostream>
#include<string>
#include<stdio.h>
#include<cstring>	
using namespace std;

int main()
{
	int n,p,count=0,req1,req2;
	float price1,price2;
	char str[85];
	char name1[100],name2[100];

	while(cin>>n>>p)
	{	
		count++;
		if(n==0 && p==0)
			break;
		int loop1=n;
		while(loop1--)
		{	
			gets(str);
			}
		
		if(p>0){
				gets(name1);
				//cin>>name1;
			cin>>price1>>req1;
			p--;
			int loop2=req1;
			while(loop2--)
				{
					gets(str);
				}
			
			}
		while(p--)
		{			gets(name2);
					//cin>>name2;
					cin>>price2>>req2;
					if(req2>req1){
						strcpy(name1,name2);
						//name1=name2;
						price1=price2;
						req1=req2;}
					else if(req2==req1 && price2<price1){
						strcpy(name1,name2);
						//name1=name2;
						price1=price2;
						req1=req2;}
					while(req2--)
						{
							gets(str);
						}
			
		}
		cout<<"RFP #"<<count<<endl<<name1<<endl;
		cout<<endl;

	}
	
	return 0;
}

Posted: Fri Sep 08, 2006 1:29 am
by A1
don't use gets() and cin in same code!! they always do trouble...!!
u can use scanf() instead of cin, and to read the ending new line character by scanf(), the code should be:

Code: Select all

scanf("%d\n",&v);
then you can use gets();
I don't test ur code but I think u r getting TLE because it is taking inputs incorrectly and stuck :roll:

10141 Kindly check on my WA code

Posted: Sat Oct 07, 2006 12:11 pm
by Tariq Shahriar
Judges ans is WA.

Code: Select all

Deleted after Accepted. Because you may resolve and submit my code.
1. initialize highest=-1 and low_price=999999999999.0
2. I just read, don't store the requirements
3. only keep the highest offer value.
4. if offers==highest_offer then check the low price.
and then keep the company name.
6. after using scanf, i call gets() to take the new line char and spaces
(if any).