Логические задачи
      NazVa.net

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct{double x,y;}cplx;

typedef struct{double size;cplx center,orient;}square;

cplx newCplx(double x,double y){
    cplx z;
    z.x=x;
    z.y=y;
    return z;
}

square newSquare(double size,cplx center,cplx orient){
    square sq;
    sq.size=size;
    sq.center=center;
    sq.orient=orient;
    return sq;
}

cplx add(cplx z1,cplx z2){return newCplx(z1.x+z2.x,z1.y+z2.y);}

cplx subt(cplx z1,cplx z2){return newCplx(z1.x-z2.x,z1.y-z2.y);}

cplx mult(cplx z1,cplx z2){
    return newCplx(z1.x*z2.x-z1.y*z2.y,z1.x*z2.y+z1.y*z2.x);
}

cplx mult1(cplx z,double k){
    return newCplx(z.x*k,z.y*k);
}

cplx w1,w2,z1,z2;
double xMin,xMax,yMin,yMax,dX,dY;
double k;

square fSq1(square sq){
    double size=sq.size*0.8;
    cplx orient=mult(sq.orient,w1);
    cplx center=add(sq.center,mult(mult1(sq.orient,sq.size),z1));
    return newSquare(size,center,orient);
}

square fSq2(square sq){
    double size=sq.size*0.6;
    cplx orient=mult(sq.orient,w2);
    cplx center=add(sq.center,mult(mult1(sq.orient,sq.size),z2));
    return newSquare(size,center,orient);
}

double fXMin(square sq,int l,int l0){
    if(l==l0||sq.center.x-k*sq.size>xMin)return sq.center.x;
    double x1=fXMin(fSq1(sq),l+1,l0);
    double x2=fXMin(fSq2(sq),l+1,l0);
    double x=fmin(sq.center.x,fmin(x1,x2));
    if(x<xMin)xMin=x;
    return x;
}

double fXMax(square sq,int l,int l0){
    if(l==l0||sq.center.x+k*sq.size<xMax)return sq.center.x;
    double x1=fXMax(fSq1(sq),l+1,l0);
    double x2=fXMax(fSq2(sq),l+1,l0);
    double x=fmax(sq.center.x,fmax(x1,x2));
    if(x>xMax)xMax=x;
    return x;
}

double fYMin(square sq,int l,int l0){
    if(l==l0||sq.center.y-k*sq.size>yMin)return sq.center.y;
    double y1=fYMin(fSq1(sq),l+1,l0);
    double y2=fYMin(fSq2(sq),l+1,l0);
    double y=fmin(sq.center.y,fmin(y1,y2));
    if(y<yMin)yMin=y;
    return y;
}

double fYMax(square sq,int l,int l0){
    if(l==l0||sq.center.y+k*sq.size<yMax)return sq.center.y;
    double y1=fYMax(fSq1(sq),l+1,l0);
    double y2=fYMax(fSq2(sq),l+1,l0);
    double y=fmax(sq.center.y,fmax(y1,y2));
    if(y>yMax)yMax=y;
    return y;
}

