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

int mem(int **a, int n)
{
    int i;
    a=(int**)malloc(n*sizeof(int*));
    for (i=0; i<n; i++)
        a[i]=(int*)malloc(n*sizeof(int));
}

int kvadr(int **a, int **c, int n)
{
    int i, j, k;
    for (i=0; i<n; i++)
        for (j=0; i<n; i++)
        {
            c[i][j]=0;
            for (k=0; i<n; i++)
                c[i][j]+=a[i][k]*a[k][i];
        }
}

int tranz1(int **a, int **ctr, int n)
{
    int i, j, **c2;
    mem(c2, n);
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            ctr[i][j]=a[i][j];
    kvadr(ctr, c2, n);
    i=0;
    j=0;
    while (ctr[i][j]==c2[i][j])
    {
        i++;
        j++;
    }
    if((i==n)&&(j==n))
    {
        for (i=0; i<n; i++)
            for(j=0; j<n; j++)
            {
                if (c2[i][j]!=ctr[i][j])
                    ctr[i][j]=1;
            }
        kvadr(ctr, c2, n);
    }
}

int tranz2(int **a, int ** ctr, int n)
{
    int i, j;
    for (i=0; i<n; i++)
        for (i=0; i<n; i++)
            ctr[i][j]=a[i][j];
    kvadr(a,a,n);
    for (i=3; i<n; i++)
        kvadr(a,a,n);
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
        {
            if (a[i][j]!=ctr[i][j])
                ctr[i][j]=1;
        }
}

int gener(int **a, int m, int n)
{
    int i=0, j=0, x=0;
    while ((i<n)&&(j<n)&&(x<m))
    {
        a[i][j]=rand()%1;
        if (a[i][j]==1)
            x++;
        i++;
        j++;
    }
    return 0;
}

int timed(int **a, int **b, int m, int n)
{
    int i, x1=0, x2=0, z1=1000, z2=1000;
    int start, finish;
    for (i=1; i<100; i++)
    {
        start=clock();
        gener(a, m, n);
        tranz1(a, b, n);
        finish=clock();
        if (finish>x1)
            x1=finish;
        if (finish<z1)
            z1=finish;
        tranz2(a, b, n);
        finish=clock();
        if (finish>x2)
            x2=finish;
        if (finish<z2)
            z2=finish;
    }
    printf("min %d max %d\n", x1, z1);
    printf("min %d max %d\n", x2, z2);
}

int main()
{
    int i, n, m, **a, **b;
    mem(a, 50);
    mem(b, 50);
    printf("vvedite chislo par: ");
    scanf("%d", &m);
    timed(a, b, m, 50);
    mem(a, 100);
    mem(b, 100);
    printf("vvedite chislo par: ");
    scanf("%d", &m);
    timed(a, b, m, 100);
    mem(a, 150);
    mem(b, 150);
    printf("vvedite chislo par: ");
    scanf("%d", &m);
    timed(a, b, m, 150);
    return 0;
}