i`ve been given an assignment from my lecturrer.
it`s about the "let`s dance!!" topic problem set no 10218
would somebody please help me , at least about the algorythm
i can`t even understand the problem
10218 - Let's Dance !!!
Moderator: Board moderators
-
- New poster
- Posts: 2
- Joined: Sat Jun 07, 2003 7:51 am
10218 - Let's Dance!!
could somebody please explain to me about problems no 10218
i can`t understand the problems totaly.
PLEASE........
i can`t understand the problems totaly.
PLEASE........
Yes...
Someone plz explain the problem description to us!! Thx in advance!!
Someone plz explain the problem description to us!! Thx in advance!!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Still... no reply... after half a year... ![:(](./images/smilies/icon_frown.gif)
![:(](./images/smilies/icon_frown.gif)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Is the sample input/output correct?
From the problem description, I do this for the second example input (10 20 7):
There are 30 people total. We choose any 7. Total number of possible groups is 30 choose 7 or 2,035,800.
Now, the only way to split CC equally among 2 groups is if the number of men is 0, 2, 4, or 6. The number of groups that exist are:
10 choose 0 * 20 choose 7 plus
10 choose 2 * 20 choose 5 plus
10 choose 4 * 20 choose 3 plus
10 choose 6 * 20 choose 1 equals 1,018,800
1,018,800 / 2,035,800 equals 0.5004421 which is not the expected 0.5002286.
Is there something in the problem that I'm misinterpreting?
I also wrote a brute force checker and the numbers turn out as above.
From the problem description, I do this for the second example input (10 20 7):
There are 30 people total. We choose any 7. Total number of possible groups is 30 choose 7 or 2,035,800.
Now, the only way to split CC equally among 2 groups is if the number of men is 0, 2, 4, or 6. The number of groups that exist are:
10 choose 0 * 20 choose 7 plus
10 choose 2 * 20 choose 5 plus
10 choose 4 * 20 choose 3 plus
10 choose 6 * 20 choose 1 equals 1,018,800
1,018,800 / 2,035,800 equals 0.5004421 which is not the expected 0.5002286.
Is there something in the problem that I'm misinterpreting?
I also wrote a brute force checker and the numbers turn out as above.
hi all,
after a hard effort , i manage to solve this problem
.
i assume that, i have c candy and i am gonna give the first candy to one of all(w+m) people. after that i am ready to give second candy to again one of all (w+m) people. this mean the candy does not identical or something like that, but the order of the candy does not matter. and i also assume all the men are identical and all the women are identical. and a man can hold more than one candy or no candy which does not matter for this problem. i have to just distribute the candy to a group of man whatever one of them take more than one or all of the take more then one. and every time i am going to distribute the candy into all people .
i am not sure that i am using the right assumption to solve the problem. if i am wrong please tell me that .
i think these will help.
after a hard effort , i manage to solve this problem
![:lol:](./images/smilies/icon_lol.gif)
i assume that, i have c candy and i am gonna give the first candy to one of all(w+m) people. after that i am ready to give second candy to again one of all (w+m) people. this mean the candy does not identical or something like that, but the order of the candy does not matter. and i also assume all the men are identical and all the women are identical. and a man can hold more than one candy or no candy which does not matter for this problem. i have to just distribute the candy to a group of man whatever one of them take more than one or all of the take more then one. and every time i am going to distribute the candy into all people .
i am not sure that i am using the right assumption to solve the problem. if i am wrong please tell me that .
i think these will help.
__nOi.m....
-
- Experienced poster
- Posts: 196
- Joined: Wed May 02, 2007 10:12 pm
- Location: Hungary, Pest county, Halasztelek
- Contact:
Re: 10218 - Let's Dance!!
Here it is the exact values for the sample input:
As you can see in the first testcase the result is very close to 0.5, but it is differ from that in reality.
Code: Select all
f(10,20,20)=1743392201/3486784401
f(10,20,7)=1094/2187
Re: 10218 - Let's Dance !!!
The problem statement should be a little more clear.
It took me a while to figure out what the problem statement actually wants to say. We have m men and w women who are identical and c candies which are not identical. So, we have to take into account the type of candies that people receive, the distinction has to be made just between men and women and not which men or women gets the candy.
(c choose 0) * (p^0) * ((1-p)^c) + (c choose 2) * (p^2) * ((1-p)^(c-2)) + (c choose 4) * (p^4) * ((1-p)^(c-4)) + ---
this is the binomial expansion of ((a+b)^n + (-a+b)^n) / 2, where a = p; b = (1-p)
It took me a while to figure out what the problem statement actually wants to say. We have m men and w women who are identical and c candies which are not identical. So, we have to take into account the type of candies that people receive, the distinction has to be made just between men and women and not which men or women gets the candy.
- P(that a man gets a candy) = m / (m + w) = p
- P(that a women gets a candy) = w / (m + w) = (1 - p)
(c choose 0) * (p^0) * ((1-p)^c) + (c choose 2) * (p^2) * ((1-p)^(c-2)) + (c choose 4) * (p^4) * ((1-p)^(c-4)) + ---
this is the binomial expansion of ((a+b)^n + (-a+b)^n) / 2, where a = p; b = (1-p)