/* POTM ENTRY: mudpack */
/* Your Name: Doug Jones */
/* Your email: daj@esun.ho.att.com */

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

#include <sys/types.h>
#include <sys/times.h>
#include <limits.h>

#define MAXN	200
#define MAXPSZ	(MAXN/3+4)

int nNumbers;				/* number of numbered balls */
char triple[MAXPSZ][MAXPSZ][MAXPSZ];	/* !=0 if number triple covered */
int numCount[MAXPSZ];			/* counter used for tie breaking */

#define TRIPLE(N1,N2,N3)	triple[N1][N2][N3]

/*
 *	Flags number triple N1,N2,N3 as covered.
 *	Sets all permutations so that the code that checks doesn't have to.
 *	I don't remember why the assignments aren't inside the if block.
 *	Its probably a mistake since I added the if late in the development.
 */
#define SETTRIPLE(N1,N2,N3)		\
	if (triple[N1][N2][N3] == 0) {	\
		numCount[N1]++;		\
		numCount[N2]++;		\
		numCount[N3]++;		\
	}				\
	triple[N1][N2][N3]= 1;		\
	triple[N1][N3][N2]= 1;		\
	triple[N2][N1][N3]= 1;		\
	triple[N2][N3][N1]= 1;		\
	triple[N3][N1][N2]= 1;		\
	triple[N3][N2][N1]= 1;

/*
 *	Array used to renumber the tickets to reduce the final sum.
 */
struct count_ {
	int origNumber;
	int newNumber;
	int count;
};
struct count_ countArray[MAXN+1]; 

struct ticket_ {
	int num[7];			/* usually the number minus one */
	struct ticket_ *next;
};
struct ticket_ *tickets = NULL;		/* linked list of tickets */
struct ticket_ *unusedTickets = NULL;	/* list of free ticket structures */
int nTickets;				/* number of tickets on tickets list */

int numPartitionTickets[MAXPSZ];	/* number of tickets needed to */
					/* completely cover a partition */
struct ticket_ *partitionTickets[MAXPSZ];/* tickets that cover a partition */

/*
 *	Recycles the tickets on list.
 */
void freeTickets(struct ticket_ *list)
{
	struct ticket_ *tp;
	while (list != NULL) {
		tp= list->next;
		list->next= unusedTickets;
		unusedTickets= list;
		list= tp;
	}
}

/*
 *	Adds a new ticket to the tickets list and records all the
 *	number triples that the ticket covers.
 */
void addTicket(int n1, int n2, int n3, int n4, int n5, int n6, int n7)
{
	struct ticket_ *tp;
	if (unusedTickets == NULL) {
		tp= (struct ticket_ *) malloc(sizeof(struct ticket_));
	} else {
		tp= unusedTickets;
		unusedTickets= unusedTickets->next;
	}
	tp->num[0]= n1;
	tp->num[1]= n2;
	tp->num[2]= n3;
	tp->num[3]= n4;
	tp->num[4]= n5;
	tp->num[5]= n6;
	tp->num[6]= n7;
	tp->next= tickets;
	tickets= tp;
	nTickets++;
	SETTRIPLE(n1,n2,n3);
	SETTRIPLE(n1,n2,n4);
	SETTRIPLE(n1,n2,n5);
	SETTRIPLE(n1,n2,n6);
	SETTRIPLE(n1,n2,n7);
	SETTRIPLE(n1,n3,n4);
	SETTRIPLE(n1,n3,n5);
	SETTRIPLE(n1,n3,n6);
	SETTRIPLE(n1,n3,n7);
	SETTRIPLE(n1,n4,n5);
	SETTRIPLE(n1,n4,n6);
	SETTRIPLE(n1,n4,n7);
	SETTRIPLE(n1,n5,n6);
	SETTRIPLE(n1,n5,n7);
	SETTRIPLE(n1,n6,n7);
	SETTRIPLE(n2,n3,n4);
	SETTRIPLE(n2,n3,n5);
	SETTRIPLE(n2,n3,n6);
	SETTRIPLE(n2,n3,n7);
	SETTRIPLE(n2,n4,n5);
	SETTRIPLE(n2,n4,n6);
	SETTRIPLE(n2,n4,n7);
	SETTRIPLE(n2,n5,n6);
	SETTRIPLE(n2,n5,n7);
	SETTRIPLE(n2,n6,n7);
	SETTRIPLE(n3,n4,n5);
	SETTRIPLE(n3,n4,n6);
	SETTRIPLE(n3,n4,n7);
	SETTRIPLE(n3,n5,n6);
	SETTRIPLE(n3,n5,n7);
	SETTRIPLE(n3,n6,n7);
	SETTRIPLE(n4,n5,n6);
	SETTRIPLE(n4,n5,n7);
	SETTRIPLE(n4,n6,n7);
	SETTRIPLE(n5,n6,n7);
}

