119 - Greedy Gift Givers

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

Moderator: Board moderators

randomer
New poster
Posts: 3
Joined: Wed Jul 11, 2007 6:50 am

119 Greedy Gift Givers

Post by randomer » Wed Jul 11, 2007 6:55 am

I searched the entire board, none of them helped, so I'm creating a new thread.

First, does anyone have sample input/output for this problem?

My question is, do i have to take in all the input at once? Or can I just take one group and print out the result, then take the next group?

Here is my WA C++ code:

Code: Select all

#include <iostream>
#include <cstring>
using namespace std;

int main()
{	
	char people[10][10];
	char temp[12];
	int netGain[10];
	int numGroup, numSubGroup, moneySpent;

	while(cin >> numGroup)								//get the total number of people in the group
	{
		for(int x = 0; x < 10; x++)
		{
			netGain[x] = 0;
		}
		for(int x = 0; x < numGroup; x++)				//set the people's name into the array people[]
		{
			cin >> people[x];
		}
		
		for(int z = 0; z < numGroup; z++)
		{
			cin >> temp >> moneySpent >> numSubGroup;		//get the first line
			
			if(moneySpent != 0)
			{
				for(int x = 0; x < numGroup; x++)				//find out person the line corresponds to
				{
					if(strcmp(temp,people[x]) == 0)
					{
						if(numSubGroup != 0)
						{
							netGain[x] -= moneySpent;
							netGain[x] += moneySpent%numSubGroup;	
							break;
						}
					}
				}
			}
			if(numSubGroup != 0)
			{
				for(int x = 0; x < numSubGroup; x++)
				{
					
					cin >> temp;
					if(moneySpent != 0)
					{
						for(int y = 0; y < numGroup; y++)
						{
							if(strcmp(temp,people[y]) == 0)
							{
								netGain[y] += moneySpent/numSubGroup;
								break;
							}
						}
					}
				}
			}
		}
		
		for(int x = 0; x < numGroup; x++)
		{
			cout << people[x] << " " << netGain[x] << endl;
		}
		cout << "\n";
	}

	return 0;
}
What could be the error, I hear there are a lot of 'special cases' but in the other threads they wouldn't tell what they are...
Please help, I would appreciate it!

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

Post by Jan » Wed Jul 11, 2007 7:13 pm

Dont open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage

randomer
New poster
Posts: 3
Joined: Wed Jul 11, 2007 6:50 am

Post by randomer » Thu Jul 12, 2007 12:11 am

I searched the entire board, none of them helped, so I'm creating a new thread.

First, does anyone have sample input/output for this problem?

My question is, do i have to take in all the input at once? Or can I just take one group and print out the result, then take the next group?

Here is my WA C++ code:

Code: Select all

#include <iostream>
#include <cstring>
using namespace std;

int main()
{   
   char people[10][10];
   char temp[12];
   int netGain[10];
   int numGroup, numSubGroup, moneySpent;

   while(cin >> numGroup)                        //get the total number of people in the group
   {
      for(int x = 0; x < 10; x++)
      {
         netGain[x] = 0;
      }
      for(int x = 0; x < numGroup; x++)            //set the people's name into the array people[]
      {
         cin >> people[x];
      }
      
      for(int z = 0; z < numGroup; z++)
      {
         cin >> temp >> moneySpent >> numSubGroup;      //get the first line
         
         if(moneySpent != 0)
         {
            for(int x = 0; x < numGroup; x++)            //find out person the line corresponds to
            {
               if(strcmp(temp,people[x]) == 0)
               {
                  if(numSubGroup != 0)
                  {
                     netGain[x] -= moneySpent;
                     netGain[x] += moneySpent%numSubGroup;   
                     break;
                  }
               }
            }
         }
         if(numSubGroup != 0)
         {
            for(int x = 0; x < numSubGroup; x++)
            {
               
               cin >> temp;
               if(moneySpent != 0)
               {
                  for(int y = 0; y < numGroup; y++)
                  {
                     if(strcmp(temp,people[y]) == 0)
                     {
                        netGain[y] += moneySpent/numSubGroup;
                        break;
                     }
                  }
               }
            }
         }
      }
      
      for(int x = 0; x < numGroup; x++)
      {
         cout << people[x] << " " << netGain[x] << endl;
      }
      cout << "\n";
   }

   return 0;
}
What could be the error, I hear there are a lot of 'special cases' but in the other threads they wouldn't tell what they are...
Please help, I would appreciate it![/code]

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

