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

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

11500 - Vampires

Post by neilor » Mon Oct 06, 2008 10:33 pm

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

Post by naffi » Thu Oct 09, 2008 4:44 am

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

Post by 898989 » Tue Oct 14, 2008 8:47 am

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

Post by neilor » Sat Oct 18, 2008 3:53 am

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

Post by naffi » Sat Oct 18, 2008 2:19 pm

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

Post by 898989 » Sat Oct 18, 2008 5:42 pm

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

Post by Jan » Mon Dec 22, 2008 1:32 pm

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

Post by rehan » Sat Dec 27, 2008 2:35 pm

can anyone tell me what is the wrong with my code
&
what i hav to add in this code :oops: :oops: :oops: :oops: :oops: :oops: :oops: :oops: :oops: :oops: :oops:
(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

Post by fidels » Mon Mar 02, 2009 3:05 pm

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

Post by wallace » Sat Sep 11, 2010 1:49 am

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

Post by forthright48 » Tue May 06, 2014 10:20 pm

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

Post Reply

Return to “Volume 115 (11500-11599)”