/*
 *	Prints the final list of tickets.
 */
void printTickets()
{
	struct ticket_ *tp;
	for (tp=tickets; tp; tp=tp->next)
		printf("%d %d %d %d %d %d %d\n",tp->num[0],tp->num[1],
		  tp->num[2],tp->num[3],tp->num[4],tp->num[5],tp->num[6]);
}

/*
 *	Adds a copy of all tickets on list tp1 to the current tickets list.
 *	Adds offset to all the numbers as they are copied.
 */
void cloneTickets(struct ticket_* tp1, int offset)
{
	int i;
	struct ticket_ *tp2;
	for (; tp1; tp1=tp1->next) {
		if (unusedTickets == NULL) {
			tp2= (struct ticket_ *) malloc(sizeof(struct ticket_));
		} else {
			tp2= unusedTickets;
			unusedTickets= unusedTickets->next;
		}
		for (i=0; i<7; i++)
			tp2->num[i]= tp1->num[i]+offset;
		tp2->next= tickets;
		tickets= tp2;
	}
}

/*
 *	Makes a solution for the partition of size sz from the solution
 *	of size sz+1 by replacing the extra number with any value allowed
 *	(this happens when the final renumbering is done).
 *	This only gets used for sz==14, since makePartition gets
 *	a better answer for 15 than for 14.
 */ 
cloneBiggerPartition(int sz)
{
	int i;
	struct ticket_ *tp1,*tp2;
	freeTickets(partitionTickets[sz]);
	partitionTickets[sz]= NULL;
	for (tp1=partitionTickets[sz+1]; tp1; tp1=tp1->next) {
		if (unusedTickets == NULL) {
			tp2= (struct ticket_ *) malloc(sizeof(struct ticket_));
		} else {
			tp2= unusedTickets;
			unusedTickets= unusedTickets->next;
		}
		for (i=0; i<7; i++)
			tp2->num[i]= tp1->num[i]<sz ? tp1->num[i] : -1;
		tp2->next= partitionTickets[sz];
		partitionTickets[sz]= tp2;
	}
	numPartitionTickets[sz]= numPartitionTickets[sz+1];
}

/*
 *	Makes a solution for the partition of size sz from the solution
 *	of size sz-1 by adding tickets that missing number with all pairs
 *	of the other numbers in groups of three.
 *	This only gets used for sz==16, which is good because it only
 *	work if sz-1 is divisble by 3.
 */ 
extendSmallerPartition(int sz)
{
	int i,j;
	freeTickets(partitionTickets[sz]);
	tickets= NULL;
	cloneTickets(partitionTickets[sz-1],0);
	nTickets= numPartitionTickets[sz-1];
	for (i=0; i<sz-3; i+=3)
		for (j=i+3; j<sz-3; j+=3)
			addTicket(i,i+1,i+2,j,j+1,j+2,sz-1);
	partitionTickets[sz]= tickets;
	numPartitionTickets[sz]= nTickets;
}

