119 - Greedy Gift Givers

[nghiank]

test

[arjasepp]

I have a problem with 119, I get WA. I dont know what is wrong with my code.

Here you can find my code

Do I understand correctly that all input comes at once and after input reads EOF, then comes output all in groups separeated by blank line???

[kmhasan]

i think you're printing a blank line after each set. but the problem statement says:

The output for each group should be separated from other groups by a blank line.

i'd usually use:
[c]
int main() {
int first = 1;
while(scanf("%i",&n)==1) {
if (!first)
putchar('\n');
first = 0;
/* do whatever has to be done */
}
return 0;
}
[/c]

[arjasepp]

Why do I get WA? I mean with my test data everything shows right
[c]
#include <stdio.h>
#include <string.h>

#define MAX 13
#define INIMESI 10

void arvuta(int);

int main(void)
{
int n;

while((scanf("%d",&n))!=EOF)
{
arvuta(n);
}
}

void arvuta(int arv)
{
char nimi[MAX], nimed[INIMESI][MAX];
int abi, raha, papp[INIMESI], tulem;
int j, i, count, sopru;

for(i=0;i<arv;i++)
{
scanf("%s",nimed);
papp=0;
}
count=0;
while(count<arv)
{
scanf("%s%d%d",nimi, &raha, &sopru);
for(i=0;i<arv;i++)
{
tulem=strcmp(nimed,nimi);
if(!tulem)
{
if(sopru!=0)
{
papp-= (raha-(raha%sopru));
abi=raha/sopru;
}
else
papp+= raha;
}
}
for(i=0;i<sopru;i++)
{
scanf("%s",nimi);
for(j=0;j<arv;j++)
{
tulem=strcmp(nimi,nimed[j]);
if(!tulem)
{
papp[j]+=abi;
break;
}/*IF mis annab raha*/
}/*FOR, mis v

[akram_s_s]

Hi every one,
I solved the problem 119 (greedy gift givers), and i applied to it the sample input file and it worked fine. THen i realized that i have to not use or open any file. So, i change the code a little bit and it worked fine
But i dont know why the judge didnt accept it?
THis is my C code:
#include <stdio.h>
#include <math.h>
#include <string.h>
void main(void)
{

int i,j,k,l=0,m,a,n,gnumber[10000],account[10000][10]={0};
char name[10000][10][12],giver[1000][12],reciever[10000][10][12],line[100];
for (l=0;;l++)
{
gets(line);
if (strlen(line) == 0)
break;
sscanf(line,"%d", &gnumber[l]) ;

for (i=0;i<gnumber[l];i++)
scanf("%s",name[l]);
for (k=0;k<gnumber[l];k++)
{
scanf("%s",giver[l]);
scanf("%d %d",&a,&n);
for (i=0;i<n;i++)
scanf("%s",reciever[l]);

for (i=0;i<gnumber[l];i++)
if (strcmp(name[l],giver[l])==0)
{
if (n==0)
account[l]+=a;
else
{
account[l]+=-(a/n)*n;
break;
}
}
for (i=0;i<gnumber[l];i++)
for (j=0;j<n;j++)
if (strcmp(reciever[l][j],name[l])==0)
account[l]+=a/n;

}
gets(line);


}
for (m=0;m<l;m++)
{
for (i=0;i<gnumber[m];i++)
printf("%s %d\n",name[m],account[m]);
printf("\n");
}
for (i=0;i<gnumber[l];i++)
account[l]=0;

}

Pleease help!!
Thank you

[Nick]

OK, here's what i think some possible WA causes :

#include <stdio.h>
#include <math.h>
#include <string.h>
void main(void)
{

int i,j,k,l=0,m,a,n,gnumber[10000],account[10000][10]={0}; <------

(i think the way u initialize all elements of account to zero is imprecise

instead of that, why dont u add some code like this :
for (i=0;i<gnumber;i++)
{
account[l]=0;
}

before inputing the names of group members

)

char name[10000][10][12],giver[1000][12],reciever[10000][10][12],line[100];
for (l=0;;l++)
{
gets(line);
if (strlen(line) == 0)
break;
sscanf(line,"%d", &gnumber[l]) ;

for (i=0;i<gnumber[l];i++)
scanf("%s",name[l]);
for (k=0;k<gnumber[l];k++)
{
scanf("%s",giver[l]);
scanf("%d %d",&a,&n);
for (i=0;i<n;i++)
scanf("%s",reciever[l]);

for (i=0;i<gnumber[l];i++)
if (strcmp(name[l],giver[l])==0)
{
if (n==0)
account[l]+=a; <--------- when n is 0 u should leave account 0
else
{
account[l]+=-(a/n)*n;
break;
}
}
for (i=0;i<gnumber[l];i++)
for (j=0;j<n;j++)
if (strcmp(reciever[l][j],name[l])==0)
account[l]+=a/n;

}
gets(line);


}
for (m=0;m<l;m++)
{
for (i=0;i<gnumber[m];i++)
printf("%s %d\n",name[m],account[m]);
printf("\n");
}

for (i=0;i<gnumber[l];i++) <----- its not necessary to set account 0
account[l][i]=0; <------and it might cause judge's system to
consider it wrong

}



anyway.....tell me if u've got it fixed and accepted... and please post the accepted code as a reply
thx

[adikhosla]

Somebody please help me. I know I have written a bit of complicated code which could be shortened greatly, but please do help me to determine what is wrong with the current code.


[c]#include <stdio.h>
#include <string.h>
#include <ctype.h>
int i, x, y=0, m, l, ppl[10], t, temp, amt, ppls, temp2, temp3, ds=1;
char line[255], names[10][12], currline[15][12];
int main(void)
{
while(scanf(" %d\n", &i)!=EOF)
{
if(ds!=1) printf("\n");
for(temp=0; temp<255; temp++) line[temp]=32;

for(temp=0; temp<10; temp++) for(temp2=0; temp2<12; temp2++)
names[temp][temp2]=32;
l=0;
y=0;
gets(line);
for(x=0; x<(int)(strlen(line)); x++)
{
if((line[x]==32 && line[x-1]!=32) || x==(int)(strlen(line))-1)
{
if(x==(int)(strlen(line))-1) x++;
for(m=y; m<x; m++) names[l][m-y]=line[m];
names[l][m-y]='\0';
y=x+1;
l++;
} else if((line[x]==32 && line[x-1]==32)) y++;
}
for(temp2=0; temp2<10; temp2++) ppl[temp2]=0;
for(t=0; t<i; t++)
{
for(temp=0; temp<255; temp++) line[temp]=32;
for(temp=0; temp<15; temp++) for(temp2=0; temp2<12; temp2++)
currline[temp][temp2]=32;
l=0;
y=0;
gets(line);
for(x=0; x<(int)(strlen(line)); x++)
{
if((line[x]==32 && line[x-1]!=32) || x==(int)(strlen(line))-1)
{
if(x==(int)(strlen(line))-1) x++;
for(m=y; m<x; m++) currline[l][m-y]=line[m];
currline[l][m-y]='\0';
y=x+1;
l++;
}else if((line[x]==32 && line[x-1]==32)) y++;
}
for(temp=0; temp<i; temp++) if(strcmp(currline[0], names[temp])==0)
break;
for(temp2=0; temp2<2; temp2++)
{
if(isdigit(currline[temp2+1][1]))
{
if(isdigit(currline[temp2+1][2]))
{
if(isdigit(currline[temp2+1][3]))
{
if(temp2==0)
amt=(currline[temp2+1][0]-48)*1000+(currline[temp2+1][1]-48)*100+ (currline[temp2+1][2]-48)*10+(currline[temp2+1][3]-48);
else
ppls=(currline[temp2+1][0]-48)*1000+(currline[temp2+1][1]-48)*100+ (currline[temp2+1][2]-48)*10+(currline[temp2+1][3]-48);
}
else
{
if(temp2==0)
amt=(currline[temp2+1][0]-48)*100+(currline[temp2+1][1]-48)*10+ (currline[temp2+1][2]-48);
else
ppls=(currline[temp2+1][0]-48)*100+(currline[temp2+1][1]-48)*10+ (currline[temp2+1][2]-48);
}
}
else
{
if(temp2==0)
amt=(currline[temp2+1][0]-48)*10+(currline[temp2+1][1]-48);
else ppls=(currline[temp2+1][0]-48)*10+(currline[temp2+1][1]-48);
}
}
else
{
if(temp2==0) amt=(currline[temp2+1][0]-48);
else ppls=(currline[temp2+1][0]-48);
}
}
if(amt!=0)
{
if(ppls!=0)
{
ppl[temp]+=amt%ppls;
ppl[temp]-=amt;
amt=(amt-amt%ppls)/ppls;
for(temp2=0; temp2<ppls; temp2++)
{
for(temp3=0; temp3<i;temp3++) if(strcmp(names[temp3],
currline[temp2+3])==0 ) break;
ppl[temp3]+=amt;
}
}
else ppl[temp]+=amt;
}
}
for(temp2=0; temp2<i; temp2++) printf("%s %d\n", names[temp2], ppl[temp2]);
ds++;

}
return 0;
}[/c]

Thank You Very Much!

[karakX]

char line[255], names[10][12], currline[15][12];
^
this is a problem.
"no name is more than 12 characters in length"
but equal is acceptable.
Try the following test input
2
123456789012 123456789012
123456789012 0 0
123456789012 0 0

and your program write the names[0]="123456789012123456789012" becouse the '\0' character write the names[0][12]=names[1][0]

and

use the following functions,it is simply and (i think) fast.
_ void *memset (void *s, int c, size_t n);
Remarks:
memset sets the first n bytes of the array s to the character c.

And you can read the string in the consol

char stringx[100];
scanf("%s",&stringx);

Karak

[kurnia w]

you can use struct to make your code less complicated

[Md Masuqur Rahman]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void main()
{
int i,j,tk,div,k,taka[10][13],lp=0,l,tr[10],t;
char nam[10][14][15],str[20],other[12][12];

for(i=0;i<10;i++)
for(j=0;j<13;j++)
taka[j] = 0;

while(scanf("%d",&i) != EOF)
{
tr[lp] = i;
fflush(stdin);
for(j=0;j<i;j++)
scanf("%s",&nam[lp][j]);

nam[lp][j][0] = '\0';

for(j=0;j<i;j++)
{
scanf("%s %d %d",&str,&tk,&div);
k=0;
while(nam[lp][k][0] != '\0')
{
if(!strcmp(nam[lp][k],str))
break;
k++;
}

if(div!=0)
taka[lp][k] = taka[lp][k] + (tk%div - tk);

for(k=0;k<div;k++)
scanf("%s",other[k]);

other[k][0]='\0';

k=0;
while(other[k][0] != '\0')
{
l=0;
while(nam[lp][l][0] != '\0')
{
if(!strcmp(nam[lp][l],other[k]))
break;
l++;
}

if(div!=0)
taka[lp][l] = taka[lp][l] + (tk/div);
k++;
}
}
lp++;
}
l=0; t=0;
while(t<lp) {
while(l<tr[t])
{
printf("%s %d\n",nam[t][l], taka[t][l]);
l++;
}
if(t != (lp-1))
printf("\n");
t++;l=0;
}
}

[chunyi81]

Here is my program for problem 119 in Java. I do not understand why the judge keeps on giving WA. My program works fine with the sample input and gives the correct output.

[java]import java.io.*;
import java.util.*;
class Main {

static String ReadLn (int maxLg)
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}

catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}

public static void main(String[] args) {

String line;
int num = 0;
Vector V = new Vector();
String blank = "";
String[] people = null;
int[] gain = null;

while((line = ReadLn(255)) != null) {

StringTokenizer st = new StringTokenizer(line);

if (st.countTokens() == 1) {
num = Integer.parseInt(st.nextToken());
people = new String[num];
gain = new int[num];
}

else {

for (int i = 0;i < num;i++)
people = st.nextToken();

for (int k = 0;k < num;k++) {

if (k < num) {

line = ReadLn(255);
st = new StringTokenizer(line);

}

String giver = st.nextToken();
int amount = Integer.parseInt(st.nextToken());
int receiver = Integer.parseInt(st.nextToken());
int given = 0;
int j = search(people,giver);

if (receiver > 0)
given = amount / receiver;

while(st.hasMoreTokens()) {

int index = search(people,st.nextToken());
gain[index] += given;
gain[j] -= given;

}

}

printData(people,gain,V);
V.addElement(blank);

}

}

for (int i = 0;i < V.size() - 1;i++) {

if (((String)V.elementAt(i)).equals(""))
System.out.println();

else
System.out.println(V.elementAt(i));

}

}

public static int search(String[] people,String giver) {

for (int i = 0;i < people.length;i++)
if (people.compareTo(giver) == 0)
return i;

return -1;

}

public static void printData(String[] people,int[] gain,Vector V) {

for (int i = 0;i < people.length;i++)
V.addElement(people + " " + gain);

}

}[/java]

I print a blank line between groups using System.out.println(), no blank line after the last group, but judge says WA. What is wrong with my code?

[chunyi81]

Never mind, I think I found the problem. I forgot to consider the possibility that a group can have only 1 person.

[chunyi81]

My program also fails for a group containing 2 persons only. It only prints out the data for 1 person only.

[Noim]

I have accepted this problem. But i got two WA before Ac this problem. I have a question about this problem:

if the input is as follow:

2
noim nahid
noim 10 0
nahid 9 0

what should be the output?

the problem states that:

Any money not given is kept and is part of a person's ``net worth'' printed in the output.

so both noim and nahid kept their money to them.
So, should not the ouput be noim 10 and nahid 9 ?????? but i got WA for that.

when i output noim 0 and nahid 0 for above input i got AC. Why so?

[Joseph Kurniawan]

For each group of gift-givers, the name of each person in the group should be printed on a line followed by the net gain (or loss) received (or spent) by the person.

To compute the net / loss, we surely need the value of the money in the first time and the final value of the money. The money that is kept is part of the total money we have.
First condition:
noim = 10
nahid = 9

There aren't any transaction between them, so they gain nothing and lose nothing (net = loss = 0).
That's why the output should be all zeroes.