ACSU Programming Competition

11 April 1998

Results and Solutions


Problems

The problems are available as a Microsoft Word document. (You may have to shift-click on the link to get it to download properly.)

I think this was the most successful of our four contests to date. All of the problems were answered correctly by at least two contestants. Four contestants got four problems correct.


Results

The top four contestants were:
  1. Mike Smullens, 4 correct, 576 minutes
  2. Winfred Wong, 4 correct, 585 minutes
  3. Erik Dangremond, 4 correct, 595 minutes
  4. Jyhtar Chong, 4 correct, 642 minutes
Problems 1 and 2 had two correct submissions, problem 3 had 15 correct submissions and no incorrect submissions, problem 4 had 15 correct, problem 5 had six, and problem 6 had three.

There were 20 participants.


Solutions

I decided this time to use submissions by actual participants. I occasionally changed the spacing or blank lines in the solutions, but they are otherwise unchanged.

Problem 1 - Going To The Chapel

Here is the solution by Mike Smullens:
#include < stdio.h >
#include < stdlib.h >
#include < math.h >

int grid[26][26];
char path[100];

bool find (int a, int n, int p)
{
	int i;
	path[p]=a+'A';
	path[p+1]=0;
	bool j=false, f=false, t=false;

	if (a==2)
	{
		for (i=0; i < p; i++)
		{
			j|=(path[i]=='J');
			f|=(path[i]=='F');
			t|=(path[i]=='T');
		}
		if (j&&f&&t) return true;
	}

	for (i=0; i<26; i++)
		if (grid[a][i] < n&&grid[a][i]>0)
			if (find(i,n-grid[a][i],p+1)) return true;

	return false;
}

void main ()
{
	int sets, n, i, j, k, d;
	char a, b;
	char inp[80];

	scanf("%d", &sets);
	for (i=0; i < sets; i++)
	{
		scanf("%d", &n);
		for (j=0; j<26; j++)
			for (k=0; k<26; k++)
				grid[j][k]=0;

		gets(inp);
		for (j=0; j < n; j++)
		{
			gets(inp);
			a=inp[0]-'A';
			b=inp[2]-'A';
			d=atoi(&inp[4]);
			grid[a][b]=d;
		}

		for (j=0; j<10000; j++)
			if (find(0,j, 0))
			{
				printf("Data set %d: The shortest path is %s and has length %d.",
					i+1, path, j-1);
				break;
			}
	}
}
The test input was:
4
12
A B 2
A D 3
B D 1
D B 1
B T 3
D T 4
T F 5
F J 7
J C 6
F C 1
T J 5
C F 3
6
A B 1
B C 1
B F 1
F T 1
T J 1
J B 1
40
Y J 1
J K 1
K L 1
L M 1
N C 1
C B 1
B I 1
I X 1
W H 1
H A 1
A D 1
D O 1
P E 1
E F 1
F G 1
G V 1
U T 1
T S 1
S R 1
R Q 1
U V 1
V W 1
W X 1
X Y 1
J I 1
I H 1
H G 1
G T 1
S F 1
F A 1
A B 1
B K 1
L C 1
C D 1
D E 1
E R 1
Q P 1
Q O 1
O N 1
N M 1
18
A B 1
A J 1
A E 1
A T 1
A D 1
A F 1
D F 1
F B 2
B J 3
J E 4
E T 5
T D 6
F C 1
D C 1
T C 1
E C 1
J C 1
B C 1
The correct output was:
Data set 1: The shortest path is ABTJCFC and has length 20.
Data set 2: The shortest path is ABFTJBC and has length 6.
Data set 3: The shortest path is ABIHGTSFABIXYJKLC and has length 16.
Data set 4: The shortest path is ATDFBJC and has length 14.

Problem 2 - Photographs

Here is the solution by Winfred Wong:
#include < iostream.h >

