# 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
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.