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


const int K = 20;
const int N = K+12;

void randseed();
void packets(int M[N][K]);
void pr(int M[N][K]);
int swap(int M[N][K], int i, int j);
int doxor(int M[N][K], int i, int j);
int lu(int M[N][K], int p, int NN);
int dolu(int M[N][K], int NN);
int recv(int M[N][K]);
double rate(int T, int suc[N+1]);
void packets_degree(int M[N][K], int d);
void newp(int p[K], int q);

main()
{
  randseed();

  int suc[N+1];
  int T=500;

  double S;
  S=rate(T,suc);
  printf("S=%f\r\n",S);

  for(int i=K;i<=N;i++)
    printf("%2d, %f\r\n",i-K,(double)suc[i]/T);

}

double rate(int T, int suc[N+1])
{
  int M[N][K];
  for(int i=0;i<=N;i++)
    suc[i]=0;
  for(int t=0;t<T;t++)
  {
    packets_degree(M,3);
    int n=K+recv(M);
    for(int i=n;i<=N;i++)
      suc[i]++;
    if(n==N)
     printf("%3d, %2d\n",t,n);
  }
  double S;
  for(int i=0;i<=N;i++)
    S+=(double)suc[i]/T;
  return S;
}

int recv(int M[N][K])
{
  int r=0;
  for(int i=0;i<K;i++)
  {
    while(!lu(M,i,K+r))
    {
      r++;
      if(K+r>N)
        return N-K+1;
    }
  }
  return r;
}

int dolu(int M[N][K], int NN)
{
  for(int i=0;i<K;i++)
  {
    if(!lu(M,i,NN))
      return 0;
  }
  return 1;
}

int lu(int M[N][K], int p, int NN)
{
  int i;
  for(i=p;i<NN;i++)
    if(M[i][p])
      break;
  if(i>=NN)
    return 0;
  if(i!=p)
    swap(M,p,i);
  for(i=p+1;i<N;i++)
    if(M[i][p])
      doxor(M,i,p);
  return 1;  
}

int doxor(int M[N][K], int i, int j)
{
  for(int k=0;k<K;k++)
    M[i][k]^=M[j][k];
}

int swap(int M[N][K], int i, int j)
{
  for(int k=0;k<K;k++)
  {
    int tm;
    tm=M[i][k];
    M[i][k]=M[j][k];
    M[j][k]=tm;
  }
}

void pr(int M[N][K])
{
  printf("M[%d][%d]=\r\n",N,K);
  for(int i=0;i<N;i++)
  {
    printf("%3d:",i);
    for(int j=0;j<K;j++)
      printf(" %s",M[i][j]?"X":"-");
    printf("\r\n");
  }
}

void newp(int p[K], int q)
{
  for(int i=0;i<K;i++)
    p[i]=0;

  for(int n=0;n<q;n++)
  {
    int i = rand()%(K-n);
    int j = -1;
    for(;i>=0;i--)
    {
      j++;
      for(;p[j];j++)
        ;
    }
    p[j]=1;
  }
}

void packets_degree(int M[N][K], int d)
{
  for(int i=0;i<N;i++)
    newp(M[i],d);
}

void packets(int M[N][K])
{
  for(int i=0;i<N;i++)
    for(int j=0;j<K;j++)
      M[i][j]=rand()%2;
}

void randseed()
{
  int ti=time(0);
  printf("srand=%d\r\n",ti);
  srand(ti);
}