Greddy Gift Givers-USACO

[Guest]

Boas, estou a resolver o problema, ja tenho quase todo o codigo feito e so no final me apercebi que o meu output e o da USACO nao eram o mesmo o que recorri fazer a mao e mesmo assim o meu output nao é semelhante ao da usaco.

O Dave da 200 euros a tres pessoas logo fica com saldo negativo depois recebe 500 euros logo -200 + 500 = 300 mas no site indica como sendo 302

A laura não da nada mais recebe dois presentes de 66 e outro de 75 logo 66 + 75 = 141 que no site esta a 66.

O owen recebe 66 euros mas da 500 ao Dave logo 66-500 = -434 mas no site esta -359

a Vick recebe dois presentes de 66 e de 75 logo 66+75 = 141 e aqui o site e eu ja concordamos

O Amr não recebe presente mas da 150 euros.

O enunciado do problema: http://dpaste.com/761090/

Deixo de seguida o meu codigo mas ainda não acabado pois como disse em cima ainda me esta a dar o resultado mal.

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

#define MAXNAME 15

struct person{
char name[MAXNAME];
int money;
};

/* Get the index of the person */
int getname(char name[MAXNAME], struct person people[], int n_people)
{
int i;
for(i=0 ; i<n_people; i++)
	if((strcmp(name,people[i].name)) == 0)
		return i;
}



void distribute_money(FILE *fp, struct person people[], int n_people)
{
float total_amount = 0;
float total_people = 0;
float amount_per_people = 0;
char name[MAXNAME];
int i;
int index;
/* Get the name */  
fscanf(fp,"%s",name);
/* Get the amount of money */
fscanf(fp,"%f %f",&total_amount, &total_people);
/* Get the inicial money into the variable */
people[getname(name,people,n_people)].money -= total_amount;

/* How much money does each one gets */  
if(total_amount != 0 || total_people != 0)  
	amount_per_people = total_amount / total_people;
/* Reads the amount of people */
for(i=0; i<total_people; i++){
	/* Reads the people name */	  
	fscanf(fp,"%s",name);
	/* Search for the people name and add the money in there */
	people[getname(name,people,n_people)].money = (int)amount_per_people;
}
}

int main(void)
{
FILE *fp = fopen("gift1.in","r");
int n_people;
/* Get the number of people that will contribute to the gift */  
fscanf(fp,"%d",&n_people);
/* Declare an array of structs */  
struct person *people = malloc(n_people);
int i;

/* Puts the name in the structs */
for(i=0; i<=n_people; i++){
	fscanf(fp,"%s",people[i].name);
	people[i].money = 0;
}


for(i=0; i<=n_people;i++)
	distribute_money(fp,people,n_people);

fclose(fp);
fp = fopen("gift1.out","w");
for(i=0; i<n_people; i++)
	fprintf(fp,"%s %d\n",people[i].name,people[i].money);

fclose(fp);
return 0;
}

Agradeço desde já o tempo dispendido

[HappyHippyHippo]

estás a ver mal a lista de ofertas

não confirmei todas mas se a Vick da 150 quem os recebe ?

ps : já li melhor o enunciado e vi que estava errado, no entanto também tu.

quem recebe os 150/2 é a Vick e o owen e não a vick e a laura

pss: a razão porque o Dave fica com 302 no final é porque andas a mexer com floats (algo que o enunciado expressamente diz para não usar)

o dinheiro deve ser separado igualmente pelas pessoas sempre em números inteiros

no caso do dave, ao dividir 200 pelas 3 pessoas, dá 66 para cada um e fica com 2 por dividir (fica para ele)

Edited June 19, 2012 at 09:32 AM by HappyHippyHippo

[Warrior]

Acho que não deves ter percebido bem o enunciado.

O Dave tem 200 e dá a 3 pessoas, pelo que dá 66 a cada uma e fica com 2 para ele. Mais tarde, recebe 500 do Owen, ficando com 502.

O que o problema te pede é para dizer qual o ganho ou perda de cada um, ou seja, comparando com o inicial que quantidade deram ou receberam. No caso do Dave, 502-200 = 302, que é a resposta para ele.

[Guest]

Pois o problema deve estar ai pois eu estava a arredondar os valores.

[pmg]

O Dave da 200 euros a tres pessoas logo fica com saldo negativo depois recebe 500 euros logo -200 + 500 = 300 mas no site indica como sendo 302

Não! Estás a interpretar mal. O Dave dá 200/3 arredondado a 3 pessoas ... ou seja, ele dá 66 * 3 = 198 euros.

[Guest]

Alguem sabe qual é a falha na minha logica?

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

#define MAXNAME 15

struct person{
char name[MAXNAME];
int money;
};


/* Get the index of the person */
int getname(char name[MAXNAME], struct person people[], int n_people)
{
int i;
for(i=0 ; i<n_people; i++)
	if((strcmp(name,people[i].name)) == 0)
		return i;
}



void distribute_money(FILE *fp, struct person people[], int n_people)
{
float total_amount = 0;
float total_people = 0;
float amount_per_people = 0;
char name[MAXNAME];
int i;
/* Get the name */  
fscanf(fp,"%s",name);
/* Get the amount of money */
fscanf(fp,"%f %f",&total_amount, &total_people);
/* Get the inicial money into the variable */
people[getname(name,people,n_people)].money -= total_amount;

/* How much money does each one gets */  
if(total_amount != 0 || total_people != 0)  
	amount_per_people = total_amount / total_people;

/* Reads the amount of people */
for(i=0; i<total_people; i++){
	/* Reads the people name */	  
	fscanf(fp,"%s",name);
	/* Search for the people name and add the money in there */
	people[getname(name,people,n_people)].money = (int)amount_per_people;

	if(total_amount != (amount_per_people * total_people))
		people[getname(name,people,n_people)].money += (total_amount - (amount_per_people * total_people));

}

}