/*
 *	Makes tickets to completely cover triples involving numbers
 *	from 1 to sz (0 to sz-1 here).  Saves the results if its the
 *	best answer found so far.
 *	Uses a simple greedy heuristic that loops over all possible
 *	number triples and adds a ticket when it find one that needs
 *	to be covered.
 *	Start1 and start2 control two different methods for generating
 *	a starting solution.
 *	Cmult controls the tie breaking method.
 *	An old bug in the code is enabled if oldbug is not 0,
 *	this works better than anything else for sz of 18.
 *	The pointers are used to move the array index multiplications
 *	out of the inner loops, without them the runtime for large sz
 *	would exceed the 10 minute limit.
 */
void makePartition(int sz, int start1, int start2, int cmult, int oldbug)
{
	int n1,n2,n3;
	int n4,n5,n6,n7,s,si,bs,i,j,c,bc;
	char *p12,*p13,*p14,*p15,*p23,*p24,*p25,*p34,*p35,*p45;
	char *p1i,*p2i,*p3i,*p4i,*p5i;
	tickets= NULL;
	nTickets= 0;
	for (n1=0; n1<sz; n1++) {
		numCount[n1]= 0;
		for (n2=0; n2<sz; n2++)
			for (n3=0; n3<sz; n3++)
				triple[n1][n2][n3]= 0;
	}
	if (start1) {
		n7= (sz-3) / 4;
		n6= 3 + n7*4;
		n7--;
		for (i=6; i<n6; i+=4)
			addTicket(0,1,2,i-3,i-2,i-1,i);
		j= 0;
		for (i=0; i<n7; i++) {
			n1= 7 + 2*(2*(j%n7) + j/n7);
			j= (j+1) % (2*n7);
			n2= 7 + 2*(2*(j%n7) + j/n7);
			j= (j+1) % (2*n7);
			addTicket(0,3,4,n1,n1+1,n2,n2+1);
		}
		j= 1;
		for (i=0; i<n7; i++) {
			n1= 7 + 2*(2*(j%n7) + j/n7);
			j= (j+1) % (2*n7);
			n2= 7 + 2*(2*(j%n7) + j/n7);
			j= (j+1) % (2*n7);
			addTicket(0,5,6,n1,n1+1,n2,n2+1);
		}
	}
	if (start2) {
		for (n1=1; n1<sz-1; n1+= 2)
			for (n2=n1+2; n2<sz-1; n2+= 2)
				for (n3=n2+2; n3<sz-1; n3+= 2)
					if (triple[0][n1][n2]==0 &&
					  triple[0][n1][n3]==0 &&
					  triple[0][n2][n3]==0)
						addTicket(0,n1,n1+1,n2,n2+1,
						  n3,n3+1);
	}
	for (n1=0; n1<sz; n1++) {
		for (n2=n1+1; n2<sz; n2++) {
			for (n3=n2+1; n3<sz; n3++) {
				if (triple[n1][n2][n3])
					continue;
				p12= triple[n1][n2];
				p13= triple[n1][n3];
				p23= triple[n2][n3];
				bs= 0x7fffffff;
				for (i=0; i<sz; i++) {
					if (i==n1 || i==n2 || i==n3)
						continue;
					si= p12[i] + p13[i] + p23[i];
					p1i= triple[n1][i];
					p2i= triple[n2][i];
					p3i= triple[n3][i];
					for (j=i+1; j<sz; j++) {
						if (j==n1 || j==n2 || j==n3)
							continue;
						s= si +
						  p12[j] + p13[j] + p23[j] +
						  p1i[j] + p2i[j] + p3i[j];
						if (s < bs) {
							bs= s;
							bc= cmult*numCount[i] +
							  cmult*numCount[j];
							n4= i;
							n5= j;
						} else if (s == bs) {
							c= cmult*numCount[i] +
							  cmult*numCount[j];
							if (c > bc) {
								bs= s;
								bc= c;
								n4= i;
								n5= j;
							}
						}
					}
				}
				p14= triple[n1][n4];
				p15= triple[n1][n5];
				p24= triple[n2][n4];
				p25= triple[n2][n5];
				p34= triple[n3][n4];
				p35= triple[n3][n5];
				p45= triple[n4][n5];
				bs= 0x7fffffff;
				for (i=0; i<sz; i++) {
					if (i==n1 || i==n2 || i==n3 ||
					  i==n4 || i==n5)
						continue;
					si= p12[i] + p13[i] + p14[i] + p15[i] +
					  p23[i] + p24[i] + p25[i] + p34[i] +
					  p35[i] + p45[i];
					p1i= triple[n1][i];
					p2i= triple[n2][i];
					p3i= triple[n3][i];
					p4i= triple[n4][i];
					p5i= triple[n5][i];
					for (j=i+1; j<sz; j++) {
						if (j==n1 || j==n2 || j==n3 ||
						  j==n4 || j==n5)
							continue;
						s= si +
						  p12[j] + p13[j] + p14[j] +
						  p15[j] + p23[j] + p24[j] +
						  p25[j] + p34[j] + p35[j] +
						  p45[j] + p1i[j] + p2i[j] +
						  p3i[j] + p4i[j] + p5i[j];
						if (oldbug)
							s-= p4i[j]+p5i[j];
						if (s < bs) {
							bs= s;
							bc= cmult*numCount[i] +
							  cmult*numCount[j];
							n6= i;
							n7= j;
						} else if (s == bs) {
							c= cmult*numCount[i] +
							  cmult*numCount[j];
							if (c > bc) {
								bs= s;
								bc= c;
								n6= i;
								n7= j;
							}
						}
					}
				}
				addTicket(n1,n2,n3,n4,n5,n6,n7);
			}
		}
	}
	if (nTickets < numPartitionTickets[sz]) {
		freeTickets(partitionTickets[sz]);
		numPartitionTickets[sz]= nTickets;
		partitionTickets[sz]= tickets;
	} else {
		freeTickets(tickets);
	}
}

