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

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

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

Oh ho! what a great mistake.

I forgot to store the highest proposal's price in low_price.

that's the wrong. Sorry.

Now AC (Air Conditioning).
[ Common thing of every man is that, everyone thinks that he is uncommon ]

zaman
New poster
Posts: 8
Joined: Sun Jan 07, 2007 5:40 am
Location: dhaka

WA(10141)

Post by zaman » Sat Feb 03, 2007 8:38 pm

Hi, everyone. I'm getting WA in this easy problem.
Anybody please give some sample input where it fail.Here is my code.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#define SIZE 500000

char ch[85];
char proposal[SIZE][85];
double cost[SIZE];
int met_req[1050];


void main(){
	int n, p, i, j, max_req, pos, rfp_no = 0;
	long double min_cost;
	char c[85];
	
	//freopen("G:\\input.txt","r",stdin);

	while (2 == scanf("%d%d",&n,&p)){
		
		if (n == 0 && p == 0)
			break;

		else {
			
			if (rfp_no != 0)
				printf("\n");
			
			gets(ch);
			
			for ( i = 1; i <= n; i++)
				gets(ch);
			
			
			for ( i = 1; i <= p; i++){
				scanf("%s%lf%d",&proposal[i],&cost[i],&met_req[i]);

				if (i == 1){
					max_req = met_req[i];
					min_cost = cost[i];
					pos = i;
				}
				else{
					if (max_req < met_req[i]){
						max_req = met_req[i];
						min_cost = cost[i];
						pos = i;
						
					}
					else if (max_req == met_req[i]){
						
						if (min_cost > cost[i]){
							pos = i;
							min_cost = cost[i];
						}
					}


				}
				gets(c);
				for ( j = 1; j <= met_req[i]; j++)
					gets(c);
					
			}
			
			printf("RFP #%d\n",++rfp_no);
			puts(proposal[pos]);
		}
	
	}
}
Any help will be appreciated.Please reply soon.

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

Post by Tariq Shahriar » Tue Feb 13, 2007 1:08 pm

Problem mentioned: a line naming the proposal (up to 80 characters terminated by end of line). so the proposal name may contain white spaces.
But your code is-

Code: Select all

