10141 - Request for Proposal

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

Moderator: Board moderators

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

10141 - Request for Proposal

Post by stcheung » Sat Jan 18, 2003 3:56 am

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
New poster
Posts: 7
Joined: Wed Sep 11, 2002 9:19 am

Post by SMBfromRU » Mon Jan 20, 2003 1:10 pm

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
New poster
Posts: 1
Joined: Sat Jan 31, 2004 5:59 pm

10141 Always got TLE !! help !!!

Post by Anson » Sat Jan 31, 2004 6:08 pm

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
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning » Tue Feb 03, 2004 7:37 pm

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
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

Jadecarp
New poster
Posts: 1
Joined: Wed Jan 19, 2005 4:21 am

10141 Why Time Limit Exceeded?

Post by Jadecarp » Mon Jan 24, 2005 5:13 pm

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
New poster
Posts: 1
Joined: Fri Feb 25, 2005 3:03 pm
Contact:

10141

Post by ally01202 » Fri Feb 25, 2005 3:10 pm

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

User avatar
Homeway
New poster
Posts: 3
Joined: Wed Sep 11, 2002 5:53 am

Post by Homeway » Wed Jun 01, 2005 9:29 am

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;    
}
Let Program Save My Life.

User avatar
Homeway
New poster
Posts: 3
Joined: Wed Sep 11, 2002 5:53 am

Post by Homeway » Wed Jun 01, 2005 10:07 am

Ohh, I have found my fault .....
I am stupid ....
Let Program Save My Life.

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Fri Jun 03, 2005 12:46 pm

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 :(
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

Salman
New poster
Posts: 25
Joined: Thu Jun 26, 2003 9:45 am

10141 Need test case!

Post by Salman » Sun Sep 25, 2005 9:35 am

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

Salman

User avatar
Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

10141 - Request for Proposal

Post by Roby » Tue Oct 11, 2005 9:46 am

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"

User avatar
Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

Post by Roby » Tue Nov 29, 2005 8:31 am

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

deena sultana
New poster
Posts: 36
Joined: Mon Jun 19, 2006 5:43 pm
Location: Bangladesh
Contact:

10141 TLE, HELP plzzzzzzz.

Post by deena sultana » Thu Jun 22, 2006 8:12 pm

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

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Fri Sep 08, 2006 1:29 am

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:

User avatar
Tariq Shahriar
New poster
Posts: 17
Joined: Wed Mar 01, 2006 8:34 pm
Location: 2nd floor

10141 Kindly check on my WA code

Post by Tariq Shahriar » Sat Oct 07, 2006 12:11 pm

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).
Last edited by Tariq Shahriar on Mon Oct 09, 2006 8:21 am, edited 3 times in total.
[ Common thing of every man is that, everyone thinks that he is uncommon ]

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest