//-------------------------------------------------------------------
// enigma1359.c (c) 2005 by Charles Petzold (www.charlespetzold.com)
//
// "The Weaker Sex" by Susan Denham, New Scientist, 24 September 2005, page 52.
//
// N couples play round robin squash. Each of the 2N players plays
// every other player once.  At least one man and one woman have 
// scores that are prime.  The lowest scoring woman has a score 
// at least 3 times the highest scoring man.
//
// How many couples played? How many times did a man beat a woman?
//
// There are N couples and 2N players. The total number of matches is:
//
// 	(2N - 1) + (2N - 2) + ... + 1
//
// or:
//
//	(2N - 1)(2N)
//	------------ = (2N - 1)(N) = T
//	      2
//
// where T stands for Total.
//
// The number of matches where a man plays another man is:
//
//	(N - 1)(N)
//	---------- = U
//	     2
//
// and that's also the number of matches where a woman plays another woman.
// The U stands for Unisex.
// 
// It is useful to look at the scores of each player as a "partition" of the
// total number of matches. "A partition is a way of writing an integer n
// as a sum of positive integers..." (Eric W. Weisstein. "Partition." From 
// MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Partition.html)
//
// In this case, were writing T (the total scoare) as the sum of 2N scores for each
// of the 2N players. (If there is a player who wins no matches, then we're actually
// writing T as the sum of 2N-1 scores. Only one player can have no wins. If two
// players have no wins, then what happened to the match between those two?)
//
// For this exercise, let's write our partitions with the highest number first. 
// For example, if N = 5, then T = 45 and U = 10. The most lopsided distribution of
// scores among the 10 players is this partition of 45:
//
//	9 8 7 6 5 4 3 2 1 0
//
// Because we know that the lowest-scoring woman scored higher than the highest-
// scoring men, the 5 women's scores are the first five numbers, followed by the
// 5 men's scores.
//
// The two numbers in the center of the paritition are, in fact, the lowest women's
// score and the highest men's score. The former must be at least 3 times the latter.
// These two scores verge most greatly when both the men's scores and the women's 
// scores tend to even out. Here's the extreme case:
//
//	7 7 7 7 7 2 2 2 2 2
//
// Because the men play 10 matches among themselves, the men's total score must be 
// at least 10, and here we have 10 spread out among the 5 men. Similarly, the 
// total women's score can be no greater than T - U (35 in this example), and that
// too is spread out among the 5 women.
//
// Lo and behold, this distribution solves the problem. The lowest women's score is
// 7 and that's more than 3 times the highest man's score of 2. At least one man 
// and one woman (actually, all of them) have prime scores.
//
// The solution is: 5 couples, with 0 matches with a man beating a woman.
//
// Notice there's not a lot of wiggle room. If one man won one more match, the
// partition would look like this:
//
//	7 7 7 7 6 3 2 2 2 2
// 
// Now the lowest woman's score is only double the highest man's score.
//
// Is this the only solution? Let's look at cases where no men win a match against
// woman, and the scores are evenly distributed as in the solution with 5 couples.
//
// If no man wins a match against a woman, the average man's score is U / N, or:
//
//	                      N - 1
//	Average man's score = -----
//                              2
//
// The average women's score is (T - U) / N or:
//
//	                        3N - 1
//	Average woman's score = ------ 
//	                           2
//
// If N is odd, then the men's scores can be evenly distributed among the N
// men, and so can the women's. Each man scores (N - 1) / 2 and each woman
// scores (3N - 1) / 2. Each women's score is 3 times plus 1 of each men's
// score.
//
// If N is even, then the men's and women's scores cannot be equally 
// distributed among the N men and women. Half the men score N/2 and half 
// score (N-1)/2. Half of the women score 3N/2 and half score 3N/2 - 1.
// The lowest women's score is no longer more than 3 times the highest man's.
//
// So, the only cases that work right are those where N is odd, and all the
// men and women have the same score:
//
//	 N	Men	Women 
//	 -	---	-----
//	 3	  1	   4
//	 5	  2	   7
//	 7	  3	  10
//	 9	  4	  13
//	11	  5	  16
//
// and so forth. The men's scores alternate between odd and even, and the
// women's altenate between even and odd. The only time both men and women
// have prime scores is when the men have the only even prime number of 2.
//
// Let's code up a solution anyway.
//-----------------------------------------------------------------------------	

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

typedef int BOOL;
#define TRUE 1
#define FALSE 0

#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MAX(a,b) ((a) > (b) ? (a) : (b))

// a is an array of 'num' integers, where a[i] >= a[i + 1].
// The 'num' integers are a partition of the sum of the integers in a.
// This function methodically "flattens out" the partition.
// Each call rearranges the elements of the array and normally returns TRUE.
// A FALSE return value means the partition is as flat as possible.

BOOL NextPartition(int a[], int num)
{
	int i, new, accum = 0;

	for (i = num - 1; i > 0; i--)
	{
		accum += a[i];

		if (a[i - 1] > 1 + a[num - 1])
			break;
	}
	
	if (i == 0)
		return FALSE;

	new = a[i - 1] -= 1;
	accum += 1;

	for ( ; i < num; i++)
	{
		a[i] = MIN(new, accum);		
		accum -= MIN(new, accum);
	}
	return TRUE; 
}

// Returns the sum of 'num' integers in array a.

int Sum(int a[], int num)
{
	int i, sum = 0;

	for (i = 0; i < num; i++)
		sum += a[i];

	return sum;

}

BOOL IsPrime(int i)
{
	int j = 2;

	if (i < 2)
		return FALSE;

	while (j * j <= i)
	{
		if (i % j == 0)
			return FALSE;
		j += 1;
	}
	return TRUE;
}

int main(void)
{
	int couples, i;

	// 'couples' is the number of couples. 

	for (couples = 2; couples < 10; couples++)
	{
		// This array holds the scores and is also a partition of the 
		// the total of all the scores. THe first 'couples' elements
		// are the women, followed by the men.

		int scores[2 * couples];

		// Initialize the 'scores' array to be as lopsided as possible.

		for (i = 0; i < 2 * couples; i++)
			scores[i] = 2 * couples - 1 - i;

		printf("Couples = %i\n", couples);

		// This loop cycles through the partitions of 'scores'.

		do
		{
			// Initialize these two variables

			BOOL OneMalePrime = FALSE, OneFemalePrime = FALSE;

			// Check that the women have sufficient scores among themselves.

			if (Sum(scores, couples) < (couples - 1) * couples / 2)
				continue;

			// Check that the men have sufficient scores among themselves

			if (Sum(scores + couples, couples) < (couples - 1) * couples / 2)
				continue;

			// Check that at least one woman and one man have a prime score.

			for (i = 0; i < couples; i++)
			{
				OneFemalePrime |= IsPrime(scores[i]);
				OneMalePrime   |= IsPrime(scores[i + couples]);
			}

			if (!OneFemalePrime || !OneMalePrime)
				continue;

			// Check if the highest scoring woman is more than 3 times the
			//	highest scoring man.
			// If so, we have a winner.

			if (scores[couples - 1] > 3 * scores[couples])
			{
				printf("scores: ");

				for (i = 0; i < 2 * couples; i++)
					printf("%i ", scores[i]);

				printf("\n");

				printf("Men defeat women: %i\n", 
                                       Sum(scores + couples, couples) - (couples - 1) * couples / 2);
			}
		}
		while (NextPartition(scores, 2 * couples));
	}

	return 0;
}