Post by Jan » Thu Jul 12, 2007 7:48 pm

The input names can have at most 10 characters. So, you need an array which can store the 11 characters, (One for the NULL character). So, use

Code: Select all

char people[10][11];
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm

Post by sklitzz » Fri Jul 27, 2007 1:52 pm

Hi, I've been getting WA for this problem quite a while.
I've searched the forum and tried out the test cases.
I still can't find why it gets WA. Can anybody help?

My code

Code: Select all

#include <iostream>
#include <string>
#include <vector>
using namespace std;

#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)

int N;
vector < string > ppl;
vector < int > money;

int _find( string name ) {
	for( int i = 0; i < ppl.size(); ++i )
		if( ppl[i] == name )
			return i;
	return -1;
}

int main() {

	int cnt = 0;

	while( cin >> N ) {
	
		if( cnt > 0 ) cout << endl;
		cnt++;
			
		ppl.clear(); ppl.resize( N );
		money.clear(); money.resize( N, 0 );
		
		for( int i = 0; i < N; ++i ) cin >> ppl[i];

		for( int i = 0; i < N; ++i ) {
			string from, to;
			int m, n;
			
			cin >> from >> m >> n;

			int to_give = ( m == 0 || n == 0 ) ?  0 : m / n;

			if( n > 0 ) money[_find(from)] -= m;
			//else money[_find(from)] += m;

			if( n > 0 && m != 0 && to_give != 0 ) money[i] += m % to_give;
			
			for( int i = 0; i < n; ++i ) {
				cin >> to;
				money[ _find( to ) ] += to_give;
			}
			
		}

		for( int i = 0; i < N; ++i )
			cout << ppl[i] << " " << money[i] << endl;
	}

	
	return 0;
}

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

Post by Jan » Sat Jul 28, 2007 2:15 am

Try the cases.

Input:

Code: Select all

10
qghume ylnlf xfir vscxggb kfnqdux fnf zvsrtkjpr pggxrpn vystmwcy yyc
zvsrtkjpr 1805 1 yyc
qghume 1350 6 ylnlf vscxggb vystmwcy yyc vscxggb kfnqdux
kfnqdux 756 4 zvsrtkjpr zvsrtkjpr ylnlf vystmwcy
kfnqdux 439 1 vscxggb
pggxrpn 1538 5 xfir yyc ylnlf vscxggb fnf
yyc 1658 4 qghume pggxrpn zvsrtkjpr vscxggb
zvsrtkjpr 1021 4 kfnqdux xfir qghume yyc
pggxrpn 1573 2 xfir zvsrtkjpr
qghume 1161 3 fnf pggxrpn fnf
kfnqdux 31 6 qghume qghume ylnlf zvsrtkjpr qghume pggxrpn
8
atxdknly yhfixjsw kkufnuxxzr bmnmgq oketl hnkoaugzq cddi teiojwa
kkufnuxxzr 886 1 yhfixjsw
hnkoaugzq 142 5 atxdknly yhfixjsw cddi kkufnuxxzr bmnmgq
hnkoaugzq 1699 3 oketl oketl bmnmgq
atxdknly 600 1 bmnmgq
hnkoaugzq 1861 4 yhfixjsw teiojwa teiojwa kkufnuxxzr
yhfixjsw 182 1 atxdknly
kkufnuxxzr 617 3 atxdknly oketl yhfixjsw
kkufnuxxzr 1721 5 atxdknly yhfixjsw atxdknly oketl yhfixjsw
Output:

Code: Select all

qghume -1827
ylnlf 726
xfir 1348
vscxggb 1610
kfnqdux -745
fnf 1081
zvsrtkjpr -1242
pggxrpn -2301
vystmwcy 414
yyc 936

atxdknly 503
yhfixjsw 2090
kkufnuxxzr -2728
bmnmgq 1194
oketl 1681
hnkoaugzq -3698
cddi 28
teiojwa 930
Hope these help.
Ami ekhono shopno dekhi...
HomePage

randomer
New poster
Posts: 3
Joined: Wed Jul 11, 2007 6:50 am

Post by randomer » Tue Aug 14, 2007 4:00 am