void main(void) {

	int numDataSet;
	int numGuest;
	int numCond;

	int taller;
	int shorter;

	cin >> numDataSet;

	for (int i=0; i < numDataSet;i++) {

		cin >> numGuest;
		cin >> numCond;

		int* guest = new int[numGuest];
		int flag;

		int** info = new int*[numGuest];
		for (int y=0; y < numGuest;y++) {
			info[y] = new int[numGuest];
		}

		for (int n=0; n < numGuest;n++) {
			guest[n] = 0;
			for (int p=0; p < numGuest;p++) {
				info[n][p]=0;
			}
		}

		flag = 0;

		cout << "Data set " << i+1 << ": " << endl;


		for (int j=0; j < numCond;j++) {

			int height;

			cin >> taller;
			cin >> shorter;

			taller--;
			shorter--;

			height = guest[shorter];

			info[shorter][taller] = 1;

			if ((guest[shorter]!=0) && (guest[shorter]>guest[taller])) {

				cout << "Data inconsistent." << endl;
				flag = 1;
				break;

			}
			else {

				if (guest[taller] < (guest[shorter] + 1)) {

					guest[taller] = guest[shorter] + 1;

					// update info

					for (int q=0; q < numGuest;q++) {
						for (int c=0; c < numGuest;c++) {
							for (int s=0; s < numGuest;s++) {
								if (info[c][s] == 1) {
									if (guest[s] < guest[c]+1) {
										guest[s] = guest[c]+1;
									}
								}
							}
						}
					}
				}
			}
		}

		// check duplicate rank
		if (flag==0) {
			
			for (int k=0; k < numGuest-1; k++) {

				for (int m=k+1; m < numGuest; m++) {

					if (guest[k] == guest[m]) {

						flag = 1;
						break;

					}
				}
			}

			if (flag==1) {
				cout << "Not enough Information.\n";
			}

		}

		// output the result

		if (flag == 0) {

			for (int k=0; k < numGuest;k++) {

				for (int m=0; m < numGuest; m++) {

					if (guest[m] == k) {

						cout << m+1 << " ";
					}

				}

			}
		}

		cout << endl;

	}

}
The test input was:
4
5 4
1 2
2 3
3 4
4 5
3 3
1 2
2 3
3 1
50 2
19 24
15 3
10 12
1 2
2 3
1 3
3 4
4 5
5 6
6 8
7 8
1 10
6 7
8 9
9 10
The correct output was:
Data set 1: 5 4 3 2 1 
Data set 2: Data inconsistent.
Data set 3: Not enough Information.
Data set 4: 10 9 8 7 6 5 4 3 2 1 

Problem 3 - Let Them Eat Cake

Here is the solution by Erik Dangremond:
#include < stdio.h >
#include < math.h >
#include < stdlib.h >

void main() {
	int i, j, k;

	int numsets, nump, firstp;
	int cake[100];
	int total;

	scanf("%d", &numsets);
	for (i=1; i<=numsets; i++) {
		scanf("%d %d", &nump, &firstp);

		cake[1] = firstp;
		for (j=2; j<=nump; j++) {
			if (j%7==0)
				cake[j] = j%11+1;
			else if (
				sqrt((float)j) - (float)(int)sqrt((float)j) < 0.00001) {
				cake[j] = (int)floor(sqrt((float)j)+.0001);
				//printf("perfect: %d\n", j);
			}
			else if (j%2==0)
				cake[j]=cake[j-1]+1;
			else if (cake[j-1]==0)
				cake[j]=cake[1];
			else
				cake[j]=cake[j-1]-1;
		}
		total=0;
		for (j=1; j<=nump; j++)
			total += cake[j];
		printf("Data set %d: %d units of cake are eaten.\n", i, total);
	}
}
The test input was:
5
10 1
5 10
1000 1
20 3
99 2
The correct output is:
Data set 1: 33 units of cake are eaten.
Data set 2: 34 units of cake are eaten.
Data set 3: 29 units of cake are eaten.
Data set 4: 74 units of cake are eaten.
Data set 5: 563 units of cake are eaten.

Problem 4 - Congratulations

Here is the solution by Chin-Yu Hsu:
#include < stdio.h >
#include < iostream.h >
#include < string.h >

int  plen[2000];
char pass[2000][21];

int	 msglen;
char message[61];
char final[61];
int passnum;

main()
	{
	int loops;
	int curloop;
	int i,j;
	int passtry;

	cin >> passnum >> loops;

	for( curloop = 0; curloop < passnum; curloop++ )
		{
		cin >> pass[curloop];
		plen[curloop] = strlen(pass[curloop]);
		}

	for( curloop = 0; curloop < loops; curloop++ )
		{
		cin >> message;

		msglen = strlen(message);

		passtry = 0;

		int pp;

		do
			{
			i = 0;
			for(j=0; j < msglen;j++)
				{
				pp= (int)((message[j]-'A'+1)+(pass[passtry][i]-'A'+1));
				if(pp>26) pp -=26;
				pp--;
				final[j] = 'A' + pp;
				i=((i+1)%plen[passtry]);
				}
	
			final[msglen]='\0';
			for(i=0; i < msglen;i++)
				if( final[i]=='C' )
					{
					if( strncmp( final+i, "CONGRATULATIONS",15)==0 )
						{
						cout << "Message " << curloop+1 << ": Password " << pass[passtry]
						  << " worked. Message is " << final << ".\r\n";
						}
					}


			passtry++;
			} while(passtry < passnum);

		}

	return 0;
	}
The test input was:
6 5
ANT
BABYLON
CODE
DAY
ELEPHANT
Z
ANLHFLFSKYUWZZQZBBA
XCIQJZFAGOOSGME
ZZNIBWHXLYCMXEQGXEEJKDJZMSAR
YCONGRATULATIONS
The correct output was:
Message 1: Password BABYLON worked. Message is CONGRATULATIONSADAM.
Message 2: Password ELEPHANT worked. Message is CONGRATULATIONS.
Message 3: Password CODE worked. Message is CORNELLCONGRATULATIONSNEPHEW.
Message 4: Password Z worked. Message is YCONGRATULATIONS.

Problem 5 - Mischievous Children

Here is the solution by Jyhtar Chong:
#include < stdlib.h >
#include < stdio.h >
#include < string.h >
#include < iostream.h >
unsigned long int f(char *s)
{
	unsigned long int l=strlen(s);
	unsigned long int i,j,k, divi=1;
	unsigned long int m[100];
	unsigned long int ans=1;
	for (i=0;i<100;i++){
		m[i]=0;
	}
	for (i=0;i<(l-1);i++){
		for (j=i+1; j < l;j++){
			if (s[i] == s[j]) {
				if (m[i] == 0) {
					m[i]=2;
				} else if (m[i]>0) m[i]++;
			}
		}
	}
	for (i=1;i<=l;i++){
		ans=ans*i;
		for(k=0;k<100;k++){
			for (j=0;j<100;j++){
				if (m[j] >0){
					if (ans % m[j] == 0){
						ans = ans / m[j];
						m[j]=0;
					}
				}
			}
		}
	}
	for (j=0;j<100;j++){
		if (m[j] >0){
				ans = ans / m[j];
				m[j]=0;
		}
	}
	
	return (ans);
}

void main()
{

	unsigned long int i,n;
	char str[100];
	unsigned long int ans[100];
	scanf("%d",&n);
	for (i=0; i < n;i++){
		scanf("%s",str);
		ans[i]=f(str);
	}
	for (i=0; i < n;i++){
		cout << "Data set"<< i+1<<": " << ans[i] << endl;
	}

}
The test input was:
5
HAPPY
WEDDING
ADAM
AAAAAABBBBBBCCCCCC
AAAAAAAAAAAAA
The correct output was:
Data set 1: 60
Data set 2: 2520
Data set 3: 12
Data set 4: 17153136
Data set 5: 1

