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

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

Post by Noim » Sat Aug 02, 2003 4:34 pm

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. :)
__nOi.m....

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Sat Aug 02, 2003 5:42 pm

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

Post by Riku » Mon Aug 04, 2003 5:42 pm

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 :o
anyone have a tricky test case ?

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

Post by Noim » Mon Aug 04, 2003 5:50 pm

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
__nOi.m....

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan » Mon Aug 04, 2003 5:50 pm

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

Riku
New poster
Posts: 4
Joined: Fri Aug 01, 2003 7:45 am

Post by Riku » Tue Aug 05, 2003 2:17 am

thanks 4 the help, I just make a little stupid fault :oops:
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

Post by udvat » Fri Aug 08, 2003 5:36 pm

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

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

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Thu Aug 14, 2003 3:40 am

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
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Fri Aug 22, 2003 10:24 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

Post by carlosbp2002 » Fri Nov 07, 2003 8:37 pm

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
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Fri Nov 07, 2003 9:10 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

Post by halyavin » Thu Nov 13, 2003 3:55 pm

>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
New poster
Posts: 4
Joined: Wed Oct 15, 2003 5:14 pm

119: Run time error?????

Post by zymeth02 » Mon Dec 08, 2003 9:54 am

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

[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

Post by aakash_mandhar » Sat Dec 13, 2003 11:34 pm

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

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » Mon Dec 15, 2003 5:59 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

Post Reply

Return to “Volume 1 (100-199)”