## 11500 - Vampires

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

neilor
New poster
Posts: 10
Joined: Fri Oct 03, 2008 6:00 pm

### 11500 - Vampires

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
New poster
Posts: 23
Joined: Wed Mar 19, 2008 12:25 pm
Location: BUET, Bangladesh
Contact:

### Re: 11500 - Vampires - tips

Gambler's Ruin is for D = 1, What about D != 1 ?
Always At Your Help.
898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

### Re: 11500 - Vampires - tips

Can you please give me more details? What is the approach for solving this problem?
and please elaborate more on "Gambler ruin"
Sleep enough after death, it is the time to work.
Mostafa Saad
neilor
New poster
Posts: 10
Joined: Fri Oct 03, 2008 6:00 pm

### Re: 11500 - Vampires - tips

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
New poster
Posts: 23
Joined: Wed Mar 19, 2008 12:25 pm
Location: BUET, Bangladesh
Contact:

### Re: 11500 - Vampires - tips

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.
Always At Your Help.
898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

### Re: 11500 - Vampires - tips

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";
}
``````
Sleep enough after death, it is the time to work.
Mostafa Saad
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

### Re: 11500 - Vampires

My idea was to derive some equations, and then gaussian elimination.
Ami ekhono shopno dekhi...
HomePage
rehan
New poster
Posts: 5
Joined: Thu Dec 25, 2008 1:24 pm

### Re: 11500 - Vampires

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
New poster
Posts: 6
Joined: Thu Jan 25, 2007 4:07 pm
Location: La Plata, Argentina

### Re: 11500 - Vampires

You can also solve it without using the formula for the Gambler's Ruin... think memoization ;-D
wallace
New poster
Posts: 10
Joined: Thu Feb 26, 2009 4:03 pm

### Re: 11500 - Vampires

Can I solve this problem using Markov's chain?
forthright48
New poster
Posts: 37
Joined: Wed Mar 14, 2012 11:57 am
Location: Bangladesh
Contact:

### Re: 11500 - Vampires

I simply assumed that after 1000 moves, the probability becomes so small that it is negligible. Got AC with O(20*20*1000)
What ever happens, happens for good. Even when we get WA :p
http://www.forthright48.com