/*
 *	Tries to find the best solution for a partition of size sz
 *	by running the greedy heuristic with various parameters.
 */
void makeBestPartition(int sz)
{
	if (sz<7 || sz>=MAXPSZ)
		return;
	makePartition(sz,1,1,1,0);
	makePartition(sz,0,1,1,0);
	if (sz <= 40)
		makePartition(sz,0,0,1,0);
	if (sz <= 20) {
		makePartition(sz,0,0,0,0);
		makePartition(sz,1,1,-1,0);
		makePartition(sz,0,0,0,1);
	}
}

/*
 *	Initializes the partition solution arrays and finds solutions
 *	for partition sizes from nNumbers/3-4 to nNumbers/3+4.
 *	Starts at nNumbers/3 and works its way outward.
 *	Stops early if the run time gets close to the limit.
 */
void initPartitions()
{
	int i,m;
	clock_t limit;
	struct tms t;
	for (i=0; i<MAXPSZ; i++) {
		numPartitionTickets[i]= 0x0fffffff;
		partitionTickets[i]= NULL;
	}
	m= nNumbers/3;
	times(&t);
	limit= 9*60*CLK_TCK + 3*(t.tms_utime+t.tms_stime);
	makeBestPartition(m);
	times(&t);
	limit-= 2*(t.tms_utime+t.tms_stime);
	for (i=1; i<5; i++) {
		makeBestPartition(m+i);
		times(&t);
		if (t.tms_utime+t.tms_stime > limit)
			break;
		makeBestPartition(m-i);
		times(&t);
		if (t.tms_utime+t.tms_stime > limit)
			break;
	}
	for (i=MAXPSZ-2; i>7; i--)
		if (partitionTickets[i]!=NULL &&
		  partitionTickets[i+1]!=NULL &&
		  numPartitionTickets[i]>numPartitionTickets[i+1])
			cloneBiggerPartition(i);
	for (i=10; i<MAXPSZ; i+=3) {
		m= (i-1)/3;
		if (partitionTickets[i]!=NULL &&
		  partitionTickets[i-1]!=NULL &&
		  numPartitionTickets[i]>numPartitionTickets[i-1]+m*(m-1)/2)
			extendSmallerPartition(i);
	}
}

