My Weblog

Blog about programming and math

Project Euler problem 205

Project Euler problem 205 is related to probability. Probability of winning peter = favorable case for peter/ total cases.
Total cases are 4^9 * 6^6 . To find out favorable case for peter, find out for a particular throw by petet how many throw of colin is lagging. I counted all the throw of peter [it will be from 9 to 36] and colin [ it will be from 6 to 36].
Here is the out come of peter
( 9-> 1) ( 10-> 9) ( 11-> 45) ( 12-> 165) ( 13-> 486) ( 14-> 1206) ( 15-> 2598) ( 16-> 4950) ( 17-> 8451) ( 18-> 13051) ( 19-> 18351) ( 20-> 23607) ( 21-> 27876) ( 22-> 30276) ( 23-> 30276) ( 24-> 27876) ( 25-> 23607) ( 26-> 18351) ( 27-> 13051) ( 28-> 8451) ( 29-> 4950) ( 30-> 2598) ( 31-> 1206) ( 32-> 486) ( 33-> 165) ( 34-> 45) ( 35-> 9) ( 36-> 1)
For colin
( 6 -> 1) ( 7 -> 6) ( 8 -> 21) ( 9 -> 56) ( 10 -> 126) ( 11 -> 252) ( 12 -> 456) ( 13 -> 756) ( 14 -> 1161) ( 15 -> 1666) ( 16 -> 2247) ( 17 -> 2856) ( 18 -> 3431) ( 19 -> 3906) ( 20 -> 4221) ( 21 -> 4332) ( 22 -> 4221) ( 23 -> 3906) ( 24 -> 3431) ( 25 -> 2856) ( 26 -> 2247) ( 27 -> 1666) ( 28 -> 1161) ( 29 -> 756) ( 30 -> 456) ( 31 -> 252) ( 32 -> 126) ( 33 -> 56) ( 34 -> 21) ( 35 -> 6) ( 36 -> 1)
So favorable case for peter will (total number of way to get 9 by peter )*(total number of way to get less then 9 by colin)+ ( total number of way to get 10 by peter )*(total number of way to get less then 10 by colin)+ ……………..+ (total number of way to get 36 by peter )*(total number of way to get less then 36 by colin).

#include<cstdio>
#include<iostream>
using namespace std;

long long  pat[40],coll[40];
void recur_col(int n,int lev)
	{
		if(lev==5) {coll[n]++;return;}
		for(int i=1;i<=6;i++) recur_col(n+i,lev+1);
		return;
	}
void recur_pat(int n,int lev)
	{
		if(lev==8) {pat[n]++;return;}
		for(int i=1;i<=4;i++) recur_pat(n+i,lev+1);
	}
int main()
	{

		long long s_1=0,s_2=0,tot,win=0;
		for(int i=1;i<=6;i++) recur_col(i,0);
		for(int i=1;i<=4;i++) recur_pat(i,0);
		for(int i=9;i<=36;i++) s_1+=pat[i],cout<<"( "<<i<<"-> "<<pat[i]<<") ";cout<<endl;
		for(int i=6;i<=36;i++) s_2+=coll[i],cout<<"( "<<i<<" -> "<<coll[i]<<") ";cout<<endl;
		//cout<<s_1<<" "<<s_2<<endl;
		
		for(int i=9;i<=36;i++)
		{
			long long sum=0;
			for(int j=6;j<i;j++) sum+=coll[j];
			win+=pat[i]*sum;
		}
		//cout<<win<<" "<<s_1*s_2<<endl;	
		long double d_1=win*1.0,d_2=s_1*s_2*1.0;
		printf("%.7llf\n",d_1/d_2);	
	}
Advertisements

July 24, 2010 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: