equationmanuel.c

1995年ACM contest FINAL试题和源码

/*

1995-96 ACM International Collegiate Programming Contest
Southwestern European Regional Contest
ETH Zurich, Switzerland
December 9, 1995


Problem: Equation

Idea:			Frank Moehle, Contest Director
Implementation:	Manuel Bleichenbacher, Head Judge

Source file: equation.c / equation.p
Input file: equation.in
Output file: equation.out

*/

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

int n, n2;
int h2q;
int *v, *g;
int *b1, *b2, *b3, *b4;
int *f;
int *a, *b;


void ReadVector (FILE* fin, int** vector, int size);
void ReadMatrix (FILE* fin, int** matrix, int size);
void AddAt (int i, int j);
void Add_u (int p, int i, int j, int factor);
void Add_f (int p, int i, int j, int factor);


void ReadVector (FILE* fin, int** vector, int size)
{
	int i, dummy;
	
	*vector = (int*) malloc (size * sizeof(int));
	assert (*vector != NULL);
	
	for (i = 0; i < size; i++) {
		dummy = fscanf (fin, "%d", &(*vector)[i]);
		assert (dummy == 1);
	}
}


void ReadMatrix (FILE* fin, int** matrix, int size)
{
	int i, j, dummy;

	*matrix = (int*) malloc (size * size * sizeof(int));
	assert (*matrix != NULL);
	
	for (i = 0; i < size; i++)
		for (j = 0; j < size; j++) {
			dummy = fscanf (fin, "%d", &(*matrix) [i * size + j]);
			assert (dummy == 1);
		}
}


void Add_u (int p, int i, int j, int factor)
{
	int q;	/* number of point */
	
	assert (0 <= i && i <= n);
	assert (0 <= j && j <= n);
	
	if (i == 0)			/* top border */
		b[p] -= h2q * factor * b2[j];
	else if (i == n)	/* bottom border */
		b[p] -= h2q * factor * b1[j];
	else if (j == 0)	/* left border */
		b[p] -= h2q * factor * b3[i];
	else if (j == n)	/* right border */
		b[p] -= h2q * factor * b4[i];
	else  {				/* inner point */
		q = (i - 1) * (n - 1) + j - 1;
		assert (0 <= q && q < n2);
		a[p * n2 + q] += h2q * factor;
	}
}


void Add_f (int p, int i, int j, int factor)
{
	assert (0 <= i && i <= n);
	assert (0 <= j && j <= n);
	
	b[p] += factor * f [i * (n+1) + j];
}

void AddAt (int i, int j)
{
	int p;	/* number of point */
	
	assert (0 < i && i < n);
	assert (0 < j && j < n);
	
	p = (i - 1) * (n - 1) + j - 1;
	assert (0 <= p && p < n2);
	
	Add_u (p, i-1, j-1, v[0]);
	Add_u (p, i-1, j  , v[1]);
	Add_u (p, i-1, j+1, v[2]);
	Add_u (p, i  , j-1, v[3]);
	Add_u (p, i  , j  , v[4]);
	Add_u (p, i  , j+1, v[5]);
	Add_u (p, i+1, j-1, v[6]);
	Add_u (p, i+1, j  , v[7]);
	Add_u (p, i+1, j+1, v[8]);
	
	Add_f (p, i-1, j-1, g[0]);
	Add_f (p, i-1, j  , g[1]);
	Add_f (p, i-1, j+1, g[2]);
	Add_f (p, i  , j-1, g[3]);
	Add_f (p, i  , j  , g[4]);
	Add_f (p, i  , j+1, g[5]);
	Add_f (p, i+1, j-1, g[6]);
	Add_f (p, i+1, j  , g[7]);
	Add_f (p, i+1, j+1, g[8]);
}


int main(int argc, char* argv[])
{
	FILE *fin, *fout;
	int nTests, dummy;
	int i, j;
	
	fin = fopen ("equation.in", "r");
	assert (fin != 0);
	
	fout = fopen ("equation.out", "w");
	assert (fout != 0);
	
	dummy = fscanf (fin, "%d", &nTests);
	assert (dummy == 1);
	
	while (nTests-- > 0) {
		dummy = fscanf (fin, "%d", &n);
		assert (dummy == 1);
		
		n2 = (n-1) * (n-1);
		h2q = n * n;
		
		/* read in */
		ReadMatrix (fin, &v, 3);
		ReadMatrix (fin, &g, 3);
		
		ReadVector (fin, &b1, n+1);
		ReadVector (fin, &b2, n+1);
		ReadVector (fin, &b3, n+1);
		ReadVector (fin, &b4, n+1);
		
		ReadMatrix (fin, &f, n+1);
		
		/* intialize */
		a = (int*) malloc (n2 * n2 * sizeof(int));
		assert (a != NULL);
		b = (int*) malloc (n2 * sizeof(int));
		assert (b != NULL);
		
		for (i = 0; i < n2; i++) {
			b[i] = 0.0;
			for (j = 0; j < n2; j++)
				a[i * n2 + j] = 0.0;
		}
		
		/* calculate */
		for (i = 1; i < n; i++)
			for (j = 1; j < n; j++)
				AddAt (i, j);
		
		/* print out */
		for (i = 0; i < n2; i++)
			for (j = 0; j < n2; j++)
				fprintf (fout, "%d%c", a[i * n2 + j],
							j == n2 - 1 ? '\n' : ' ');

		for (i = 0; i < n2; i++)
			fprintf (fout, "%d%c", b[i],
						i == n2 - 1 ? '\n' : ' ');
		
		/* clean up */
		free(v); free(g); free(f);
		free(b1); free(b2); free(b3); free(b4);
		free(a); free(b);
	}		
	
	fclose (fin);
	fclose (fout);
	
	return 0;
}