# My Weblog

## Project Euler problem 155

Project euler problem 155 is simply based on recursion and dynamic programming. Using one capacitor you can build only one value circuit [ Say D(1)].Now second unit capacitor can be placed in either series or parallel to D(1) [ Say this configuration D(2)]. Now third unit can be place in same fashion to D(1) and D(2) until we put 18 unit capacitor. Configuration D(k) can be generated by putting D(1) and D(k-1) , D(2) and D(k-2) , D(3) and D(k-3) and so in series and parallel fashion. Try to generate the recursion tree and you can see the solution. Source code

```#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;

struct frac
{
int num,denum;
frac(int num,int denum)
{

this->num=num;
this->denum=denum;
}
bool operator<(struct frac f) const
{
return ( ( this->num ) * f.denum ) < ( ( this->denum ) * f.num );
}
bool operator==(struct frac f) const
{
return ( ( this->num ) * f.denum ) == ( ( this->denum ) * f.num );
}

};
set<struct frac> s[20],q;
int main()
{
int n;
cin>>n;
s[1].insert((struct frac) {1,1});
q.insert((struct frac) {1,1});
for(int i=1;i<n;i++)
{
int n_1,d_1;
for(set<struct frac> :: iterator it_1=s[i].begin();it_1!=s[i].end();it_1++)
{
n_1=it_1->num,d_1=it_1->denum;
for(int j=1;i+j<=n;j++)
{
int n_2,d_2;
for(set<struct frac> :: iterator it_2=s[j].begin();it_2!=s[j].end();it_2++)
{
n_2=it_2->num,d_2=it_2->denum;
s[i+j].insert((struct frac) {n_1*d_2+n_2*d_1,d_1*d_2});
s[i+j].insert((struct frac) {n_1*n_2,n_1*d_2+n_2*d_1});
q.insert((struct frac) {n_1*d_2+n_2*d_1,d_1*d_2});
q.insert((struct frac) {n_1*n_2,n_1*d_2+n_2*d_1});
}
}
}
}

cout<<q.size()<<endl;
//for(set<struct frac> :: iterator it=s[1].begin();it!=s[1].end();it++) cout<<(*it).num<<" "<<(*it).denum<<endl;
}
```