#include "stdafx.h"
#define N 8
#include <set>
using namespace std;

class number{
    int up;
    int down;
public:
    number(const number& n):up(n.up),down(n.down){}
    number(int n=0):up(n),down(1){}
    number& operator+=(const number& n);
    number& operator-=(const number& n);
    number& operator*=(const number& n);
    number& operator/=(const number& n);
    bool is_zero()const{return down!=0&&up==0;}
    bool is_valid()const{return down!=0;}
    bool is_one()const{return down!=0&&up==down;}
    bool operator==(const number& n)const{return
        is_valid()&&n.is_valid()&&n.down*(long long)up==n.up*(long long)down;}
    bool operator<(const number& n)const;
    bool operator>(const number& n)const{return n<*this;}
    bool operator<=(const number& n)const{return !(*this>n);}
    bool operator!=(const number& n)const{return !(n==*this);}
    bool operator>=(const number& n)const{return !(*this<n);}
    number operator+(const number& n)const{number m(*this);return m+=n;}
    number operator-(const number& n)const{number m(*this);return m-=n;}
    number operator*(const number& n)const{number m(*this);return m*=n;}
    number operator/(const number& n)const{number m(*this);return m/=n;}
    bool is_integer()const{return down!=0&&up%down==0;}
    int get_integer()const{if(is_integer())return up/down;else return -1;}
    number& operator=(int n){up=n;down=1;return *this;}
    int get_up()const{return up;}
    int get_down()const{return down;}
        number abs()const{number x;x.up=up>=0?up:-up;x.down=down>=0?down:-down;return x;}
};

number& number::operator +=(const number& n)
{
    up=up*n.down+down*n.up;
    down*=n.down;
    return *this;
}

number& number::operator -=(const number& n)
{
    up=up*n.down-down*n.up;
    if(up<0)up=-up;
    down*=n.down;
    return *this;
}

number& number::operator *=(const number& n)
{
    up*=n.up;
    down*=n.down;
    return *this;
}

number& number::operator /=(const number& n)
{
    down*=n.up;
    up*=n.down;
    return *this;
}

bool number::operator <(const number &n)const
{
    return (long long)up*n.down<n.up*(long long)down;
}

bool has_set(int x[],int size)
{
    int mask=0;
    int i;
    char fName[20];
    for(i=0;i<size;i++){
        mask|=1<<(x[i]-1);
    }
    sprintf(fName,"data\\%d",mask);
    FILE *pFile=fopen(fName,"rb");
    if(pFile==NULL)
        return false;
    fclose(pFile);
    return true;
}

#define BUFF_LEN 4096
number buff[BUFF_LEN];
number buff2[BUFF_LEN];

void output_r(int i)
{
    int s=(1<<i)-1;
    char fName[20];
    sprintf(fName,"data\\%d",s);
    FILE *pFile=fopen(fName,"rb");
    if(pFile==NULL){
        fprintf(stderr,"Cannot read file %s\n",fName);
        exit(-1);
    }
    int yu=fread(buff,sizeof(number),BUFF_LEN,pFile);
    int x=1,start;
    if(buff[0]==0)start=1;else start=0;
    while(buff[start]<=x){
                if(buff[start]<x){
                        start++;
                }else{
                        x++;
                        start++;
                }
        if(start>=yu){
            if(yu==BUFF_LEN){
                yu=fread(buff,sizeof(number),BUFF_LEN,pFile);
                start=0;
                if(yu==0)break;
            }else break;
        }
    }
    printf("r[%d]=%d\n",i,x);
    fclose(pFile);
}

void save_set(const set<number>& result, int x[],int size)
{
    int mask=0;
    int i;
    char fName[20];
    for(i=0;i<size;i++){
        mask|=1<<(x[i]-1);
    }
    sprintf(fName,"data\\%d",mask);
    FILE *pFile=fopen(fName,"wb");
    if(pFile==NULL){
        fprintf(stderr,"Cannot write file %s\n",fName);
        exit(-1);
    }
    int j;
    set<number>::const_iterator cit;
    i=j=0;
    for(cit=result.begin();cit!=result.end();++cit){
        buff[j++]=*cit;
        i++;
        if(j==BUFF_LEN){
            j=0;
            fwrite(buff,sizeof(number),BUFF_LEN,pFile);
        }
    }
    if(j>0){
        fwrite(buff,sizeof(number),j,pFile);
    }
    fclose(pFile);

    if((mask&(mask+1))==0){
        output_r(size);
    }
}


