## 10141 - Request for Proposal

Moderator: Board moderators

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

### 10141 - Request for Proposal

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

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

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

### 10141 Why Time Limit Exceeded?

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

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
New poster
Posts: 3
Joined: Wed Sep 11, 2002 5:53 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.

Homeway
New poster
Posts: 3
Joined: Wed Sep 11, 2002 5:53 am
Ohh, I have found my fault .....
I am stupid ....
Let Program Save My Life.

Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Contact:
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!

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

Salman

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

### 10141 - Request for Proposal

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
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:
Forget it...
Just wrong and silly approach...

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

### 10141 TLE, HELP plzzzzzzz.

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
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
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
New poster
Posts: 17
Joined: Wed Mar 01, 2006 8:34 pm
Location: 2nd floor

### 10141 Kindly check on my WA code

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 ]