rsalz@uunet.uu.net (Rich Salz) (02/08/89)
Submitted-by: jim nelson <nelson@uncecs.edu>
Posting-number: Volume 17, Issue 86
Archive-name: contest-prog/part03
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of archive 3 (of 3)."
# Contents: contestrules gr prob18.c prob18.txt score.c
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'contestrules' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'contestrules'\"
else
echo shar: Extracting \"'contestrules'\" \(3260 characters\)
sed "s/^X//" >'contestrules' <<'END_OF_FILE'
X
XRules:
X
X1) The winning team in each category is the one which solves the most
Xproblems in its appropriate category. Period!
X
XHOWEVER:
X
X2) In the event of TIES, the penalty-point method will be used. Teams
Xwith fewer penalty points rank ahead of teams with more penalty points,
Xfor the purpose of breaking ties only.
X
XPenalty points are assessed as follows:
X
X 10 points for each incorrect judged run
X
X 1 point for every minute a problem (in your category) remains
X unsolved by your team
X
X
X3) You may make, without penalty, any number of trial runs of your
Xprogram against your own input data, but a judged run is made against
Xthe judges' input data, which you will NEVER (until after the end of
Xthe contest) be allowed to see.
X
X4) The judging program will compile your program and run it against the
Xjudges' input data, in a protected account. You will be notified of
Xthe correctness or incorrectness of your output by a program which
Xcompares byte-by-byte your output with the correct answer ("diff").
XThat's all. You must read standard-input, and write standard-output.
XYou may not open any additional file-descriptors or FILE *'s.
X
X5) Programs must be in C, Pascal, or Fortran. They must be a single
Xmonolithic file (you may #include). We cannot handle makefiles, awk
Xscripts, compile-line options, etc. Just plain & simple quick & dirty
Xcoding. The judges will not look at the code, only the output.
X
X6) Your submitted source code must be named
X<something><problem#>.[c|f|p|pas]
XIf your filename ends in .pas, the pascal compiler will be invoked.
XIf your filename ends in .p , the pc compiler will be invoked.
XIf your filename ends in .f , the fortran compiler will be invoked.
XIf your filename ends in .c , the cc compiler will be invoked.
XThe first digit-string will be deemed to be the problem number you
Xare submitting.
X
XTo submit a program for judging, use the judge command.
XExamples:
X$ judge prob1.c
X$ judge prog3.f
X$ judge contestprob13.pas
X$ judge why_did_i_ever_get_myself_into_this_12.p
XYou will be notified by mail of the result of your judged run. (Or
Xyou could periodically run "score").
X
X7) If your judged run is correct, the cutoff time for penalty points
Xfor that problem will be the time you SUBMITTED it, NOT the time it
Xwas judged; so don't be overly concerned that judging may take a few
Xminutes. Go work on another problem while waiting.
X
X8) As soon as the contest begins, you may find the statements of the
Xproblems in the /tmp directory. They will be named /tmp/probxx.txt,
Xwhere xx is the number of the problem. Beginners will be interested
Xin prob1.txt up through prob6.txt. Intermediates will be interested
Xin prob7.txt up through prob12.txt. Advanced entrants should
Xhave already figured out that they want prob13.txt thru prob18.txt.
X(It will do you no good to solve a problem in a category not
Xappropriate to your class; the scoreboard program will ignore
Xit, and you will have wasted your time.)
X
X9) Only one contestant per team may be logged in at any one time.
X
X10) The contest ends exactly four hours after it begins. Problems
Xsubmitted for judging after the cutoff time will not be judged.
XHowever, juding of problems submitted just before the end may
Xextend until all have been judged.
END_OF_FILE
if test 3260 -ne `wc -c <'contestrules'`; then
echo shar: \"'contestrules'\" unpacked with wrong size!
fi
# end of 'contestrules'
fi
if test -f 'gr' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'gr'\"
else
echo shar: Extracting \"'gr'\" \(3885 characters\)
sed "s/^X//" >'gr' <<'END_OF_FILE'
X#! /bin/sh
Xcd $HOME
Xif test -f lock
Xthen
X echo another judge has me busy, try again momentarily
X exit
Xfi
Xfailure=""
Xtouch lock
Xcat $MAIL >>mal
Xcp /dev/null $MAIL
Xfn=`grep Judge: mal |head -1`
Xcase $fn in
X "")rm lock;exit;;
Xesac
Xfun=` echo $fn | sed 's/Judge/judge/' `
Xecho $fn
Xecho $fun
Xsed "s=$fn=$fun=" mal >/tmp/pqr$$
Xcp /tmp/pqr$$ mal
Xrm -f /tmp/pqr$$
X
X
Xecho fn = $fn
Xfl=`echo $fn|cut -f2 -d' '`
Xecho fl = $fl
Xseconds=`echo $fn|cut -f3 -d' '`
Xecho seconds = $seconds
Xendtime=`cat endtime`
Xecho endtime = $endtime
X
Xda=`echo $fn|cut -f2 -d';'`
Xecho da = $da
X
Xcase $fl in
X "")rm -f lock;exit;;
Xesac
X
Xt=`echo $fl|cut -f3 -d'/'`
Xecho t = $t
Xcase $t in
X team0) t=judges;;
Xesac
Xecho t = $t
Xp=`echo $fl|cut -f4 -d'/'`
Xecho $seconds $endtime
Xif expr $seconds '>' $endtime
Xthen
X echo too late
X echo $fn >/tmp/dumb$$
X echo "submitted too late">>/tmp/dumb$$
X mail $t < /tmp/dumb$$
X rm /tmp/dumb$$
X rm lock
X exit
Xelse
X echo not too late
Xfi
X
Xsrc=`shorten $t.$p`
Xecho src=$src
Xecho p = $p
Xif test -f $src.right
Xthen
X echo They seem to have already completed that problem...
X echo Do you want to proceed?
X read zork
X case $zork in
X y) ;;
X *) rm -f lock;exit;;
X esac
Xfi
X
X
X
Xs=$fl
Xecho s = $s
Xext=`basename $s`
Xecho ext = $ext
Xcase $ext in
X *.p)c=pc;dot=p;;
X *.pas)c=pascal;dot=p;;
X *.c)c=cc;dot=c;;
X *.f)c=fortran;dot=f;;
X *) echo invalid extension;rm -f lock;exit;;
Xesac
X
Xif test -f $s
Xthen
X echo cp $s $src.$$.$dot
X cp $s $src.$$.$dot
Xelse
X echo $s not found
X echo $s >/tmp/dumb$$
X echo "was not found in your directory">>/tmp/dumb$$
X mail $t </tmp/dumb$$
X rm -f lock
X echo bye
X rm -f /tmp/dumb$$
X exit
Xfi
X#q=`echo $p|cut -f2 -db`
X#q=`echo $q|cut -f1 -d.`
Xq=`digits $p`
Xqq=`digits $t`
Xcase $q in
X -)q=99;;
Xesac
Xcase $qq in
X -)qq=99;;
Xesac
Xecho $qq $q
Xecho $src.$$.$dot
Xecho the compiler is $c
Xif $c -o subdir/${src}.$$.e $src.$$.$dot
Xthen
X echo compiled ok ... about to run it
Xelse
X echo compilation failed
X failure=1
Xfi
Xcase $failure in
X "")
X echo about to run $src.$$.e
X cp prob$q.in subdir/prob$q.in$$
X echo cp prob$q.in subdir/prob$q.in$$
X #cd subdir
X if test -f prob$q.in
X then
X echo "chexec8 <subdir/prob$q.in$$ >out subdir/$src.$$.e"
X rm -f out
X chexec8 <subdir/prob$q.in$$ >out subdir/$src.$$.e
X chmod og-rwx out
X
X else
X echo prob$q.in$$ not found in gr ... you dummy!
X exit
X fi
X #cd ..
X echo through running
X diff out prob$q.ans
X rm -f subdir/*
X if compare out prob$q.ans
X then
X echo "1" $qq $q $seconds>>scoreboard
X echo yes their output is correct
X mv out keep/$src.$$.m
X rm lock
X echo \
X "CONGRATS! $t successfully did prob$q at `date`">\
X $src.right
X mail $t < $src.right
X echo "submitted: $seconds">$src.at
X echo "$t completed problem $q at `date`">$src.msg
X list=""
X for i in `cat listofteams` ;
X do
X case $i in
X $t) ;;
X *) list="$list $i"
X ;;
X esac
X done
X mail $list < $src.msg
X exit
X else
X echo "0" $qq $q $seconds >>scoreboard
X echo not correct
X mv out keep/$src.$$.m
X rm lock
X echo "do you wish to mail them an explanatory note? "
X read zork
X case $zork in
X y)
X echo "mail $t"
X mail -s "$p" $t
X ;;
X *) echo "your $p not correct">failure$$
X mail -s "$p" $t<failure$$
X rm -f failure$$
X ;;
X esac
X fi
X ;;
X 1)
X echo "0" $qq $q $seconds >>scoreboard
X echo not correct
X mv out keep/$src.$$.m
X rm lock
X echo "do you wish to mail them an explanatory note? "
X read zork
X case $zork in
X y)
X echo "mail $t"
X mail -s "$p" $t
X ;;
X *) echo "your $p not correct">failure$$
X mail -s "$p" $t<failure$$
X rm -f failure$$
X ;;
X esac
Xesac
END_OF_FILE
if test 3885 -ne `wc -c <'gr'`; then
echo shar: \"'gr'\" unpacked with wrong size!
fi
chmod +x 'gr'
# end of 'gr'
fi
if test -f 'prob18.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'prob18.c'\"
else
echo shar: Extracting \"'prob18.c'\" \(5065 characters\)
sed "s/^X//" >'prob18.c' <<'END_OF_FILE'
X/*
XProblem 18:Expanding square codes
X
X One method of encoding messages is known as the "expanding square
Xcode." This method encodes messages by placing the characters of the
Xmessage to be encoded in an odd order(1,3,5,7,9) square matrix row by
Xrow, and then retrieves them (decoding) in a clockwise expanding
Xsquare spiral from the center of the matrix. If the message is not
Xexactly the right length to fill the matrix, the rest of the matrix
Xis filled with asterisk characters (*).
X
X For example, the two square matrices below show the order in which
Xthe characters are placed in a matrix(order 5), and the order in which
Xthey are to be retrieved. Notice that the order of retrieval begins
Xat the center, then proceeds to the right, and then spirals
Xclockwise.
X
X order in order out
X
X 1 2 3 4 5 21 22 23 24 25
X 6 7 8 9 10 20 7 8 9 10
X 11 12 13 14 15 19 6 1 2 11
X 16 17 18 19 20 18 5 4 3 12
X 21 22 23 24 25 17 16 15 14 13
X
X Examples:
X
X encode:
X message in: "This is a test message!"
X
X message out: "stssees a a**!egmtiThis "
X
X decode:
X message in: "anreh is io *.enotshAnd t"
X
X message out: "And this is another one."
X
X Your program should be able to encode and to decode messages by
Xthis method. The input will consist of pairs of lines; the first
Xline in each pair will contain either the word encode or the word
Xdecode in lower case characters. The second line in each pair will
Xconsist of a message to be either encoded or decoded by the above
Xmethod, containing a maximum of 80 characters. There will be no
Xquotation marks (") surrounding the messages, and you should not
Xoutput your messages with "'s.
X
X From the length of the message, you should determine the minimum
Xodd order required for the matrix, and perform the specified operation.
XThe output for each operation will consist of one blank line, the
Xgiven message, and the resultant message. Each message should be
Xon a separate line. A decoded message may not contain the asterisk
Xcharacters used to fill the matrix in the encoding process. You
Xmay assume that no actual message contains an asterisk.
X
X Your program should continue reading input lines and performing
Xoperations until something other than the words encode or
Xdecode is encountered.
X
XHere is an actual run; the input file consisted of exactly four lines.
XThe output file consists of exactly six lines; lines 1 and 4 are
Xblank lines.
XThis was the input file (the next four lines):
Xencode
Xnow is the time for all
Xdecode
Ximroft thee **lla snow i
XHere was the output file (the next six lines, NOTICE the blank lines!):
X
Xnow is the time for all
Ximroft thee **lla snow i
X
Ximroft thee **lla snow i
Xnow is the time for all
X*/
X#include <stdio.h>
X#include <kindex.c>
X#define newline '\n'
X#define null '\0'
Xint E[]={0,1};
Xint S[]={1,0};
Xint W[]={0,-1};
Xint N[]={-1,0};
Xint *dir;
Xint x,y;
Xint size;
X#define SZ 55
Xint a[SZ+3][SZ+3];
X
Xmain(){
X int len,d,n,i,k,j,jj;
X char line[256];
X
X while( gets(line)==line){
X if(kindex(line,"encode")==0)goto encode;
X if(kindex(line,"decode")==0)goto decode;
X exit(0);
X encode:
X putchar(newline);
X gets(line);
X puts(line);
X for(i=0;i<=90;i++)if(line[i]==newline ||line[i]==null)break;
X line[i]=null;
X len=i;
X for(size=1;;size++,size++)if(size*size>=len)break;
X for(i=len;i<size*size;i++)line[i]='*';line[i]=null;
Xfor(i=1;i<=SZ;i++)for(k=1;k<=SZ;k++){a[i][k]= 0;}
Xj=0;
Xfor(i=1;i<=size;i++)for(k=1;k<=size;k++){a[i][k]=line[j++];}
X/*
Xfor(i=1;i<=size;i++)
X{
X for(k=1;k<=size;k++){
X printf("%c",a[i][k]);
X }
X putchar(newline);}
X */
X x=y=(size+1)/2;
X n=size*size;
X dir=E;
X printf("%c",a[x][y]);
X for(k=1;k<=size;k++){
X for(j=1;j<=k;j++){
X d=godir();if(d>0)printf("%c",d); if(d<0)goto out;
X }
X nextdir();
X for(j=1;j<=k;j++){
X d=godir();if(d>0)printf("%c",d); if(d<0)goto out;
X }
X nextdir();
X }
X out:putchar(newline);
X goto getnextline;
X
X decode:
X /*for(i=0;i<=SZ;i++)for(j=0;j<=SZ;j++)a[i][j]=1;*/
X putchar(newline);
X gets(line);
X for(i=0;i<=90;i++)if(line[i]==newline ||line[i]==null)break;
X line[i]=null;
X puts(line);
X len=i;
X for(size=1;;size++,size++)if(size*size>=len)break;
X for(i=len;i<size*size;i++)line[i]=' ';line[i]=null;
X x=y=(size+1)/2;
X n=size*size;
X dir=E;
X jj=0;
X a[x][y]=line[jj++];
X for(k=1;k<=size;k++){
X for(j=1;j<=k;j++){
X d=godir();a[x][y]=line[jj++]; if(jj>n)goto out1;
X/* printf("x,y= %d %d\n",x,y);*/
X }
X nextdir();
X for(j=1;j<=k;j++){
X d=godir();a[x][y]=line[jj++]; if(jj>n)goto out1;
X/* printf("x,y= %d %d\n",x,y);*/
X }
X nextdir();
X }
X out1:
X jj=0;
X for(i=1;i<=size;i++)for(j=1;j<=size;j++)line[jj++]=a[i][j];
X for(i=0;i<100;i++)if(line[i]=='*')line[i]=null;
X puts(line);
Xgetnextline: ;
X}
X}
Xgodir()
X{
X x= x+ dir[0];
X y= y+ dir[1];
X if(y<1 || y>size)return -1;
X if(x<1 || x>size)return -1;
X return a[x][y];
X
X}
Xnextdir()
X{
X if(dir==E){dir=S;return;}
X if(dir==S){dir=W;return;}
X if(dir==W){dir=N;return;}
X if(dir==N){dir=E;return;}
X
X}
END_OF_FILE
if test 5065 -ne `wc -c <'prob18.c'`; then
echo shar: \"'prob18.c'\" unpacked with wrong size!
fi
# end of 'prob18.c'
fi
if test -f 'prob18.txt' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'prob18.txt'\"
else
echo shar: Extracting \"'prob18.txt'\" \(3113 characters\)
sed "s/^X//" >'prob18.txt' <<'END_OF_FILE'
XProblem 18: Expanding square codes.
X
X One method of encoding messages is known as the "expanding square
Xcode." This method encodes messages by placing the characters of the
Xmessage to be encoded in an odd order(1,3,5,7,9) square matrix row by
Xrow, and then retrieves them (decoding) in a clockwise expanding
Xsquare spiral from the center of the matrix. If the message is not
Xexactly the right length to fill the matrix, the rest of the matrix
Xis filled with asterisk characters (*).
X
X For example, the two square matrices below show the order in which
Xthe characters are placed in a matrix(order 5), and the order in which
Xthey are to be retrieved. Notice that the order of retrieval begins
Xat the center, then proceeds to the right, and then spirals
Xclockwise.
X
X order in order out
X
X 1 2 3 4 5 21 22 23 24 25
X 6 7 8 9 10 20 7 8 9 10
X 11 12 13 14 15 19 6 1 2 11
X 16 17 18 19 20 18 5 4 3 12
X 21 22 23 24 25 17 16 15 14 13
X
X Examples:
X
X encode:
X message in: "This is a test message!"
X
X message out: "stssees a a**!egmtiThis "
X
X decode:
X message in: "anreh is io *.enotshAnd t"
X
X message out: "And this is another one."
X
X Your program should be able to encode and to decode messages by
Xthis method. The input will consist of pairs of lines; the first
Xline in each pair will contain either the word encode or the word
Xdecode in lower case characters. The second line in each pair will
Xconsist of a message to be either encoded or decoded by the above
Xmethod, containing a maximum of 80 characters. There will be no
Xquotation marks (") surrounding the messages, and you should not
Xoutput your messages with "'s.
X
X From the length of the message, you should determine the minimum
Xodd order required for the matrix, and perform the specified operation.
XThe output for each operation will consist of one blank line, the
Xgiven message, and the resultant message. Each message should be
Xon a separate line. A decoded message may not contain the asterisk
Xcharacters used to fill the matrix in the encoding process. You
Xmay assume that no actual message contains an asterisk.
X
X You may assume that no input line will be longer than 80 characters,
Xso that a matrix larger than 9x9 will never be required.
X
X Your program should continue reading input lines and performing
Xoperations until something other than the words encode or
Xdecode is encountered.
X
X By the way, this is a TERRIBLE code; try it on a "quick brown fox"
Xand see if you can't guess it.
X
XHere is an actual run; the input file consisted of exactly four lines.
XThe output file consists of exactly six lines; lines 1 and 4 are
Xblank lines.
XThis was the input file (the next four lines):
Xencode
Xnow is the time for all
Xdecode
Ximroft thee **lla snow i
XHere was the output file (the next six lines, NOTICE the blank lines!):
X
Xnow is the time for all
Ximroft thee **lla snow i
X
Ximroft thee **lla snow i
Xnow is the time for all
END_OF_FILE
if test 3113 -ne `wc -c <'prob18.txt'`; then
echo shar: \"'prob18.txt'\" unpacked with wrong size!
fi
# end of 'prob18.txt'
fi
if test -f 'score.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'score.c'\"
else
echo shar: Extracting \"'score.c'\" \(2852 characters\)
sed "s/^X//" >'score.c' <<'END_OF_FILE'
X#define CURVERS 21
X#define HOURS 4
X#include <stdio.h>
X#include <sys/types.h>
X#ifdef sequent
X#include <sys/time.h>
X#else
X#include <time.h>
X#endif
Xint prob,team;
Xchar *let[4] = {
X " ","beg","int","adv"};
Xint category[31];
X
Xmain()
X{
X char *malloc();
X char *end;
X FILE *fopen(), *fp ;
X int sus,finish;
X long version,starttime;
X char *teamnames[31], *strcpy();
X time_t ct,ct1;
X long time();
X int solvedat[31][19];
X int penal[31],nfail[31],nworked[31];
X int i,k;
X long endcontest;
X char temp[81];
X
X for(team=1;team<=30;team++){
X penal[team]=0;
X nfail[team]=0;
X nworked[team]=0;
X teamnames[team]=(char *)0;
X for(prob=1;prob<=18;prob++)solvedat[team][prob]=0;
X }
X
X if ((fp= fopen(SCOREBOARD,"r")) == NULL) {
X printf("Can not open scoreboard file [%s].\n",SCOREBOARD);
X exit(1);
X }
X
X if ( fscanf(fp,"%d",&version) != 1) {
X printf("Can not read version from scoreboard\n");
X exit(2);
X }
X if (version!=CURVERS){
X puts("an old version perhaps?");
X exit(8);
X }
X for(i=1;i<=30;i++){
X if( fscanf(fp,"%d%d%s",&team,&k,temp) != 3){
X printf("%d%d%s\n",team,k,temp);exit(3);}
X if(team==99)team=0;
X if(k<0){
X break;
X }
X else {
X if(team==99)team=0;
X category[team]=k;
X teamnames[team]=malloc((unsigned)(strlen(temp)+2));
X (void)strcpy(teamnames[team],temp);
X }
X }
X
X if(1!=fscanf(fp,"%ld",&starttime))exit(5) ;
X endcontest=starttime+HOURS*3600;
X ct = time((long *)0);
X ct1=ct;
X end="ends ";
X if(ct>endcontest){ct=endcontest;end="ended";}
X
X while ( fscanf(fp,"%d %d %d %d",&sus,&team,&prob,&finish) == 4) {
X if(team==99)team=0;
X if (sus) {
X solvedat[team][prob]=finish;
X }
X else{
X nfail[team]++;
X penal[team] += 10;
X }
X }/*end of file*/
X
X (void) fclose(fp);
X
X for(team=1;team<=30;team++)
X if(category[team])
X for(k=prob=category[team]*6-5;prob<k+6;prob++)
X if(solvedat[team][prob])
X {
X penal[team] +=(solvedat[team][prob]-starttime)/60;
X nworked[team]++;
X }
X else
X {
X penal[team] += (ct - starttime)/60;
X }
X
X printf("\n the scoreboard \n\n");
X printf(" %s\n",ctime((time_t *)&ct1));
X printf(" contest began %s",ctime( (time_t *) &starttime));
X printf(" contest %s %s\n",end,ctime( (time_t *) &endcontest));
X printf(
X "team class #fail penal #solved which who\n");
X for(i=3;i>=1;i--)
X /*if(i!=2)*//*this line eliminates the intermediate category*/
X {
X puts("");
X for(team=1;team<=15;team++)
X if(category[team]==i)
X {
X printf("%3d %s %5d%11d %d "
X ,team,let[category[team]],nfail[team],
X penal[team],
X nworked[team]);
X if(category[team])
X for(k=prob=category[team]*6-5;prob<k+6;prob++)
X if(solvedat[team][prob])printf("%3d", prob);
X else printf(" .");
X if(teamnames[team]){
X (void)putchar(' ');
X (void)putchar(' ');
X puts(teamnames[team]);
X }
X else printf("\n");
X }
X }
X
X}
END_OF_FILE
if test 2852 -ne `wc -c <'score.c'`; then
echo shar: \"'score.c'\" unpacked with wrong size!
fi
# end of 'score.c'
fi
echo shar: End of archive 3 \(of 3\).
cp /dev/null ark3isdone
MISSING=""
for I in 1 2 3 ; do
if test ! -f ark${I}isdone ; then
MISSING="${MISSING} ${I}"
fi
done
if test "${MISSING}" = "" ; then
echo You have unpacked all 3 archives.
rm -f ark[1-9]isdone
else
echo You still need to unpack the following archives:
echo " " ${MISSING}
fi
## End of shell archive.
exit 0
--
Please send comp.sources.unix-related mail to rsalz@uunet.uu.net.