119 - Greedy Gift Givers

[randomer]

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]

Dont open a new thread if there is one already.

[randomer]

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]

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.

[sklitzz]

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]

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.

[randomer]

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]

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.

[jjtse]

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]

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]

Thanks! That did the trick

[ligregni]

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.

Code: Select all

[ligregni]

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!

[vivgrn]

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]

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