for(i=1;i<=p;i++){
            scanf("%s%lf%d",&proposal[i],&cost[i],&met_req[i]);
so use gets().
You can optimize

Code: Select all

for(i=1;i<=p;i++){
            scanf("%lf%d", cost+i, met_req+i);
but this will not work for string input. For string input, it needs some modification. Rather, &str is better.
Moreover, you have no need to store proposal, cost, met_req in an array; because you are inputing and using these variables immediately, and are not using it later. So just declare as a single variable.
[ Common thing of every man is that, everyone thinks that he is uncommon ]

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

Post by Tariq Shahriar » Tue Feb 13, 2007 1:47 pm

However, there has another problem in your code. Initialize max_rep and min_cost by an out-of-range value for every case.
[ Common thing of every man is that, everyone thinks that he is uncommon ]

User avatar
Fuad Hassan EWU
New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

help

Post by Fuad Hassan EWU » Sat Oct 06, 2007 11:36 pm

:oops:
WA!!! in this problem!!!!! plz help

Code: Select all

Don't take the easy problem easily and don't do silly mistakes, coz doing silly mistakes are the non silly crime. 
Last edited by Fuad Hassan EWU on Tue Oct 09, 2007 12:04 pm, edited 1 time in total.
Eagle er moto daana meley urbo

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Oct 09, 2007 12:09 am

Try the set.

Input:

Code: Select all

4 4
a
b
c
d
A
20 2
a
b
B
21 1
b
C 
20 2
c 
d
D
20 2
a
d
0 0
Output:

Code: Select all

RFP #1
A
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

User avatar
Fuad Hassan EWU
New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

..

Post by Fuad Hassan EWU » Tue Oct 09, 2007 12:02 pm

hmm jan vai now it is AC. actually i didn't go through the problem attentively. that's why i calculated the result using totally wrong variables.
this is always happens in case of easy problems. thanks.
Eagle er moto daana meley urbo

ByOnti
New poster
Posts: 3
Joined: Thu Dec 16, 2010 1:39 pm

Re: 10141 - Request for Proposal

Post by ByOnti » Sat Dec 18, 2010 1:01 am

Hi everybody,

Can any of you can help me with this problem? I tested with all possible cases, but still having WA from judge.

- I send a blank line only between cases and I got WA.
- I send nothing where there are no winner and I got WA, ( the problem does not specify what to print )
- about this rule : " If several proposals have the same compliance and price you are to select the first one in the input. " I'm saving the original order in the index field, so at the end I'm ordering and print the first supplier in the list. but also I got WA.

So I don't know what more I can do.


this is my code :

Code: Select all

//============================================================================
// Name        : rfp.cpp
// Author      : byOnti 
// Description : UVA#10141 - Request for Proposal
//============================================================================

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;

struct candidate {
	string name;
	double money, compliance;
	int index;
};

bool myCompare (candidate i,candidate j) { 
	if ( i.compliance > j.compliance ) return true;
	if ( i.compliance < j.compliance ) return false;
		
	if ( i.money < j.money ) return true;
	if ( i.money > j.money ) return false;

	if ( i.index < j.index ) return true;
	if ( i.index > j.index ) return false;
		
	return false;
}


  set <string> items;
  set <string>::iterator mi;

  vector<candidate> proposal;
  vector<candidate>::iterator pi;

int main() {
	int n,p,i,j,t;
	string a,b;
 
  cin>>n>>p;
	cin.ignore();//dummy char
	t=0;
  while( !(n==0 && p==0)) {	
    //if (t) cout << endl;
  	items.clear();
  	proposal.clear();
  	cout<<"RFP #"<<++t<<endl;
  	for (i=0; i<n; i++) {
  		getline(cin,a);
  		items.insert(a);
  	}
  	int cant,met;
  	for (i=0; i<p; i++) {
  		candidate c;
  		getline(cin, c.name);
  		cin>>c.money>>cant;
  		cin.ignore();
  		met = 0;
  		for (j=0; j<cant; j++ ) {
    		getline(cin,b);
    		mi = items.find(b);
    		if (mi!= items.end()) met++;
  		}
  		c.index = i;
  		c.compliance = 1.0 * met / items.size();
  		proposal.push_back ( c );
  	}

    sort (proposal.begin(), proposal.end(), myCompare); 
    //cout << "proposal contains: "<<endl;
    //for (pi=proposal.begin(); pi!=proposal.end(); pi++) 
    //cout << pi->compliance<<" " <<pi->money<< "  "<<pi->index<<" "<<pi->name << endl;

		pi=proposal.begin();
		if (pi->compliance > 0) cout<<pi->name<<endl;
    cout<<endl;

    cin>>n>>p;
    cin.ignore();
	}
	return 0;
}

rte
New poster
Posts: 2
Joined: Tue Mar 22, 2011 2:37 am

10141

Post by rte » Fri Aug 12, 2011 4:38 am

hi everybody...

i was tried to solve the 10141 problem, and firstly i thought that i needed to search if any name of the requirement (from the proposal) was in the main list
i used a set, and my code was:

Code: Select all

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>

using namespace std;

int main(){
	
	int count = 1,r;
	while(true){
		int n,m;
		set < string > s, s2;
		
		double maxPrize=0, prize;
		int maxMet=0;
		string maxName, name, requeriment, met;
		
		scanf("%d%d\n", &n, &m);
		
		maxMet = -1;
		maxPrize = 0;
				
		if(n==0) break;
		
		for(int i=0; i<n; ++i){
			getline(cin, requeriment, '\n');
			s.insert(requeriment);
		}
		for(int i=0; i<m; ++i){
			getline(cin, name, '\n');
			scanf("%lf%d\n", &prize, &r);
			
			for(int j=0; j<r; ++j){
				getline(cin, met, '\n');
				if(s.find(met) != s.end()) s2.insert(met);				
			}
			if(maxMet < (int)s2.size()) {
				maxName = name;
				maxMet = (int)s2.size();
				maxPrize = prize;
			}else if(maxMet == (int)s2.size() && maxPrize > prize){
				maxName = name;
				maxPrize = prize;
			}
			s2.clear();			
		}
		if(count > 1) printf("\n");
		printf("RFP #%d\n", count);
		cout << maxName << endl;
		count ++;
	}
}
but i got WA, then i tried to solve without searching the requirement, replacing

this segment:

Code: Select all

			for(int j=0; j<r; ++j){
				getline(cin, met, '\n');
				if(s.find(met) != s.end()) s2.insert(met);				
			}
			if(maxMet < (int)s2.size()) {
				maxName = name;
				maxMet = (int)s2.size();
				maxPrize = prize;
			}else if(maxMet == (int)s2.size() && maxPrize > prize){
				maxName = name;
				maxPrize = prize;
			}
			s2.clear();
for this:

Code: Select all

			for(int j=0; j<r; ++j){
				getline(cin, met, '\n');
			}
			if(maxMet < r) {
				maxName = name;
				maxMet = r;
				maxPrize = prize;
			}else if(maxMet == r && maxPrize > prize){
				maxName = name;
				maxPrize = prize;
			}
and i got AC...

i can't understand why my first code was wrong, the only answer that i find is the file.IN (input file) contains some test cases that ignore if a requirement of any proposal is in the list of requirements...

if i'm wrong, please tell me...

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10141 - Request for Proposal

Post by Mukit Chowdhury » Mon Dec 31, 2012 12:06 pm

Why WA !!!! Help please.... This problem is very easy .... :(

Code: Select all

Accepted.... :)

cosmin79
New poster
Posts: 11
Joined: Fri Aug 09, 2013 7:25 pm

Re: 10141 - Request for Proposal

Post by cosmin79 » Fri Aug 09, 2013 7:34 pm

Code: Select all

#include <cstdio>
#include <cstring>
#include <vector> 
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#define mp make_pair
#define LMAX 85
#define NMAX 1005
using namespace std;
int n, p, r, no, res_no;
char A[NMAX][LMAX];
char name[LMAX], word[LMAX], res_name[LMAX];
double price, best_price;

int main()
{
    freopen("input", "r", stdin);
    
    int i, j, k, rfp_no = 0;
    while (scanf("%d%d\n", &n, &p) == 2)
    {
        if (!n && !p)
            return 0;
        if (rfp_no)
            printf("\n");
        
        rfp_no++;
        for (i = 1; i <= n; i++)
            gets(A[i]);
        
        for (i = 1; i <= p; i++)
        {
            memset(name, 0, sizeof(name));
            gets(name);
            scanf("%lf%d\n", &price, &r);
            no = 0;
            
            for (j = 1; j <= r; j++)
            {
                memset(word, 0, sizeof(word));
                gets(word);
                for (k = 1; k <= n; k++)
                    if (strcmp(A[k], word) == 0)
                    {
                        no++;
                        break ;
                    }
            }
            
            if (res_no < no || (res_no == no && price < best_price))
            {
                memcpy(res_name, name, sizeof(name));
                best_price = price;
                res_no = no;
            }
        }
        
        printf("RFP #%d\n", rfp_no);
        cout << res_name << "\n";
        best_price = 0; res_no = -1;
        memset(A, 0, sizeof(A));
    }
    return 0;
}

Can anyone please tell me what's wrong in this piece of code? I have made the obvious approach of storing the requirements into a matrix and afterwards, whenever I'm analysing a proposal I'm looking up each requirement against the previous matrix. As for the comparison criteria, the no of met requirements comes first and in case of equality, the price (lower) comes second. I'm making sure I'm leaving a blank line between every 2 tests cases and that I'm not leaving 2 blank lines after the last testcase.
Therefore, I would expect a TLE result in the worst case for the lookup step, but instead I'm getting a WA verdict.
Ideas please? Thank you in advance!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10141 - Request for Proposal

Post by brianfry713 » Sat Aug 10, 2013 12:05 am

Don't read from a file.
Check input and AC output for thousands of problems on uDebug!

cosmin79
New poster
Posts: 11
Joined: Fri Aug 09, 2013 7:25 pm

Re: 10141 - Request for Proposal

Post by cosmin79 » Sat Aug 10, 2013 12:30 am

Sorry about that. I have left it unintentionally. I usually comment it before submitting ; so this is not the issue

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10141 - Request for Proposal

Post by brianfry713 » Sat Aug 10, 2013 1:33 am

All requirements are from the RFP requirement list, and no requirements are duplicated.

Instead of matching requirements, just compare the numbers. You can ignore all requirement strings, the only string I keep in my AC code is the name of the best proposal.
Check input and AC output for thousands of problems on uDebug!

d3nd0h
New poster
Posts: 8
Joined: Sun Nov 03, 2013 3:39 am

Re: 10141 - Request for Proposal

Post by d3nd0h » Sun Nov 03, 2013 3:45 am

Hello if been trying for some time, but still isn't getting AC, can anyone give me several test case which I would make the stupid mistake?
If you can please also check my code, Thx :D

Code: Select all

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

int main(){
	string dum,out;
	double d,num,price ;
	int n,p,r,count=0;
	scanf("%d%d",&n,&p);
	while(n!=0 && p!=0){
		price=99999999999;num=0;out="";
		getline(cin,dum);
		for(int i=0;i<n;i++) getline(cin,dum);
		for(int i=0;i<p;i++){
			getline(cin,dum);
			scanf("%lf %d",&d,&r);
			if(r==0)continue;
			if(num<r){num=r; price=d; out=dum;}
			else if(num==r && price>d){num=r; price=d; out=dum;}
			getline(cin,dum);
			for(int j=0;j<r;j++) getline(cin,dum);
		}
		count++;
		printf("RFP #%d\n",count);
		cout<<out<<'\n'<<'\n';
		scanf("%d%d",&n,&p);
	}
	return 0;
}

Post Reply

Return to “Volume 101 (10100-10199)”