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

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

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

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:
Thanks! That did the trick

ligregni
New poster
Posts: 11
Joined: Thu Nov 29, 2007 12:41 am
Location: Queretaro, M
Contact:
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

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

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

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|_|\/|\/|/-\|\|