10141 - Request for Proposal

[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]

[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

[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]

[Morning]

U can't use gets() after cin.It's strange but the gets() will absorb the second variable
see my post:
http://online-judge.uva.es/board/viewto ... 0923#20923

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

[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...

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

[Homeway]

Ohh, I have found my fault .....
I am stupid ....

[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

[Salman]

I need some test case for this easy problem . Can anyone help?

Salman

[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"

[Roby]

Forget it...
AC already...
Just wrong and silly approach...

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

[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

[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).