void add_result(set<number>& result, int y[],int yc,int z[],int zc)
{
    int mask=0;
    int i,j;
    char fName[20];
    FILE *yFile,*zFile;
    int yu,zu;
    if(yc<=2){
        if(yc==1){
            yu=1;
            buff[0]=y[0];
        }else{
            yu=5;
            buff[0]=y[0]+y[1];
            buff[1]=abs(y[0]-y[1]);
            buff[2]=y[0]*y[1];
                        buff[3]=number(y[0])/y[1];
                        buff[4]=number(y[1])/y[0];
        }
        yFile=NULL;
    }else{
        mask=0;
        for(i=0;i<yc;i++){
            mask|=1<<(y[i]-1);
        }
        sprintf(fName,"data\\%d",mask);
        yFile=fopen(fName,"rb");
        if(yFile==NULL){
            fprintf(stderr,"Cannot read file %s\n",fName);
            exit(-1);
        }
        yu=fread(buff,sizeof(number),BUFF_LEN,yFile);
    }
    if(zc<=2){
        if(zc==1){
            zu=1;
            buff2[0]=z[0];
        }else{
            zu=5;
            buff2[0]=z[0]+z[1];
            buff2[1]=abs(z[0]-z[1]);
            buff2[2]=z[0]*z[1];
                        buff2[3]=number(z[0])/z[1];
                        buff2[4]=number(z[1])/z[0];
        }
        zFile=NULL;
    }else{
        mask=0;
        for(i=0;i<zc;i++){
            mask|=1<<(z[i]-1);
        }
        sprintf(fName,"data\\%d",mask);
        zFile=fopen(fName,"rb");
        if(zFile==NULL){
            fprintf(stderr,"Cannot read file %s\n",fName);
            exit(-1);
        }
        zu=fread(buff2,sizeof(number),BUFF_LEN,zFile);
    }
    if(zu<BUFF_LEN){
        do{
            for(i=0;i<zu;i++)for(j=0;j<yu;j++){
                result.insert(buff2[i]+buff[j]);
                result.insert(buff2[i]*buff[j]);
                result.insert((buff2[i]-buff[j]).abs());
                                number x=buff2[i]/buff[j];
                                if(x.is_valid()){
                                        result.insert(x);
                                }
                                x=buff[j]/buff2[i];
                                if(x.is_valid()){
                                        result.insert(x);
                                }
            }
            if(yu<BUFF_LEN)break;
            yu=fread(buff,sizeof(number),BUFF_LEN,yFile);
        }while(1);
    }else if(yu<BUFF_LEN){
        do{
            for(i=0;i<zu;i++)for(j=0;j<yu;j++){
                result.insert(buff2[i]+buff[j]);
                result.insert(buff2[i]*buff[j]);
                result.insert((buff2[i]-buff[j]).abs());
                                number x=buff2[i]/buff[j];
                                if(x.is_valid()){
                                        result.insert(x);
                                }
                                x=buff[j]/buff2[i];
                                if(x.is_valid()){
                                        result.insert(x);
                                }
            }
            if(zu<BUFF_LEN)break;
            zu=fread(buff2,sizeof(number),BUFF_LEN,zFile);
        }while(1);
    }else{
        do{
            do{
                for(i=0;i<zu;i++)for(j=0;j<yu;j++){
                    result.insert(buff2[i]+buff[j]);
                    result.insert(buff2[i]*buff[j]);
                    result.insert((buff2[i]-buff[j]).abs());
                                        number x=buff2[i]/buff[j];
                                        if(x.is_valid()){
                                                result.insert(x);
                                        }
                                        x=buff[j]/buff2[i];
                                        if(x.is_valid()){
                                                result.insert(x);
                                        }
                }
                if(yu<BUFF_LEN)break;
                yu=fread(buff,sizeof(number),BUFF_LEN,yFile);
            }while(1);
            if(zu<BUFF_LEN)break;
            zu=fread(buff2,sizeof(number),BUFF_LEN,zFile);
            if(zu==0)break;
            fseek(yFile,0,SEEK_SET);
            yu=fread(buff,sizeof(number),BUFF_LEN,yFile);
        }while(1);
    }
    if(yFile)fclose(yFile);
    if(zFile)fclose(zFile);
}


void gen_set(int x[],int size)
{
    int y[N],z[N];
    int i,j,yc,zc;
    if(size<=2)return;
    if(has_set(x,size))return;
    set<number> result;
    for(i=1;i<(1<<size)-1;i+=2){
        yc=zc=0;
        for(j=0;j<size;j++){
            if(i&(1<<j)){
                y[yc++]=x[j];
            }else{
                z[zc++]=x[j];
            }
        }
        gen_set(y,yc);
        gen_set(z,zc);
        add_result(result,y,yc,z,zc);
    }
    save_set(result,x,size);
}

int bc(int x){
        int c=0;
        while(x>0){
                if(x&1)c++;
                x>>=1;
        }
        return c;
}

int _tmain(int argc, _TCHAR* argv[])
{
    system("mkdir data");
    int x[]={1,2,3,4,5,6,7,8};
        int i;
        for(i=7;i<1<<12;i++){
                if(bc(i)<=8){
                        int j=0,k;
                        for(k=0;k<12;k++){
                                if(i&(1<<k)){
                                        x[j++]=k+1;
                                }
                        }
                        gen_set(x,j);
                }
        }
        return 0;
}