Project Euler Problem 307
Finally solved using this book. Project Euler problem 307 requires a bit knowledge of counting technique so i recommend you to read couple of chapters of An Introduction to Probability Theory and Its Applications by William Feller. The required probability will be 1.0-p(1)-p(2) where p(1) and p(2) are probability of chips having one and two defects per chip respectively. Calculation of p(1) is relatively easy but p(2) requires some trick. First defect can be put in any of N chips , second defect can be put in any of N chips …..Kth defect can be put in any of N chips so total number of ways = N^K. How many ways we can put K defects into N chips such that each chip has only one defect. First defect can be put into any of N chips , second can be put into any of (N-1) chips ………… Kth defect can be any of (N-K+1) chips so total number ways is N*(N-1)…….(N-K+1).Now things are bit complicated. We will try to mix 2 defects per chip and 1 defect per chip. How many ways we can chose 2 defects out of K defects and put it into one of N available chips[chip having two defect ] and remaining (K-2) defects into (N-1) available chips[one defect per chip]. Clearly its (K Chose 2) *N *[(N-1)(N-2)......(N-k+2)]. How many ways we can put 4 defects out of K defects in 2 chips [ 2 defects per chip ] and remaining (K-4) defects into (N-2) places [ one defect per chip].This would be (K Chose 2) *N ((K-2) Chose 2 )(N-1)*[(N-2)......(N-k+3)]. There is little catch in previous expression. Since ordering is not important so we have to divide it by 2![ 2 factorial]. We will continue till we haven’t distributed all K defects into K/2 chips [ 2 defects per chip]. It will be (K Chose 2) *N *((k-2) Chose 2) *(N-1)*((K-4) Chose 2 )*(N-2) ………… Since ordering is not important we have to divide it by factorial of Number of chips having 2 defects which is K/2[2 defects per chip]. So total probability will be 1.0-(favorable/total).
Favorable is N*(N-1)*(N-2)……..(N-k+1)+ (K Chose 2) *N*(N-1)…..(N-k+2)+ (K Chose 2) *((K-2) Chose 2)*N*(N-1)…(N-k+3)/2! + (K Chose 2) *((K-2) Chose 2)*((K-4) Chose 2)N*(N-1)…(N-k+4)/3! + ……….
Total is N^K. Hope i explained it. Source code for problem
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
typedef long double d64;
int main()
{
int n=1000000,k=20000,p,d;
long double tot=k*logl(n*1.0),fav=0,ret=0,tmp=0,fact=0;
for(int i=n-k+1;i<=n;i++) fav+=logl(i*1.0);
ret+=expl(fav-tot);
p=n-k+1,d=1;
for(int i=0;i<k;i+=2)
{
tmp+=(logl((k-i)*1.0)+logl((k-i-1)*1.0)-logl(2.0));
fav-=logl(p*1.0);
fact+=logl(d*1.0);
ret+=expl(tmp+fav-fact-tot);
p++,d++;
}
printf("%.10llf\n",1.0-ret);
}
SPOJ problem INTEGMAX
This problem ask to maximize the area of polygon.The area of polygon having n points 0.5 [y_0(x_n-1-x_1)+y_1(x_0-x_2)+ y_2(x_2-x_3)+.............+y_n-1(x_n-2-x_0)].There are K points given but we have two more points on the X axis (x_0,0) and (x_K-1,0) so we have to add these two points into x_array and y_array but these two points are fixed so we can permute only K points of y_array not the whole K+2 points[we have to exclude y_0 and y_K+1].Calculate all the difference of x_array in the given area formula but remember we have y_0 and y_n-1 [first and last point y coordinate which are fixed ] are 0 so we don’t need (x_n-1-x_1) and (x_n-2-x_0) so remove it from x_array. Now sort the difference in both increasing and decreasing order and take the maximum of both.
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
typedef pair<int,int> PI;
vector<long long> vx,vy,ret;
int main()
{
long long t,k;
double sum_1,sum_2,sum;
int n;
while(scanf("%lld",&t) && t!=-1)
{
vx.clear(),vy.clear(),ret.clear();sum_1=sum_2=sum=0;
for(int i=0;i<t;i++) scanf("%lld",&k),vx.push_back(k);
for(int i=0;i<t;i++) scanf("%lld",&k),vy.push_back(k);
vx.push_back(vx[0]);
vx.push_back(vx[t-1]);
sort(vx.begin(),vx.end());
sort(vy.begin(),vy.end());
n=t+2;
for(int i=0;i<n;i++) ret.push_back(vx[(n+i-1)%n]-vx[(i+1)%n]);
ret.erase(ret.begin(),ret.begin()+1);
ret.erase(ret.end()-1,ret.end());
sort(ret.begin(),ret.end());
for(int i=0;i<t;i++) sum_1+=ret[i]*vy[i];
sort(ret.rbegin(),ret.rend());
for(int i=0;i<t;i++) sum_2+=ret[i]*vy[i];
sum=max(fabs(sum_1),fabs(sum_2))*0.5;
printf("%.1lf\n",sum);
}
}
SPOJ Problem FUNFACT
This problem requires Stirling approximation and binary search.We search for lower bound value for (n+1) and this value will be upper bound for n. Source code for problem.
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
long long stirling(long long k)
{
double ret,n=k*1.0;
ret=n*log(n)-n+0.5*log(2*M_PI*n)+(1.0/12.0/n)-(1.0/360.0/n/n/n)+(1.0/1260.0/n/n/n/n/n)-(1.0/1680/n/n/n/n/n/n/n);
return ((long long)(ret*log10(M_E))+1LL);
}
int main()
{
long long t,n;
for(scanf("%lld",&t);t>0;t--)
{
scanf("%lld",&n);
n++;//search for lower bound for (n+1)
long long lo=1LL,hi=1LL<<31,mid;
while(lo<hi)
{
mid=(lo+hi)>>1;
if(stirling(mid)<n) lo=mid+1;
else hi=mid;
}
mid=(lo+hi)>>1;
printf("%lld\n",mid-1);
}
}
SPOJ Problem ROOTCIPH
This problem is kind of cryptic in first reading but reading carefully reveals that it simply asking about (x_1^2+x_2^2+x_3^2) where x_1,x_2,x_3 is root of cubic equation. [roots are the coordinates of the aircraft relative to the radar.]. a=-(x_1+x_2+x_3), b=x_1*x_2+x_2*x_3+x_1*x_3 , c=-(x_1*x_2*x_3) .
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
int t;
long long a,b,c;
for(scanf("%d",&t);t>0;t--)
{
scanf("%lld%lld%lld",&a,&b,&c);
cout<<a*a-2*b<<endl;
}
}
SPOJ Problem ABSURD
This problem ask you to find to a integer in range [0.95*c,1.05*c] whose absurdity is less than c. One way is to brute force but this will time limit exceed. Others are you take higher limit and keep putting 5 and 0 on last and check if higher number is still larger than lower and keep calculating absurdity of number this way . Source code for problem.
#include<cstdio>
#include<iostream>
using namespace std;
int absurdity(int n)
{
int cnt=0;
bool f=0;
while(n%10==0) n/=10;
if(n%10==5) f=1;
while(n) cnt++,n/=10;
if(f==1) return 2*cnt-1;
else return 2*cnt;
}
string int2string(int n)
{
string s="";
while(n) s=char(n%10+'0') + s,n/=10;
return s;
}
int string2int(string s)
{
int tmp=0;
for(int i=0;i<s.size();i++) tmp=tmp*10+(s[i]-'0');
return tmp;
}
int main()
{
int t,c,abrd_c,abrd_t;
bool f;
for(scanf("%d",&t);t>0;t--)
{
scanf("%d",&c);
abrd_c=absurdity(c);
int l=0.95*c,h=1.05*c;
abrd_t=absurdity(h);
string s=int2string(h);
//cout<<l+1<<" "<<h<<" "<<abrd_c<<endl;
f=1;
string tmp=s;
if(tmp[tmp.size()-1]>='5')
{
char ss=tmp[tmp.size()-1];
tmp[tmp.size()-1]='5';
if(string2int(tmp)>=(l+1)) abrd_t=absurdity(string2int(tmp));
else
{
tmp[tmp.size()-1]=ss;
f=0;
}
}
if(tmp[tmp.size()-1]>='0')
{
char ss=tmp[tmp.size()-1];
tmp[tmp.size()-1]='0';
if(string2int(tmp)>=(l+1)) abrd_t=absurdity(string2int(tmp));
else
{
tmp[tmp.size()-1]=ss;
f=0;
}
}
for(int i=tmp.size()-2;i>=1 && f;i--)
{
char ss=tmp[i];
if(tmp[i]>='5')
{
tmp[i]='5';
if(string2int(tmp)>=(l+1)) abrd_t=absurdity(string2int(tmp));
else //we are not able to decrease this number further
{
tmp[i]=ss;
f=0;
}
}
if(tmp[i]>='0')
{
tmp[i]='0';
if(string2int(tmp)>=(l+1)) abrd_t=absurdity(string2int(tmp));
else
{
tmp[i]=ss;
f=0;
}
}
}
if(abrd_t<abrd_c) cout<<"absurd\n";
else cout<<"not absurd\n";
//till now i have checked for last position.now start from second last keep doing until
/*for(int i=l+1;i<=h;i++) //calculate the min absurdity in the given range
{
abrd_t=absurdity(i);
cout<<i<<" "<<abrd_t<<endl;
if(abrd_t<abrd_c) {f=1;break;}
}
if(f==1) cout<<"absurd\n";
else cout<<"not absurd\n";*/
}
}
About
Hello All, My name is Mukesh Tiwari and I graduated from IIITM Gwalior in 2009. I am passionate about programming and mathematics. I love solving problems on SPOJ , UVA , Topcoder and Project Euler. I am curious about functional languages specially Haskell and it’s one the excellent language I encountered after python. I am also looking for some challenging functional programming job specially related to Haskell. You can reach me mukeshtiwariDOTiiitmATgmailDOTcom. Replace DOT with . and AT with @
Recent Comments
