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.
There were 20 participants.
#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 1The 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.
#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 10The 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
#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 2The 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.
#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 YCONGRATULATIONSThe 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.
#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 AAAAAAAAAAAAAThe correct output was:
Data set 1: 60 Data set 2: 2520 Data set 3: 12 Data set 4: 17153136 Data set 5: 1
#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 20For 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
This page is maintained by Adam Florence. If there are any questions or corrections, please e-mail me.