11500 - Vampires

[neilor]

Hello!

I Found the key to solve:
In http://en.wikipedia.org/wiki/Gambler%27s_ruin You can find the Both Formulas
The first one is to solve when AT = 3 (P2 = n1/(n1+n2))
The second one is to solve when AT != 3 (P1 = 1- (q/p)^n1... where q = (6-AT)/AT ...

Good lock

[naffi]

Gambler's Ruin is for D = 1, What about D != 1 ?

[898989]

Can you please give me more details? What is the approach for solving this problem?
and please elaborate more on "Gambler ruin"

[neilor]

Hi Naffi and Mostafa.

You can use to D !=1 also. You must calcule n1 and n2:

n1 = EV1/D (rounded to up) page 1 from article
n2 = EV2/D (rounded to up)

for at = 3 use the formula

prob =
n1
--------
n1 + n2

else

prob =

(1- (q/p)^n1 )
----------------
(1-(q/ ***

where (q/p) = (6-at)/at

the second prob formula including (***) can be found on link:
http://en.wikipedia.org/wiki/Gambler%27s_ruin ...

... in Unfair coin flipping
P1 = ...

... it is only to avoid to give here the complete answer,

good lock.

[naffi]

Thanks neilor for your kind elaboratin, I got AC.
But, I did not handle unfair coin flipping as you said, may be the test cases are fair.

[898989]

Hi, this is already how i did it, but last simple is not right.

Code: Select all

while(cin>>EV1>>EV2>>AT>>D && (EV1+EV2+D+AT))
	{
		clr(vis, 0);
		cout.setf(ios::fixed|ios::showpoint );
		cout.precision(1);

		double n1 = EV1/D, n2 = EV2/D;
		double p1, p2;

		if(AT == 3) {
			p1 = n1/(n1+n2);
			p2 = n2/(n1+n2);
		}
		else {	// won't work well if D != 1
			double q = (6-AT)/6.0, p = 1-q;
			p1 = (1.0-pow(q/p, n1)) / (1.0-pow(q/p, (n1+n2)));
			p2 = 1-p1;
		}

		cout<<p1*100<<" "<<p2*100<<"\n";
	}

[Jan]

My idea was to derive some equations, and then gaussian elimination.

[rehan]

can anyone tell me what is the wrong with my code
&
what i hav to add in this code
(it has done in C)

Code: Select all

#include<stdio.h>
#include<math.h>

int main()
{
unsigned long ev1,ev2,at,d,n1,n2;
double pr,m;

while(scanf("%lu%lu%lu%lu",&ev1,&ev2,&at,&d)==4)
{
 n1=ev1/d;
 n2=ev2/d;

 m=n1+n2;

 if(at==3)
 pr = (n1/m)*100;

else
{
 double q = (6-at)/6, p = 1-q;
         pr = (1-pow(q/p, n1)) / (1-pow(q/p, (n1+n2)));

}
printf("%.1lf\n",pr);

}
return 0;
}

[fidels]

You can also solve it without using the formula for the Gambler's Ruin... think memoization ;-D

[wallace]

Can I solve this problem using Markov's chain?

[forthright48]

I simply assumed that after 1000 moves, the probability becomes so small that it is negligible. Got AC with O(20*20*1000)