Problem 6 - Shall We Dance?

Here is the solution by Chin-Yu Hsu:
#include < stdio.h >
#include < iostream.h >
#include < string.h >

int grid[20][20];
		int count ,down;

void PrintResult();

main()

	{
	int loops;
	int curloop;

	cin >> loops;
	for( curloop = 0; curloop < loops; curloop++ )
		{

		cout.width(0);
		int i, j;
		for( i =0 ;i<20;i++ )
			for( j =0; j<20;j++ )
				grid[i][j] = 0;

		cin >> count;

		if (count % 2 == 0) down = count-1;
		else				down = count;

		for( j=0; j < down;j++ )
			{
			for( i = 0; i < count; i++ )
				{
				if( i==0 && j==0 )
					{
					grid[i][j] = down;
					if( down==1 && count!=down ) grid[i][j]++;
					grid[grid[i][j]-1][j] = i+1;
					}
				else if( grid[i][j] == 0 )
					{
					if( i == j )
						{
						grid[i][j] = grid[i-1][j-1];
						}
					else if( i==0 )
						{
						grid[i][j] = grid[i][j-1]+1;
						if( grid[i][j] > count )
							{
							if( i==0 && down!=count ) grid[i][j] = 2;
							else  	   grid[i][j] = 1;
							}
						}
					else
						{
						grid[i][j] = grid[i-1][j]-1;
						if( grid[i][j] < 1 ) grid[i][j]+=count;
						}

					
					//if( i == j ) grid[i][j] = grid[i-1][j-1];
					if( (grid[i][j]==i+1 && down!=count) ||
					    (grid[grid[i][j]-1][j]!=0 && grid[i][j]!=i+1) )
						{
						bool work;
						grid[i][j]=count+1;
						do
							{
							work = true;
							grid[i][j]--;
							if( grid[i][j] < 1) grid[i][j]=count;
							
							if( grid[grid[i][j]-1][j]!=0 ) work = false;
							else
								{
								int x;
								for(x=0; x < j;x++)
									if( grid[i][x]==grid[i][j] )
										{
										work = false;
										break;
										}
								}
							}
						while( !work );
						}
					grid[grid[i][j]-1][j] = i+1;
					}

				}
			}

		cout << "Data set " << curloop+1 <<": \r\n";
		PrintResult();

		}

	return 0;
	}

void PrintResult()
	{
	int i, j;
	for( j =0; j < down;j++ )
		{
		for( i =0 ; i < count;i++ )
			{
			cout.width(3);
			cout << grid[i][j];
			}
		cout << "\r\n";
		}
	cout << "\r\n";
	cout.flush();
	}
The test input was:
10
2
4
5
6
7
8
9
10
15
20
For this problem, any dance card that satisfied the criteria was correct. The output generated by this code is:
Data set 1: 
  2  1

Data set 2: 
  3  4  1  2
  4  3  2  1
  2  1  4  3

Data set 3: 
  5  4  3  2  1
  1  5  4  3  2
  2  1  5  4  3
  3  2  1  5  4
  4  3  2  1  5

Data set 4: 
  5  4  6  2  1  3
  6  5  4  3  2  1
  2  1  5  6  3  4
  3  6  1  5  4  2
  4  3  2  1  6  5

Data set 5: 
  7  6  5  4  3  2  1
  1  7  6  5  4  3  2
  2  1  7  6  5  4  3
  3  2  1  7  6  5  4
  4  3  2  1  7  6  5
  5  4  3  2  1  7  6
  6  5  4  3  2  1  7

Data set 6: 
  7  6  5  8  3  2  1  4
  8  7  6  5  4  3  2  1
  2  1  7  6  8  4  3  5
  3  8  1  7  6  5  4  2
  4  3  2  1  7  8  5  6
  5  4  8  2  1  7  6  3
  6  5  4  3  2  1  8  7

