#/usr/bin/env python

import Grafo
import random
import TSPOtimo
import sys
import GrafoUtils
import Heuristicas
from math import log,ceil


def GeraAleatorio(n=7):
	g=Grafo.Grafo(n)
	for i in range(1,n):
		for j in range(0,i) :
			g.insereAresta(i,j,random.randrange(0,20))
	return g

def getOtimo(g,n=7):
	TSPOtimo.visitaTSP(g)
	otimo = TSPOtimo.melhor_custo + 0.001
	for i in g.listaVertices():
		g.setCor(i,"branco")
	heuristica = GrafoUtils.custo_caminho(Heuristicas.VizinhoMaisProximo(g),g) + 0.001
	TSPOtimo.melhor_custo = None
	TSPOtimo.melhor_caminho = None

	print "%i  & %i  &  %i \\\\" %( heuristica, otimo, int( otimo*(0.5*ceil(log(n)) + 0.5) ))


if __name__ == '__main__' :
	n=int(sys.argv[1])
	g=GeraAleatorio(n)
	getOtimo(g,n)