#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/types.h>

// #include <iostream.h>
// #include <iomanip.h>
#include <time.h>     // for seconds()

#define MaxDim  100
#define Rand_Max  100000

// Prototypes

void seedRandom(unsigned int );
double randomn(void );
double seconds(void );
int max_iter (int *, int );
int max_rec (int *, int );
int ord_ins_rec (int *, int *, int );
void gera_tabela(int );
void print_tabela(int );
void ordem_camp(int );



// Variáveis Globais

int Tabela[MaxDim][MaxDim];

int Conjunto[MaxDim];
int Pi[MaxDim];
int Primeiro;

int Dim;


// Programa Principal

int main()
{
	int i, k, el, j, ret;

	printf(" Digite o numero de times: ");
	scanf("%d", &Dim);


	// Geração da Tabela de Resultados

	gera_tabela(Dim);

	// Impressão da Tabela de Resultados

	if(Dim < 15)
	{
	   print_tabela(Dim);
	}
	getchar();


	// Encontra a Ordem

	ordem_camp(Dim);



	el = Primeiro;
	k = 1;
	printf("\n Ordem\n\n %3d", el);
	while ( Pi[el] >=0 )
	{
		printf(" %3d", Pi[el]);
		if (k==10)
		{
			k=0;
			printf("\n");
		}
		el = Pi[el];
	}
	printf("\n");
	printf(" Verificacao \n");


	for(j=0; j<Dim; j++)
	{
	  if(Pi[j] >= 0)
	  {
		printf("%d:%d %d \n",j,Pi[j],Tabela[j][Pi[j]]);
	  }
	  else
	  {
		printf("%d:%d Ultimo \n",j,Pi[j]);
	  }
	}

    getch();

	return(0);
}

//
//  Problema: Dados os resultados de um torneio entre n times
//            onde todos jogam contra todos em um turno e onde
//            não há empates, deteminar uma ordem dos times em
//            que o primeiro vence o segundo, o segundo vence o
//            terceiro e assim por diante.
//


void ordem_camp(int n)
{
	int anterior, curr, continua;

	printf(" Chamada para n=%d\n", n);

	if (n == 2)
	{
	    //  Caso Base
	    printf(" Caso Base !!! n=%d \n", n);
	    getchar();
		if(Tabela[0][1] == 1)
		{
			Primeiro = 0; Pi[0]=1; Pi[1]=-1;
		}
		else
		{
			Primeiro = 1; Pi[1]=0; Pi[0]=-1;
		}
		getch();
	}
	else
	{

		ordem_camp(n-1);

		// Vamos inserir o n-esimo elemento (chamado n-1 n ordem)
        // Passo Indutivo

        getch();

		if (Tabela[Primeiro][n-1] == 0)
		{
			Pi[n-1] = Primeiro;
			Primeiro = n - 1;
		}
		else
		{
			anterior = Primeiro;
			curr = Pi[anterior];
			continua = 1;

			while ( continua )
			{
				if ( Pi[curr] == -1 )
				{
					Pi[curr] = n-1;
					Pi[n-1] = -1;
					continua = 0;
				}
				else
				{
					if (Tabela[curr][n - 1] == 0) // n-1 venceu curr
					{
						Pi[n-1] = Pi[anterior];
						Pi[anterior] = n - 1;
						continua = 0;
					}
					anterior = curr;
					curr = Pi[anterior];
				}
			}
		}
            printf(" apos passo indutivo n=%d\n", n);
	int el = Primeiro;
	int k = 1;
	printf("\n Ordem\n\n %3d", el);
	while ( Pi[el] >=0 )
	{
		printf(" %3d", Pi[el]);
		if (k==10)
		{
			k=0;
			printf("\n");
		}
		el = Pi[el];
	}
	printf("\n");

            getch();
	}
}

//  Gera Tabela

void gera_tabela(int n)
{
	int i,j;
	for(i=0; i<n-1; i++)
	{
		for(j=i+1; j<n; j++)
		{
			if(randomn() < 0.5)
			{
				Tabela[i][j]=1;
			}
			else
			{
				Tabela[i][j]=0;
			}
		}
	}
}


//  Print Tabela

void print_tabela(int n)
{
	int i,j;
	for(i=0; i<n-1; i++)
	{
		for(j=i+1; j<n; j++)
		{
			printf("%d:%d %d ",i,j,Tabela[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}




// System dependent routines
// File: system.cpp


void seedRandom(unsigned int seed)
// seed for random number generator.
{
  srand(seed);
  return;
}

double randomn(void)
// random number between 0.0 and 1.0 (uncluded).
{
  double rrr;

  rrr = (double) rand() / (double) RAND_MAX;
  return rrr;
}

double seconds()
// cpu time in seconds since start of run.
{
  double secs;

  secs = (double)(clock() / 1000.0);
  return(secs);
}