Hey Jan, thanks for the help, apparently that was the problem. I did your input, and I got the output correctly, yet I'm still getting the wrong answer. I'm new at this, but does all the output have to be at the end? This is what a put in the console (the input and output is mixed):

Code: Select all

10
qghume ylnlf xfir vscxggb kfnqdux fnf zvsrtkjpr pggxrpn vystmwcy yyc
zvsrtkjpr 1805 1 yyc
qghume 1350 6 ylnlf vscxggb vystmwcy yyc vscxggb kfnqdux
kfnqdux 756 4 zvsrtkjpr zvsrtkjpr ylnlf vystmwcy
kfnqdux 439 1 vscxggb
pggxrpn 1538 5 xfir yyc ylnlf vscxggb fnf
yyc 1658 4 qghume pggxrpn zvsrtkjpr vscxggb
zvsrtkjpr 1021 4 kfnqdux xfir qghume yyc
pggxrpn 1573 2 xfir zvsrtkjpr
qghume 1161 3 fnf pggxrpn fnf
kfnqdux 31 6 qghume qghume ylnlf zvsrtkjpr qghume pggxrpn
qghume -1827
ylnlf 726
xfir 1348
vscxggb 1610
kfnqdux -745
fnf 1081
zvsrtkjpr -1242
pggxrpn -2301
vystmwcy 414
yyc 936

8
atxdknly yhfixjsw kkufnuxxzr bmnmgq oketl hnkoaugzq cddi teiojwa
kkufnuxxzr 886 1 yhfixjsw
hnkoaugzq 142 5 atxdknly yhfixjsw cddi kkufnuxxzr bmnmgq
hnkoaugzq 1699 3 oketl oketl bmnmgq
atxdknly 600 1 bmnmgq
hnkoaugzq 1861 4 yhfixjsw teiojwa teiojwa kkufnuxxzr
yhfixjsw 182 1 atxdknly
kkufnuxxzr 617 3 atxdknly oketl yhfixjsw
kkufnuxxzr 1721 5 atxdknly yhfixjsw atxdknly oketl yhfixjsw
atxdknly 503
yhfixjsw 2090
kkufnuxxzr -2728
bmnmgq 1194
oketl 1681
hnkoaugzq -3698
cddi 28
teiojwa 930

it seems right...right?

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

Post by Jan » Tue Aug 14, 2007 11:04 am

You can save the inputs in a file. Then run your code using that file. Suppose the file name is 'input.txt' and all the inputs are stored. And 'input.txt' and your code are in the same directory. Then you can use like..

Code: Select all

.... // your code

int main()
{
    freopen("input.txt","r",stdin);

    .... // your code
}
And if you want to save the output in a file suppose 'output.txt' then you can use

Code: Select all

freopen("output.txt","w",stdout);
Hope these help.
Ami ekhono shopno dekhi...
HomePage

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Compile Error

Post by jjtse » Tue Oct 23, 2007 5:31 am

Does anyone know why this gives a compile error?

I compile by:

g++ filename.cpp


it works fine on my own pc, but it has a newer compiler. Does anyone know how to compile down to older versions?

Thanks.

Code: Select all

#include <iostream>
#include <string>

using namespace std;

string line;

char num[100][100];
int answer[100];
int carry;
int index;		//number verylongintegers

//returns index of last non-blank index
int fillBlanks(){
	int len = line.length();
	
	for (int i=0; i<100 - len; i++){
		num[index][i] = '0';
	}
	
	return 100 - len;
}

void printVal(){
	for (int i=0; i<index; i++){
		for (int j=0; j<100; j++){
			cout << num[i][j];
		}
		cout << endl;
	}
}

void add(){
	int sum;
	
	carry = 0;
			
	for (int i=99; i>=0; i--){		//for each digit
		sum = carry;
		carry = 0;
		for (int j=0; j<index; j++){		//for each line
			sum += (int)(num[j][i] - '0');
			while (sum > 9){
				carry++;
				sum -= 10;
			}
		}	
		answer[i] = sum;
	}
}


void printAns(){
	bool trailZero = true;
	
	for (int i=0; i<100; i++){
		if (trailZero){
			if (answer[i] == 0)
				continue;
			else
				trailZero = false;
		}
		cout << answer[i];
	}
	cout << endl;
}

