10417  Gift Exchanging
Moderator: Board moderators

 New poster
 Posts: 10
 Joined: Tue Nov 26, 2002 4:19 pm
10417  Gift Exchanging
Can any body explain the algo....... Is it pure math....??
I try calculating the probabilities ... but i always endup getting wrong answer
please help
I try calculating the probabilities ... but i always endup getting wrong answer
please help
10417
Could anyone please tell me, what's the correct answer for
or
???
Thanks in advance,
Tobias
Is it2
2 0 0 0 0
0.5 0.0 0.0 0.5 0.0
0.4 0.0 0.2 0.4 0.0
Code: Select all
1 0.556
Code: Select all
1 0.500
Thanks in advance,
Tobias
Thanks for the lightning fast response, but then I've no clue what's wrong with my code...
I'm just checking all possible distributions of the gifts and multiply up the respective probabilities:
[cpp]#include <iostream>
#include <stdio.h>
int num[5], n, t;
double prob[5][12];
double res[5];
int bestpos;
double calc(int fr) { // friend
if (fr>=n) return 1.0; // all friends checked
double P=0.0;
for(int i=0;i<5;i++) { // for each kind of gift
if (num) {
num;
P += prob[fr] * calc(fr+1); // recursive call
++num;
}
if (!fr) { // best friend
res = P;
if (!bestpos  res[bestpos1]<P) bestpos=i+1;
P = 0.0;
}
}
return P;
}
int main() {
cin>>t; // number of testcases (1<=t<=10)
while(cin>>n) { // number of friends (1<=n<=12)
t;
bestpos=0;
for(int i=0;i<5;i++) cin >> num; // read number of gifts of each kind
for(int j=0;j<n;j++) for(int i=0;i<5;i++) cin >> prob[j]; // read probabilities
calc(0); // start rec. calc with first friend
printf( "%d %0.3f\n", bestpos, res[bestpos1]/(res[0]+res[1]+res[2]+res[3]+res[4])/num[bestpos1]);
}
return 0;
}[/cpp]
I'm just checking all possible distributions of the gifts and multiply up the respective probabilities:
[cpp]#include <iostream>
#include <stdio.h>
int num[5], n, t;
double prob[5][12];
double res[5];
int bestpos;
double calc(int fr) { // friend
if (fr>=n) return 1.0; // all friends checked
double P=0.0;
for(int i=0;i<5;i++) { // for each kind of gift
if (num) {
num;
P += prob[fr] * calc(fr+1); // recursive call
++num;
}
if (!fr) { // best friend
res = P;
if (!bestpos  res[bestpos1]<P) bestpos=i+1;
P = 0.0;
}
}
return P;
}
int main() {
cin>>t; // number of testcases (1<=t<=10)
while(cin>>n) { // number of friends (1<=n<=12)
t;
bestpos=0;
for(int i=0;i<5;i++) cin >> num; // read number of gifts of each kind
for(int j=0;j<n;j++) for(int i=0;i<5;i++) cin >> prob[j]; // read probabilities
calc(0); // start rec. calc with first friend
printf( "%d %0.3f\n", bestpos, res[bestpos1]/(res[0]+res[1]+res[2]+res[3]+res[4])/num[bestpos1]);
}
return 0;
}[/cpp]

 New poster
 Posts: 8
 Joined: Thu Jul 31, 2003 2:36 pm
i think your max is the one not div num.Tobbi wrote:Thanks for the lightning fast response, but then I've no clue what's wrong with my code...
I'm just checking all possible distributions of the gifts and multiply up the respective probabilities:
if div it result will be different.
My english is poor,hope this will help.
I like AC
 Christian Schuster
 Learning poster
 Posts: 63
 Joined: Thu Apr 04, 2002 2:00 am
More than one year since the last post  let me revive that one!
I finally got this one AC after lots of WAs. The essential point is not to write "1 0.251" when you could write "2 0.251".
Personally, I think this is misleading and incorrect, as box 1 with a value of 0.2514 is definitely a better choice than box 2 with 0.2505.
I finally got this one AC after lots of WAs. The essential point is not to write "1 0.251" when you could write "2 0.251".
Personally, I think this is misleading and incorrect, as box 1 with a value of 0.2514 is definitely a better choice than box 2 with 0.2505.
10417  Gift Exchanging
could somebody explain the sample I/O ..?
I'm so poor at math. .;
input
output
thanks.. ^_^
I'm so poor at math. .;
input
Code: Select all
2
1 0 0 1 0
0.5 0.0 0.0 0.5 0.0
0.4 0.0 0.5 0.1 0.0
Code: Select all
4 0.800
Last edited by helloneo on Tue May 22, 2007 8:09 am, edited 1 time in total.
In the first sample case, there are two guests.
The 1st person (your friend), can bring a box of type A or D with equal probability.
The 2nd person can bring boxes: A with probability 0.4, C  0.5, D  0.1.
You also know, that there is 1 box of type A, and 1 box of type D.
Let's make a table, which lists all possible combinations of gifts, which could be brought by the guests, and their probabilities:
Of all these cases, you are only interested in those, in which there's one box of type A and one box of type D, namely:
Now, if you choose a box of type A, the chances that it's from your friend (the 1st person) are: (1*0.05 + 0*0.20) / (0.05+0.20) = 0.20.
If you choose a box of type D, you'll pick the right box with probability: (0*0.05 + 1*0.20) / (0.05+0.20) = 0.80.
So, in order to maximize the probability of picking a box from your friend, you should pick a box of type D (type #4), and the probability will be: 80%.
The 1st person (your friend), can bring a box of type A or D with equal probability.
The 2nd person can bring boxes: A with probability 0.4, C  0.5, D  0.1.
You also know, that there is 1 box of type A, and 1 box of type D.
Let's make a table, which lists all possible combinations of gifts, which could be brought by the guests, and their probabilities:
Code: Select all
1st person's box 2nd person's box Probability
A A 0.5*0.4 = 0.20
A C 0.5*0.5 = 0.25
A D 0.5*0.1 = 0.05
D A 0.5*0.4 = 0.20
D C 0.5*0.5 = 0.25
D D 0.5*0.1 = 0.05
Code: Select all
1st 2nd Probability
A D 0.05
D A 0.20
If you choose a box of type D, you'll pick the right box with probability: (0*0.05 + 1*0.20) / (0.05+0.20) = 0.80.
So, in order to maximize the probability of picking a box from your friend, you should pick a box of type D (type #4), and the probability will be: 80%.