/*
 *	Comparison function used to sort countArray in decreasing count order.
 */
int countCompare(struct count_ *p1, struct count_ *p2)
{
	return p2->count - p1->count;
}

/*
 *	Comparison function used to sort countArray in origNumber order.
 */
int origCompare(struct count_ *p1, struct count_ *p2)
{
	return p1->origNumber - p2->origNumber;
}

/*
 *	Renumbers the tickets to reduce the sum.
 *	Also assigns values to tickets that have don't care entries (<0).
 */
void minimizeTotal()
{
	int i,j,k;
	struct ticket_ *tp;
	for (i=0; i<=nNumbers; i++) {
		countArray[i].origNumber= i;
		countArray[i].count= 0;
	}
	for (tp=tickets; tp; tp=tp->next) {
		for (i=0; i<7; i++) {
			if (tp->num[i] > nNumbers)
				tp->num[i]= 0;
			countArray[tp->num[i]].count++;
		}
	}
	qsort(countArray+1,nNumbers,sizeof(struct count_),
	 (int(*)(const void *,const void *))countCompare);
	for (i=1; i<=nNumbers; i++)
		countArray[i].newNumber= i;
	countArray[0].newNumber= 0;
	qsort(countArray+1,nNumbers,sizeof(struct count_),
	 (int(*)(const void *,const void *))origCompare);
	for (tp=tickets; tp; tp=tp->next) {
		for (i=0; i<7; i++)
			tp->num[i]= countArray[tp->num[i]].newNumber;
		for (i=0; i<7; i++) {
			if (tp->num[i] == 0) {
				for (j=1; j<7; j++) {
					for (k=0; k<7; k++)
						if (tp->num[k] == j)
							break;
					if (k == 7)
						break;
				}
				tp->num[i]= j;
			}
		}
	}
}

main(int argc, char**argv)
{
	int p1,p2,p3,sz,bestsz,bestp1,bestp2,bestp3;
	nNumbers= atoi(argv[1]);
	if (nNumbers > 21) {
		/*
		 *	Divide nNumbers into three parts and generate
		 *	tickets to completely cover each part.
		 *	Then loop over all ways to partition nNumbers into
		 *	three to find the best one.
		 */
		initPartitions();
		bestsz= 0x7fffffff;
		for (p1=7; p1<MAXPSZ; p1++) {
			for (p2=p1; p2<MAXPSZ; p2++) {
				p3= nNumbers-p1-p2;
				if (p3<7 || p3>=MAXPSZ)
					continue;
				sz= numPartitionTickets[p1] +
				  numPartitionTickets[p2] +
				  numPartitionTickets[p3];
				if (sz < bestsz) {
					bestsz= sz;
					bestp1= p1;
					bestp2= p2;
					bestp3= p3;
				}
			}
		}
		tickets= NULL;
		cloneTickets(partitionTickets[bestp1],1);
		cloneTickets(partitionTickets[bestp2],1+bestp1);
		cloneTickets(partitionTickets[bestp3],1+bestp1+bestp2);
		minimizeTotal();
		printTickets();
	} else if (nNumbers > 16) {
		printf("1 2 3 4 5 6 7\n");
		printf("8 9 10 11 12 13 14\n");
		printf("%d %d %d %d %d %d %d\n",
		  nNumbers-6,nNumbers-5,nNumbers-4,nNumbers-3,
		  nNumbers-2,nNumbers-1,nNumbers);
	} else if (nNumbers > 11) {
		printf("1 2 3 4 5 6 7\n");
		printf("%d %d %d %d %d %d %d\n",
		  nNumbers-6,nNumbers-5,nNumbers-4,nNumbers-3,
		  nNumbers-2,nNumbers-1,nNumbers);
	} else {
		printf("1 2 3 4 5 6 7\n");
	}
	exit(0);
}