int main(){

	index = 0;	
	cin >> line;
	
	while (line != "0"){
		int j = fillBlanks();
		for (int i=0; i<line.length(); i++){
			num[index][j++] = line[i];
		}	
		index++;
		cin >> line;
	}

	//printVal();
	add();
	printAns();
	return 0;
}

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: Compile Error

Post by mf » Tue Oct 23, 2007 5:45 am

The error is in this line:
int index; //number verylongintegers
There's a standard function called index(), and that causes a conflict.
You should either rename your variable, or put it in a separate namespace.

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse » Tue Oct 23, 2007 5:56 am

Thanks! That did the trick

ligregni
New poster
Posts: 11
Joined: Thu Nov 29, 2007 12:41 am
Location: Queretaro, M
Contact:

Post by ligregni » Tue Dec 25, 2007 2:40 am

I have ACCEPTED!, and some advices, because I also suffered with this problem.
printf a newline BEFORE each case, just avoid first one (count them, if count==1, don't print anything)
print EACH name with a newline after it (after the $$$ of course), includying the last of each test case
if someone spents money in NO people "dave 100 0", just ANYONE wins or loses money, take the example above
Sergio Ligregni, hope this worth.
C: multum in parvo

"a lot since quite few"

http://acmicpc-live-archive.uva.es/nuev ... user=12539

ligregni
New poster
Posts: 11
Joined: Thu Nov 29, 2007 12:41 am
Location: Queretaro, M
Contact:

119 ACCEPTED

Post by ligregni » Tue Dec 25, 2007 2:43 am

I have ACCEPTED!, and some advices, because I also suffered with this problem.
printf a newline BEFORE each case, just avoid first one (count them, if count==1, don't print anything)
print EACH name with a newline after it (after the $$$ of course), includying the last of each test case
if someone spents money in NO people "dave 100 0", just ANYONE wins or loses money, take the example in other thread
.

Sergio Ligregni, I hope it helps!
C: multum in parvo

"a lot since quite few"

http://acmicpc-live-archive.uva.es/nuev ... user=12539

vivgrn
New poster
Posts: 6
Joined: Sat Aug 25, 2007 4:48 pm

how tot take the input

Post by vivgrn » Mon Jan 28, 2008 7:30 pm

Can we take the input 1 at a time i.e. one case as a time ???( if thats possible we just consider to input the first line ie. the number of friends and then move accordingly.)

from what codes that have been written here that is what the case seems to me...

Awaiting your reply in anticipation

thanks in advance.

mrmrumman
New poster
Posts: 10
Joined: Sat Jul 05, 2008 11:26 pm
Location: Dhaka
Contact:

Re: Compile Error

Post by mrmrumman » Wed Sep 03, 2008 2:30 am

Please see my code for UVA 119 problem it's show me floating point error why?
Any way can anyone tell what is the best free C++ compiler for VISTA and UBUNTU.

Code: Select all

# include <stdio.h>
# include <string.h>
int main()
{
	int number;
	int personnum1=10;
	int nameChar=12;
	char name[personnum1][nameChar];
        int counter=1;
	while(scanf("%d",&number)==1)
	{
            if(counter>1)
                printf("\n");
                int serial=number;
		int credit=0,gift=0;
		char receiver[personnum1][nameChar];
		char giver[nameChar];
		int account[serial];
		for(int i=0;i<serial;i++)
			account[i]=0;
		for(int i=0;i<number;i++)
			scanf("%s",name[i]);
		for(int receiverSn=0,serial=0;serial<number;serial++)
		{
			scanf("%s %d %d",giver,&credit,&gift);
                        for(receiverSn=0;receiverSn<gift;receiverSn++)
                            scanf("%s",receiver[receiverSn]);
			for(int i=0;i<number;i++)
			{
					if(strcmp(name[i],giver)==0)
						account[i]=account[i]+credit%gift;
					for(int j=0;j<receiverSn;j++)
					{
                                            int loop=strcmp(name[i],receiver[j]);
                                                if(loop==0)
						{
							account[i]=account[i]+credit/gift;
                                                        break;
						}
					}	
			}
		}
                for(int i=0;i<personnum1;i++)
                    printf("%s %d",name[i],account[i]);
                printf("\n");
                counter++;
                
	}
	return 0;
}
R|_|\/|\/|/-\|\|

Post Reply

Return to “Volume 1 (100-199)”