## 119 - Greedy Gift Givers

Moderator: Board moderators

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
ok Joseph,
you may be right. but what does the problem setter mean by that line:
Any money not given is kept and is part of a person's ``net worth'' printed in the output.
doesn't this line hold any meaning?

__nOi.m....

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
a line for each person in the group consisting of the name of the person, the amount of money spent on gifts, the number of people to whom gifts are given, and the names of those to whom gifts are given.
Your input would be invalid, because if the person never gave out a gift, his money input would always be zero (because he/she didn't spend any money) and not a positive integer.

Riku
New poster
Posts: 4
Joined: Fri Aug 01, 2003 7:45 am
I think that because nahid and noim have 9 and 10 in the first time. after giving events, they have still 9 and 10, so 9-9=0 and 10-10=0

anyway, my program still WA after this modification, why
anyone have a tricky test case ?

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Riku,

any way, Did you consider for the case when the total person is only one or two.

wish this will help
__nOi.m....

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
There's no tricky input for this prob. Perhaps you should show your code

Riku
New poster
Posts: 4
Joined: Fri Aug 01, 2003 7:45 am
thanks 4 the help, I just make a little stupid fault
I use mod calculation to determine how much one should take money for himself, so I give "if the modulo not zero", but I forgot to write the "else" code. After I read this message board, I realize that matter, but again... I write it wrong ^-^;

udvat
New poster
Posts: 29
Joined: Thu Aug 07, 2003 9:56 pm

### 119.............tired of getting RTE,help me plz

am getting RTE but failed to understand why.wud anyone plz help me?and also any kind of code improvement suggestion is appreciated.

[c]
Last edited by udvat on Tue Nov 11, 2003 7:33 pm, edited 1 time in total.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Why is your code so complicated? What are all the strcpy's for? Make your code easier to read, now I can't see how it's working.

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
The judge cheats on this problem.

At the end of the input, there is a duplicate name. Although this should not happen, it does, and it gives a RTE.

More than likely, your program looks for another token, expecting to find an integer, but instead finds a string.

Sounds silly, but I was getting an error also, so I canged

[java]while(tok.hasMoreTokens()) {
npeople = Integer.parseInt(tok.nextToken());
(....)
}[/java]

to

[java]while(tok.hasMoreTokens()) {
try{npeople = Integer.parseInt(tok.nextToken());}
catch(NumberFormatException e) {System.exit(0);}
(....)
}[/java]

And got accepted. Weird, but it worked. I know there's an extra name added because I put a check in my program. If the first character of the next token was a letter, I entered a spinlock. It returned TLE, so that's how I knew.

carlosbp2002
New poster
Posts: 2
Joined: Mon Aug 18, 2003 12:14 am

### Whats wrong with my solution ??? #119

Im new here , and my program solve the tests inputs in the problem
statement , but i got WA.. why ???

Greetings from Peru

PROGRAM Greedy(INPUT, OUTPUT);

CONST
MAX = 10;

TYPE

str12 = STRING[12];
TStrings = ARRAY[1..MAX] OF str12;
TPerson = RECORD
name : STRING;
nfriends : INTEGER;
friends : TStrings;
inimoney, finmoney : INTEGER;

END;

TPeople = ARRAY[1..MAX] OF TPerson;

{ Procedures / Functions }

FUNCTION
SearchFriend(
VAR group : TPeople;
npeople : INTEGER;
friendname : STRING
) : INTEGER;
VAR
posfriend, posi : INTEGER;
BEGIN
posfriend := -1;
FOR posi:=1 to npeople DO BEGIN
IF ( POS(friendname, group[posi].name) > 0 ) THEN BEGIN
posfriend := posi;
END;
END;
SearchFriend := posfriend;
END;

PROCEDURE
CalcFinalMoney(
VAR group : TPeople;
npeople : INTEGER;
posperson : INTEGER
);
VAR
friend, posfriend : INTEGER;
BEGIN

{ Distribute its money equally }
IF (group[posperson].inimoney <> 0) THEN

{ Keep the remainder }
IF (group[posperson].inimoney <> 0) THEN
group[posperson].finmoney := group[posperson].finmoney +
( group[posperson].inimoney MOD
group[posperson].nfriends );

FOR friend :=1 TO group[posperson].nfriends DO BEGIN

posfriend := SearchFriend(group, npeople, group[posperson].friends[friend]);

END;

END;

FUNCTION
ExtractName(
VAR names : STRING
):STRING;
VAR
posblanco : INTEGER;
nam : STRING;
BEGIN
posblanco := POS(' ', names);
IF (posblanco > 0) THEN BEGIN
nam := COPY(names, 1, posblanco-1);
DELETE(names, 1, posblanco);
END
ELSE
nam := names;

ExtractName := nam;
END;

PROCEDURE
GreedyGivers(
VAR group : TPeople;
npeople : INTEGER;
strnames : STRING
);
VAR
nperson, i : INTEGER;
name : STRING;
BEGIN

FOR nperson:=1 TO npeople DO BEGIN

{ Calculate person's final money }
CalcFinalMoney(group, npeople, nperson);

END;

{ Print names : strnames }
FOR i:=1 TO npeople DO BEGIN
name := ExtractName(strnames);
nperson := SearchFriend(group, npeople, name);
WRITELN(OUTPUT, group[nperson].name, ' ', (group[nperson].finmoney-
group[nperson].inimoney):1);

END;
END;

FUNCTION
VAR
c : CHAR;
str : STRING;
BEGIN

REPEAT
UNTIL ( (c <> ' ')
AND (c <> #10)
AND (c <> #13)) ;

str := '';

WHILE ( ( c <> ' ' )
AND ( c <> #10 )
AND ( c<> #13 )
AND (c <> #26) ) DO BEGIN
str := str + c;
END;

END;

{ PP }

VAR
group : TPeople;
i, j, cod, npeople : INTEGER;
strnames : STRING;

BEGIN
WHILE NOT EOF(INPUT) DO BEGIN
FOR i:= 1 TO npeople DO BEGIN
group.finmoney := 0;
FOR j:=1 TO group.nfriends DO BEGIN
END;
END;
GreedyGivers(group, npeople, strnames);
WRITELN(OUTPUT);
END;

END.

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
don't just post your code but tell us the method you're using.

halyavin
New poster
Posts: 3
Joined: Thu Nov 06, 2003 4:36 pm
>IF (group[posperson].inimoney <> 0) THEN
Input:
2
one two
one 100 0
two 10 1 one

Output:
one 10
two -10

zymeth02
New poster
Posts: 4
Joined: Wed Oct 15, 2003 5:14 pm

### 119: Run time error?????

this is so strange, i have tested almost all inputs and i can't find what gives it a run time error...

could any patient person pls tell me what's wrong with my code

[c]#include <stdio.h>
#include <string.h>

typedef char string12[13];

typedef struct
{
int nSpent,
nGiven,
nNetWorth;
string12 aGivenP[9],
strName;
}structGiverType;

typedef structGiverType arrGroup[10];

void fillup(arrGroup aGroup, int nPerson);
void process_net_worth(arrGroup aGroup,int nPerson);
void output(arrGroup aGroup,int nPerson);

main()
{
arrGroup aGroup;
int nPerson;

while(scanf("%d",&nPerson))
{
fillup(aGroup,nPerson);
process_net_worth(aGroup,nPerson);
output(aGroup,nPerson);
printf("\n");
}
}

void fillup(arrGroup aGroup, int nPerson)
{
int i,
j,
k,
bFound;
string12 strName;

/* gets the people in the group */
for(i=0 ; i<nPerson ; i++)
{
aGroup.nNetWorth = 0;
scanf("%s",aGroup.strName);
}

/* gets the information per person */
for(i=0 ; i<nPerson ; i++)
{
scanf("%s",strName);

j = 0;
bFound = 0;
while(!bFound)
{
if(!strcmp(aGroup[j].strName,strName))
bFound = 1;
else
j++;
}
scanf("%d",&aGroup[j].nSpent);
scanf("%d",&aGroup[j].nGiven);

for(k=0 ; k<aGroup[j].nGiven ; k++)
scanf("%s",aGroup[j].aGivenP[k]);
}
}

void process_net_worth(arrGroup aGroup,int nPerson)
{
int i,
j,
k,
bFound,
nSpent,
nGiven;
string12 strName;

for(i=0 ; i<nPerson ; i++)
{
nSpent = aGroup.nSpent;
nGiven = aGroup.nGiven;

if(nGiven != 0)
aGroup.nNetWorth -= (nSpent - nSpent%nGiven);

for(j=0 ; j<aGroup.nGiven ; j++)
{
strcpy(strName,aGroup.aGivenP[j]);

k = 0;
bFound = 0;

while(!bFound)
{
if(!strcmp(aGroup[k].strName,strName))
bFound = 1;
else
k++;
}

aGroup[k].nNetWorth += nSpent/nGiven;
}
}
}

void output(arrGroup aGroup,int nPerson)
{
int i;

for(i=0 ; i<nPerson ; i++)
printf("%s %d\n",aGroup.strName,aGroup.nNetWorth);
}
[/c]

aakash_mandhar
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore

### Problem 119: Plz help me i got wrong answer

can anyone plz tell me what is wrong with this code.. It works on the input provided.. Please let me know.... Thx in advance
[cpp]/* @JUDGE_ID: xxxxxxx 119 C++ "No special algo:)" */

# include<iostream.h>
# include<string.h>

char a[100][150];
int money[100],cash;
int n,i;
char name[200];
int people,j,k;

int main()
{

while(cin>>n)
{
for(i=0;i<n;i++)
{
cin>>a;
money=0;
}
for(i=0;i<n;i++)
{
cin>>name;
cin>>cash;
cin>>people;
for(j=0;j<n;j++)
{
if(strcmp(a[j],name)==0) {money[j]-=cash;if(people) money[j]+=cash%people; break;}
}

if(people) cash/=people; else cash=0;
for(k=0;k<people;k++)
{
cin>>name;
for(j=0;j<n;j++)
{
if(strcmp(a[j],name)==0) {money[j]+=cash;break;}
}
}

}
for(i=0;i<n;i++)
cout<<a<<" "<<money<<"\n";
cout<<"\n";
}
return 1;
}

//@end_of_source_code

[/cpp]
...I was born to code...

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am
This problem is a multiple input problem. See the page
http://online-judge.uva.es/cgi-bin/OnlineJudge?Volume:1
the instructions on the top of the page tell you how to handle the input
I guess this is the actual link
http://online-judge.uva.es/problemset/minput.html

all the best