Data set 7: 
  9  8  7  6  5  4  3  2  1
  1  9  8  7  6  5  4  3  2
  2  1  9  8  7  6  5  4  3
  3  2  1  9  8  7  6  5  4
  4  3  2  1  9  8  7  6  5
  5  4  3  2  1  9  8  7  6
  6  5  4  3  2  1  9  8  7
  7  6  5  4  3  2  1  9  8
  8  7  6  5  4  3  2  1  9

Data set 8: 
  9  8  7  6 10  4  3  2  1  5
 10  9  8  7  6  5  4  3  2  1
  2  1  9  8  7 10  5  4  3  6
  3 10  1  9  8  7  6  5  4  2
  4  3  2  1  9  8 10  6  5  7
  5  4 10  2  1  9  8  7  6  3
  6  5  4  3  2  1  9 10  7  8
  7  6  5 10  3  2  1  9  8  4
  8  7  6  5  4  3  2  1 10  9

Data set 9: 
 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1
  1 15 14 13 12 11 10  9  8  7  6  5  4  3  2
  2  1 15 14 13 12 11 10  9  8  7  6  5  4  3
  3  2  1 15 14 13 12 11 10  9  8  7  6  5  4
  4  3  2  1 15 14 13 12 11 10  9  8  7  6  5
  5  4  3  2  1 15 14 13 12 11 10  9  8  7  6
  6  5  4  3  2  1 15 14 13 12 11 10  9  8  7
  7  6  5  4  3  2  1 15 14 13 12 11 10  9  8
  8  7  6  5  4  3  2  1 15 14 13 12 11 10  9
  9  8  7  6  5  4  3  2  1 15 14 13 12 11 10
 10  9  8  7  6  5  4  3  2  1 15 14 13 12 11
 11 10  9  8  7  6  5  4  3  2  1 15 14 13 12
 12 11 10  9  8  7  6  5  4  3  2  1 15 14 13
 13 12 11 10  9  8  7  6  5  4  3  2  1 15 14
 14 13 12 11 10  9  8  7  6  5  4  3  2  1 15

Data set 10: 
 19 18 17 16 15 14 13 12 11 20  9  8  7  6  5  4  3  2  1 10
 20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1
  2  1 19 18 17 16 15 14 13 12 20 10  9  8  7  6  5  4  3 11
  3 20  1 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  2
  4  3  2  1 19 18 17 16 15 14 13 20 11 10  9  8  7  6  5 12
  5  4 20  2  1 19 18 17 16 15 14 13 12 11 10  9  8  7  6  3
  6  5  4  3  2  1 19 18 17 16 15 14 20 12 11 10  9  8  7 13
  7  6  5 20  3  2  1 19 18 17 16 15 14 13 12 11 10  9  8  4
  8  7  6  5  4  3  2  1 19 18 17 16 15 20 13 12 11 10  9 14
  9  8  7  6 20  4  3  2  1 19 18 17 16 15 14 13 12 11 10  5
 10  9  8  7  6  5  4  3  2  1 19 18 17 16 20 14 13 12 11 15
 11 10  9  8  7 20  5  4  3  2  1 19 18 17 16 15 14 13 12  6
 12 11 10  9  8  7  6  5  4  3  2  1 19 18 17 20 15 14 13 16
 13 12 11 10  9  8 20  6  5  4  3  2  1 19 18 17 16 15 14  7
 14 13 12 11 10  9  8  7  6  5  4  3  2  1 19 18 20 16 15 17
 15 14 13 12 11 10  9 20  7  6  5  4  3  2  1 19 18 17 16  8
 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1 19 20 17 18
 17 16 15 14 13 12 11 10 20  8  7  6  5  4  3  2  1 19 18  9
 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1 20 19

Last updated 28 September 1999.

This page is maintained by Adam Florence. If there are any questions or corrections, please e-mail me.