int main(void)
{
FILE *fp = fopen("gift1.in","r");
int n_people;
/* Get the number of people that will contribute to the gift */  
fscanf(fp,"%d",&n_people);
/* Declare an array of structs */  
struct person *people = malloc(n_people);
int i;

/* Puts the name in the structs */
for(i=0; i<=n_people; i++){
	fscanf(fp,"%s",people[i].name);
	people[i].money = 0;
}


for(i=0; i<=n_people;i++)
	distribute_money(fp,people,n_people);

fclose(fp);
fp = fopen("gift1.out","w");
for(i=0; i<n_people; i++)
	fprintf(fp,"%s %d\n",people[i].name,people[i].money);

fclose(fp);
return 0;
}

Meu output :

dave 500

laura 0

owen 75

vick 75

amr -150

[pmg]

Alguem sabe qual é a falha na minha logica?

   struct person *people = malloc(n_people);

Bem ... nao pesquisei a tua lógica suficientemente, mas este malloc não reserva espaço suficiente para n persons: reserve apenas n_people bytes.

Precisas de multiplicar

    struct person *people = malloc(n_people * sizeof *people);

[HappyHippyHippo]

já te disseram para não usar floats

/*float*/int total_amount = 0;
/*float*/int total_people = 0;
/*float*/int amount_per_people = 0;

nesta linha estás a apagar toda a informação de dinheiro existente e guardar o valor a ser recebido

 /* Search for the people name and add the money in there */
 people[getname(name,people,n_people)].money = (int)amount_per_people;

depois fazes isto

/* porque o if ??? */
if(total_amount != (amount_per_people * total_people))
 people[getname(name,people,n_people)].money += (total_amount - (amount_per_people * total_people));

[Guest]

o if serveria para ver se perco dados na divisão por exemplo 200/3 sao 66 mas na verdade é 66.6 logo esse 6 tera que ir po bolso do que deu o presente em primeiro lugar.

[HappyHippyHippo]

então porque não fazes simplesmente:

int total_amount = 0;
int total_people = 0;
int amount_per_people = 0;
int amount_self = 0;

...

amount_per_people = total_amount / total_people;
amount_self = total_amount % total_people;


// dar dinheiro as pessoas
for (...)
 people[...] += amount_per_people;

// ficar com o "troco"
people[...] += amount_self;

[Guest]

O problema é que tenho mesmo que usar float visto que se nao usar eu tenho uma execepção de ponto flutoante.

[HappyHippyHippo]

se todas as variáveis forem int, nunca vais ter problemas de virgula flutuante porque não existe virgula flutuante !!!!

[Guest]

Pois mas acontece que tenho....

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

#define MAXNAME 15

struct person{
   char name[MAXNAME];
   int money;
};


/* Get the index of the person */
int getname(char name[MAXNAME], struct person people[], int n_people)
{
   int i;
   for(i=0 ; i<n_people; i++)
       if((strcmp(name,people[i].name)) == 0)
           return i;
}



void distribute_money(FILE *fp, struct person people[], int n_people)
{
   int total_amount = 0;
   int  total_people = 0;
   int  amount_per_people = 0;
   char name[MAXNAME];
   int i;
   int amount_self;
   /* Get the name */   
   fscanf(fp,"%s",name);
   /* Get the amount of money */
   fscanf(fp,"%d %d",&total_amount, &total_people);
   /* Get the inicial money into the variable */
   people[getname(name,people,n_people)].money -= total_amount;

   /* How much money does each one gets */   
   if(total_amount != 0 || total_people != 0)   
       amount_per_people = total_amount / total_people;

   /*if(total_amount != (amount_per_people * total_people))
           people[getname(name,people,n_people)].money += (total_amount - (amount_per_people * total_people));*/
   amount_self = total_amount % total_people;
   people[getname(name,people,n_people)].money += amount_self;

   /* Reads the amount of people */
   for(i=0; i<total_people; i++){
       /* Reads the people name */       
       fscanf(fp,"%s",name);
       /* Search for the people name and add the money in there */
       people[getname(name,people,n_people)].money += (int)amount_per_people;

   }

}

int main(void)
{
   FILE *fp = fopen("gift1.in","r");
   int n_people;
   /* Get the number of people that will contribute to the gift */   
   fscanf(fp,"%d",&n_people);
   /* Declare an array of structs */   
   struct person *people = malloc(n_people * sizeof *people);
   int i;

   /* Puts the name in the structs */
   for(i=0; i<=n_people; i++){
       fscanf(fp,"%s",people[i].name);
       people[i].money = 0;
   }


   for(i=0; i<=n_people;i++)
       distribute_money(fp,people,n_people);

   fclose(fp);
   fp = fopen("gift1.out","w");
   for(i=0; i<n_people; i++)
       fprintf(fp,"%s %d\n",people[i].name,people[i].money);

   fclose(fp);
   return 0;
}

GDB:

(gdb) run
Starting program: /home/tiago/a.out

Program received signal SIGFPE, Arithmetic exception.
0x0000000000400834 in distribute_money ()