int main()
{
    w1=newCplx(0.8,0.6);
    w2=newCplx(0.6,-0.8);
    z1=mult(subt(newCplx(-0.5,0.5),mult(newCplx(-0.4,-0.4),w1)),newCplx(0,-1));
    z2=mult(subt(newCplx(0.5,0.5),mult(newCplx(0.3,-0.3),w2)),newCplx(0,-1));
    xMin=xMax=yMin=yMax=0;
    k=4.5*sqrt(2);
    square sq=newSquare(1,newCplx(0,0),newCplx(0,1));
    int l=0;
    double dX=0,dY=0,dX0,dY0;
    double eps=1e-14;
    do{
        l+=10;
        dX0=dX,dY0=dY;
        fXMin(sq,1,l),fXMax(sq,1,l),fYMin(sq,1,l),fYMax(sq,1,l);
        dX=xMax-xMin,dY=yMax-yMin;
        printf("L = %d\n",l);
        printf("xMin = %18.15f\n",xMin);
        printf("xMax = %18.15f\n",xMax);
        printf("yMin = %18.15f\n",yMin);
        printf("yMax = %18.15f\n",yMax);
        printf("  dX = %18.15f\n",dX);
        printf("  dY = %18.15f\n\n",dY);
    }while(fabs(dX-dX0)>eps||fabs(dY-dY0)>eps);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 16
#define u16 unsigned short
#define u32 unsigned
#define max 20

typedef struct{u16 q[N];short nz;}u16N;
typedef struct{u16N u0,u1;}u16N2;
typedef struct{int n,g;}int2;
typedef struct{int len;int2* p;}int2arr;

u16N new16N(){u16N a;for(int i=0;i<N;i++)a.q[i]=0;a.nz=0;return a;}

int nZ(u16 q[N]){int cnt=N;for(int i=N-1;i>=0;i--)if(q[i])break;else cnt--;return cnt;}

u16N toU16N(u32 n){u16N a=new16N();a.q[0]=n;a.q[1]=(n>>16);a.nz=a.q[1]?2:(a.q[0]?1:0);return a;}

u16N sum(u16N a,u16N b){
    int m=a.nz>=b.nz?a.nz:b.nz;
    u16N s=new16N();
    u32 c=0;
    for(int i=0;i<m;i++){u32 t=c+a.q[i]+b.q[i];s.q[i]=t;c=t>>16;}
    if(c&&m<N)s.q[m]=1;
    s.nz=nZ(s.q);
    return s;
}

int cmp(u16N a, u16N b){
    int s=a.nz-b.nz;
    if(s)return s;
    for(int i=a.nz-1;i>=0;i--)if(s=a.q[i]-b.q[i])return s;
    return 0;
}

u16N inv(u16N a){
    u16N b;
    for(int i=0;i<N;i++)
    b.q[i]=~a.q[i];
    b.nz=nZ(b.q);
    return b;
}

u16N subt(u16N a, u16N b){return sum(a,sum(inv(b),toU16N(1)));}

u16N shL0(u16N a,int n){
    u16N b=new16N();
    u16 c=0;
    for(int i=0;i<a.nz;i++){u32 r=c|((u32)a.q[i]<<n);b.q[i]=r;c=r>>16;}
    if(a.nz<N)b.q[a.nz]=c;
    b.nz=nZ(b.q);
    return b;
}

u16N shL(u16N a,int n){
    u16N b=shL0(a,n&0xf);
    int n1=n>>4;
    if(n1)for(int i=a.nz;i>=0;i--){int j=i+n1;if(j<N)b.q[j]=b.q[i];if(i<N)b.q[i]=0;}
    b.nz=nZ(b.q);
    return b;
}

u16N shR(u16N a){
    u16N b=new16N();
    for(int i=a.nz-1;i>=0;i--){u32 u=(i==a.nz-1?0:a.q[i+1]);u32 w=(u<<16)|a.q[i];b.q[i]=(w>>1);}
    b.nz=nZ(b.q);
    return b;
}

int max1(u16N a){
    int k=-1;
    if(a.nz){for(int i=15;i>=0;i--)if((a.q[a.nz-1]>>i)&1){k=i;break;}k+=(a.nz-1)<<4;}
    return k;
}

u16N2 div2(u16N a,u16N b){
    u16N2 res;
    res.u0=new16N();
    int d=max1(a)-max1(b);
    if(d<0){res.u1=a;return res;}
    u16N bb=shL(b,d);
    if(cmp(a,bb)>=0){res.u0=toU16N(1);a=subt(a,bb);}
    while(cmp(bb,b)){
        bb=shR(bb);
        res.u0=shL(res.u0,1);
        int k=cmp(a,bb);
        if(k>=0){if(!res.u0.nz)res.u0.nz=1;res.u0.q[0]|=1;a=subt(a,bb);}
    }
    res.u1=a;
    return res;
}

void show(u16N a){
    if(!a.nz){printf("0\n");return;}
    int d[(int)(N*1.25)+1];
    int cnt=0;
    u16N b=toU16N(1000000);
    while(a.nz){u16N2 c=div2(a,b);d[++cnt-1]=c.u1.q[0]+((u32)c.u1.q[1]<<16);a=c.u0;}
    printf("%d",d[cnt-1]);
    for(int i=cnt-2;i>=0;i--)printf(" %06d",d[i]);
}

int2arr f(int n,int l){
    int q[max-1];
    int cnt=0;
    for(int i=0;i<l;i++)
        if((n>>i)&1)q[++cnt-1]=i;
    int q1[max],s[max];
    int cnt1=0;
    for(int i=0;i<cnt;i++)
        if(i==0){q1[0]=q[0];q1[1]=q[0]+1;s[0]=s[1]=1;cnt1=2;}
        else{
            if(q[i]==q1[cnt1-1])s[cnt1-1]++;
            else{q1[++cnt1-1]=q[i];s[cnt1-1]=1;}
            q1[++cnt1-1]=q[i]+1;s[cnt1-1]=1;
        }
    int2arr a;
    a.len=1<<cnt1;a.p=(int2*)malloc(a.len*sizeof(int2));
    for(int i=0;i<a.len;i++){
        int g=0;int n=0;
        for(int j=0;j<cnt1;j++){int k=(i>>j)&1;n|=k<<q1[j];if(k&&s[j]>1)g++;}
        a.p[i].n=n;a.p[i].g=g;
    }
    return a;
}

char* hms(char* time){
    char* hms=(char*)malloc(9*sizeof(char));
    for(int i=0;i<8;i++)hms[i]=time[i+11];
    hms[8]='\0';
    return hms;
}

int main(){
    printf("max=%d\n\n",max);
    int l=1;
    u16N* m=(u16N*)malloc(2*sizeof(u16N));
    m[0]=toU16N(0);m[1]=toU16N(1);
    while(l<max){
        int size=1<<l;
        int size1=1<<(l+1);
        u16N* m1=(u16N*)malloc(size1*sizeof(u16N));
        for(int i=0;i<size1;i++)m1[i]=new16N();
        for(int i=0;i<size;i++){
            int2arr a=f(i,l);
            for(int j=0;j<a.len;j++)m1[a.p[j].n]=sum(m1[a.p[j].n],shL0(m[i],a.p[j].g));
            free(a.p);
        }
        free(m);m=m1;l++;
        u16N s=new16N();
        for(int i=0;i<size1;i++)s=sum(s,m1[i]);
        int tm=time(0);
        printf("%s",hms(ctime(&tm)));
        printf("%4d = ",l);
        show(s);printf("\n\n");
    }
    free(m);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

#define N 500
#define u16 unsigned short
#define u32 unsigned

typedef struct{u16 q[N];short nz;}u16N;
typedef struct{u16N u0,u1;}u16N2;

u16N new16N(){u16N a;for(int i=0;i<N;i++)a.q[i]=0;a.nz=0;return a;}

u16N toU16N(u32 n){u16N a=new16N();a.q[0]=n;a.q[1]=(n>>16);a.nz=a.q[1]?2:(a.q[0]?1:0);return a;}

u16N sum(u16N a,u16N b){
    int m=a.nz>=b.nz?a.nz:b.nz;
    u16N s=new16N();
    u32 c=0;
    for(int i=0;i<m;i++){u32 t=c+a.q[i]+b.q[i];s.q[i]=t;c=t>>16;}
    if(c&&m<N)s.q[m]=1;
    s.nz=nZ(s.q);
    return s;
}

u16N inv(u16N a){
    u16N b;
    for(int i=0;i<N;i++)
    b.q[i]=~a.q[i];
    b.nz=nZ(b.q);
    return b;
}

u16N subt(u16N a, u16N b){return sum(a,sum(inv(b),toU16N(1)));}

int nZ(u16 q[N]){int cnt=N;for(int i=N-1;i>=0;i--)if(q[i])break;else cnt--;return cnt;}

u16N shL0(u16N a,int n){
    u16N b=new16N();
    u16 c=0;
    for(int i=0;i<a.nz;i++){u32 r=c|((u32)a.q[i]<<n);b.q[i]=r;c=r>>16;}
    if(a.nz<N)b.q[a.nz]=c;
    b.nz=nZ(b.q);
    return b;
}

u16N shL(u16N a,int n){
    u16N b=shL0(a,n&0xf);
    int n1=n>>4;
    if(n1)for(int i=a.nz;i>=0;i--){int j=i+n1;if(j<N)b.q[j]=b.q[i];if(i<N)b.q[i]=0;}
    b.nz=nZ(b.q);
    return b;
}

u16N shR(u16N a){
    u16N b=new16N();
    for(int i=a.nz-1;i>=0;i--){u32 u=(i==a.nz-1?0:a.q[i+1]);u32 w=(u<<16)|a.q[i];b.q[i]=(w>>1);}
    b.nz=nZ(b.q);
    return b;
}

int max1(u16N a){
    int k=-1;
    if(a.nz){for(int i=15;i>=0;i--)if((a.q[a.nz-1]>>i)&1){k=i;break;}k+=(a.nz-1)<<4;}
    return k;
}

int cmp(u16N a, u16N b){
    int s=a.nz-b.nz;
    if(s)return s;
    for(int i=a.nz-1;i>=0;i--)if(s=a.q[i]-b.q[i])return s;
    return 0;
}

void show10(u16N a, u16N b){
    u16 m[N];
    for(int i=N-1;i>=0;i--){
        u16 r=0;
        for(int j=0;j<16;j++){
            b=shR(b);
            r<<=1;
            if(cmp(a,b)>=0){a=subt(a,b);r|=1;}
        }
        m[i]=r;
    }
    int n=(int)(N*0.6);
    u16 d[n];
    int cnt=0;
    int k=0;
    while(k<N&&cnt<n){
        u32 c=0;
        for(int i=k;i<N;i++){
            u32 t=(u32)10000*m[i]+c;
            m[i]=t;
            c=t>>16;
        }
        d[++cnt-1]=c;
        for(int i=k;i<N;i++)
            if(!m[i]){k=i;break;}
    }
    for(int i=0;i<cnt;i++){printf(" %04d",d[i]);if((i+1)%15==0)printf("\n");}
    printf("\n");
}

u16N fn(int n,u16N*p){
    if(n>1){
        p[n]=shL(p[n-1],1);
        if(!(n&1))p[n]=subt(p[n],p[n>>1]);
    }
    return p[n];
}

int main()
{
    int size=N<<3;
    u16N* a=(u16N*)malloc(size*sizeof(u16N));
    a[0]=toU16N(0);a[1]=toU16N(1);
    u16N numin=toU16N(0);
    int i=0;
    while(i<size-1&&(N<<4)-max1(numin)>4)
        numin=sum(shL0(numin,2),fn(++i,a));
    u16N denom=shL(toU16N(1),i+i-1);
    show10(numin,denom);
    return 0;
}