119 - Greedy Gift Givers

[Noim]

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?

anyway, thanks for replying.

[UFP2161]

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]

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]

Riku,

thanks for your explanation.

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

wish this will help

[Joseph Kurniawan]

There's no tricky input for this prob. Perhaps you should show your code

[Riku]

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]

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

[c]

[Krzysztof Duleba]

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]

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]

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

Greetings from Peru
Thanks in advance

{ GREEDY GIFT GIVERS }

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
giftmoney : INTEGER;
friend, posfriend : INTEGER;
BEGIN

giftmoney := 0;

{ Distribute its money equally }
IF (group[posperson].inimoney <> 0) THEN
giftmoney := group[posperson].inimoney DIV group[posperson].nfriends;

{ 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]);

group[posfriend].finmoney := group[posfriend].finmoney + giftmoney;

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
ReadData : STRING;
VAR
c : CHAR;
str : STRING;
BEGIN

REPEAT
READ(INPUT, c);
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;
READ(INPUT, c);
END;

ReadData := str;

END;

{ PP }

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

BEGIN
WHILE NOT EOF(INPUT) DO BEGIN
READLN(INPUT, npeople);
READLN(INPUT, strnames);
FOR i:= 1 TO npeople DO BEGIN
group.name := ReadData;
VAL(ReadData, group.inimoney, cod);
VAL(ReadData, group.nfriends, cod);
group.finmoney := 0;
FOR j:=1 TO group.nfriends DO BEGIN
group.friends[j] := ReadData;
END;
END;
GreedyGivers(group, npeople, strnames);
WRITELN(OUTPUT);
END;

END.

[Maarten]

don't just post your code but tell us the method you're using.

[halyavin]

>IF (group[posperson].inimoney <> 0) THEN
>giftmoney := group[posperson].inimoney DIV group[posperson].nfriends;
What about division by zero?
Input:
2
one two
one 100 0
two 10 1 one

Output:
one 10
two -10

[zymeth02]

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]

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]

[abishek]

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