rsalz@uunet.uu.net (Rich Salz) (02/08/89)
Submitted-by: jim nelson <nelson@uncecs.edu>
Posting-number: Volume 17, Issue 85
Archive-name: contest-prog/part02
#! /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 2 (of 3)."
# Contents: Makefile chexec8.c compare.c passwd prob1.c prob13.c
# prob13.txt prob14.c prob14.txt prob15.txt prob16.c prob16.txt
# prob17.c prob17.txt prob2.txt prob4.txt prob5.txt prob6.txt sb.c
# start
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'Makefile' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'Makefile'\"
else
echo shar: Extracting \"'Makefile'\" \(2655 characters\)
sed "s/^X//" >'Makefile' <<'END_OF_FILE'
XCC=cc
XCFLAGS= -s -O
X.IGNORE:
X#a public directory such as /usr/local
XLOCAL=/usr/contest
X#the judges directory
XJUDGES=/usr2/judges
X#the judges group
XGROUP=453
X#where the scoreboard is
X#this really should be a dependecy on a .h file for just score.c
X#but it's really easier just now to :
XSCOREBOARD=\"$(JUDGES)/scoreboard\"
X
X#parallel make flag for sequent only:
X#P=&
X#(only, I guess, sequent people appreciate the & flag)
X#maybe others have a similar thingie ... but I cannot know.
X
X#below here shouldn't need modifying (?)
X
XTBEG=prob1.txt prob2.txt prob3.txt prob4.txt prob5.txt prob6.txt
X#TINT=prob7.txt prob8.txt prob9.txt prob10.txt prob11.txt prob12.txt
XTADV=prob13.txt prob14.txt prob15.txt prob16.txt prob17.txt prob18.txt
XTSRC= $(TBEG) $(TINT) $(TADV)
X
XCBEG=prob1.c prob2.c prob3.c prob4.c prob5.c prob6.c
X#CINT=prob7.c prob8.c prob9.c prob10.c prob11.c prob12.c
XCADV=prob13.c prob14.c prob15.c prob16.c prob17.c prob18.c
XCSRC= $(CBEG) $(CINT) $(CADV)
X
XABEG=prob1.ans prob2.ans prob3.ans prob4.ans prob5.ans prob6.ans
X#AINT=prob7.ans prob8.ans prob9.ans prob10.ans prob11.ans prob12.ans
XAADV=prob13.ans prob14.ans prob15.ans prob16.ans prob17.ans prob18.ans
XANS= $(ABEG) $(AINT) $(AADV)
X
XIBEG=prob1.in prob2.in prob3.in prob4.in prob5.in prob6.in
X#IINT=prob7.in prob8.in prob9.in prob10.in prob11.in prob12.in
XIADV=prob13.in prob14.in prob15.in prob16.in prob17.in prob18.in
XIN=$(IBEG) $(IINT) $(IADV)
X
XALLC=$(CSRC) compare.c score.c seconds.c chexec8.c syserr.c digits.c \
Xshorten.c sb.c
XOTHER=n passwd start f sf README Makefile gr testem judge visc \
Xshutofflogins scoreascorrect scoreasincorre scoreboard
X
Xall: $(P) chexec8 seconds compare score judge gr shorten digits \
Xtestem
X chmod +x gr judge testem
X testem
X
Xinstall:
X mkdir keep
X mkdir subdir
X mkdir $(LOCAL)
X chmod 777 $(LOCAL)
X cp seconds $(LOCAL)
X chmod +rx $(LOCAL)/seconds
X sed s/GROUP/$(GROUP)/ judge > $(LOCAL)/judge
X chmod +rx $(LOCAL)/judge
X cp score $(LOCAL)
X chmod 755 $(LOCAL)/score
X chmod u+s $(LOCAL)/score
X
Xshar: $(TSRC) $(ALLC) $(ANS) $(IN) $(OTHER)
X makekit -m -s30k rules contestrules \
X $(TSRC) $(ALLC) $(ANS) $(IN) $(OTHER)
X
Xpasswd: shutofflogins
X shutofflogins
X
Xchexec8: $(P) chexec8.o syserr.o
X cc -o chexec8 chexec8.o syserr.o
X
Xseconds: seconds.o
X cc -o seconds seconds.o
X
Xshorten: shorten.o
X cc -o shorten shorten.o
X
Xcompare: compare.o
X cc -o compare compare.o
X
Xdigits: digits.o
X cc -o digits digits.o
X
Xscore: score.o Makefile
X cc -o score -s score.o
X
Xscore.o: score.c Makefile
X cc -c -DSCOREBOARD=$(SCOREBOARD) score.c
X
Xscoretime:
X cp /dev/null scoretime
X
Xsend:
X uuto Part* 3b2b\!judges
X
Xclean:
X rm *.e *.o Part* chexec8 seconds compare score digits shorten
X
END_OF_FILE
if test 2655 -ne `wc -c <'Makefile'`; then
echo shar: \"'Makefile'\" unpacked with wrong size!
fi
# end of 'Makefile'
fi
if test -f 'chexec8.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'chexec8.c'\"
else
echo shar: Extracting \"'chexec8.c'\" \(882 characters\)
sed "s/^X//" >'chexec8.c' <<'END_OF_FILE'
X#include <stdio.h>
X/*#include <fcntl.h>*/
X#include <signal.h>
X/*#include <sys/wait.h>*/
Xint k;
Xmain(argc,argv)
Xchar **argv;
X{
X int childstatus(),oops();
X setuid(getuid());
X k=fork();
X if(k){
X signal(SIGALRM,oops);
X#ifndef SIGCHLD
X#define SIGCHLD SIGCLD
X#endif
X/*CHLD=20 for dynix, CLD=18 for SysV2*/
X/* anyway what we want is to catch "death of child" signal*/
X signal(SIGCHLD,childstatus);
X alarm(10);
X wait(0);}
X else
X execl(argv[1],"dumbo",0);
X}
Xchildstatus(sig,code,x)
X{
X int i,j,m;
X
X fprintf(stderr,"sig=%d,code=%d, k=%d\n",sig,code,k);
X
X for(i=0;i<200;i++){
X j=k+i;
X j= j % 32768;
X if(j>1){
X m=kill(j,9);
X if(m>=0)fprintf(stderr,"killed %d ",j);
X }
X }
X
X exit(0);
X}
Xoops(sig,code,x)
X{
X fprintf(stderr,"sig=%d,code=%d\n",sig,code);
X fprintf(stderr,"there may be a daemon attack underway\n");
X fprintf(stderr,"kill %d\n",k);
X childstatus(sig,code,x);
X exit(1);
X}
X
END_OF_FILE
if test 882 -ne `wc -c <'chexec8.c'`; then
echo shar: \"'chexec8.c'\" unpacked with wrong size!
fi
# end of 'chexec8.c'
fi
if test -f 'compare.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'compare.c'\"
else
echo shar: Extracting \"'compare.c'\" \(1085 characters\)
sed "s/^X//" >'compare.c' <<'END_OF_FILE'
X#include <stdio.h>
X#define tab '\t'
X#define null '\0'
X#define newline '\n'
Xmain(argc,argv)
Xchar **argv;
X{
X FILE *fpa, *fpb;
X char linea[200], lineb[200];
X char tempa[200], tempb[200];
X
X char *p, *q;
X int eofa=0,eofb=0;
X int compare;
X if(argc!=3)exit(1);
X
X fpa=fopen(argv[1],"r");
X if(fpa==(FILE *)0)exit(2);
X
X fpb=fopen(argv[2],"r");
X if(fpb==(FILE *)0)exit(3);
X eofa=eofb=0;
X compare=0;
Xread:
X if(!eofa)if(fgets(linea,199,fpa)!=linea)eofa=1;
X if(!eofb)if(fgets(lineb,199,fpb)!=lineb)eofb=1;
X if(eofa && eofb)exit(compare);
X
X if(eofa&& !eofb)exit(4);
X if(eofb&& !eofa)exit(5);
X if(eofa || eofb)exit(6);
X
Xfor(p=linea;*p;p++){if(*p==tab) *p=' ';if(*p==newline) *p=0;}
Xfor(p=lineb;*p;p++){if(*p==tab) *p=' ';if(*p==newline) *p=0;}
X p=linea;
X q=lineb;
Xtightloop:
X while(*p==' ' || *p==tab || *p==newline)p++;
X while(*q==' ' || *q==tab || *q==newline)q++;
X if(*p!= *q){
X printf("them: %s\n",linea);
X printf(" us: %s\n",lineb);
X compare=1;
X puts("------------------------------------");
X goto read;
X }
X else{
X p++;
X q++;
X if(*p==null)if(*q==null)goto read;
X goto tightloop;
X }
X
X}
END_OF_FILE
if test 1085 -ne `wc -c <'compare.c'`; then
echo shar: \"'compare.c'\" unpacked with wrong size!
fi
# end of 'compare.c'
fi
if test -f 'passwd' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'passwd'\"
else
echo shar: Extracting \"'passwd'\" \(1863 characters\)
sed "s/^X//" >'passwd' <<'END_OF_FILE'
Xroot:Jfy5vADKI.PUo:0:0:Admin:/:/bin/csh
Xdaemon:*:1:10:Admin:/:
Xusrlimit:HVhogDpnYyySg:2:2:This is a 32 user system, DO NOT REMOVE THIS LINE:/:/dev/null
Xuucp:LHFftElncpbcU:66:10:uucp owner:/usr/lib/uucp:/bin/csh
X3b2b::67:10:UNIX-to-UNIX Copy:/usr/spool/uucppublic:/usr/lib/uucp/uucico
X3b2a::68:10:UNIX-to-UNIX Copy:/usr/spool/uucppublic:/usr/lib/uucp/uucico
Xlmc::69:10:UNIX-to-UNIX Copy:/usr/spool/uucppublic:/usr/lib/uucp/uucico
Xsigma::71:10:UNIX-to-UNIX Copy:/usr/spool/uucppublic:/usr/lib/uucp/uucico
Xcltsqnt::72:10:sequent:/usr/spool/uucppublic:/usr/lib/uucp/uucico
Xnelson:TQQhhbK575Jtc:100:0:j h nelson,MO-263,3300,3926032/3955570/147.53,:/usr1/nelson:/bin/csh
Xherbst:hwshDCyvtoI.s:104:100:R.T. Herbst,MO 256,3248,2563304,universe(ucb):/usr1/herbst:
Xguest::105:100:a guest:/usr1/guest:/usr/uncw/score
Xscore::105:100:a guest:/usr1/guest:/usr/uncw/score
Xwhipkey:HinSCYmbORBjk:116:100:k whipkey:/usr1/whipkey:
Xsmithh:7g3ZmER5p4epA:123:100:H.F. Smith,CH 200-E,3953819,,:/usr1/smithh:
Xnorris:8F42zTTbXo3Ak:125:100:f r norris,264,3953301,,:/usr1/norris:/bin/csh
Xjudges:8HrGYoJq3fxdQ:453:453:the judges,,,,:/usr2/judges:/bin/csh
Xteam1:mrCEcc.F8UocI:478:478:team1:/usr1/team1:/bin/csh
Xteam2:6DsWELtbNWOLg:479:479:team2:/usr1/team2:/bin/csh
Xteam3:BRc8uYjDHRO6.:480:480:team3:/usr2/team3:/bin/csh
Xteam4:Icegxkv..vEcQ:481:481:team4:/usr2/team4:/bin/csh
Xteam5:BjLwNCM7HePeU:482:482:team5:/usr2/team5:/bin/csh
Xteam6:Oo3fEvH61VKeo:483:483:team6:/usr2/team6:
Xteam7:k0isgx3nuFK1Q:484:484:team7:/usr3/team7:
Xteam8:h35xJdDATkW5Y:485:485:team8:/usr3/team8:
Xteam9:foTUAMb51CRDM:486:486:team9:/usr1/team9:
Xteam10:b/vzhtWaiNAJA:487:487:team10:/usr1/team10:
Xteam11:6LmSPFh9PpBDw:488:488:team11:/usr3/team11:
Xteam12:omg0gx1Lw2lr2:489:489:team12:/usr3/team12:/bin/csh
Xteam13:FlwviGdBAAXFE:490:490:team13:/usr3/team13:/bin/csh
Xteam14:kYWLsTLpfiLFg:491:491:team14:/usr3/team14:/bin/csh
END_OF_FILE
if test 1863 -ne `wc -c <'passwd'`; then
echo shar: \"'passwd'\" unpacked with wrong size!
fi
# end of 'passwd'
fi
if test -f 'prob1.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'prob1.c'\"
else
echo shar: Extracting \"'prob1.c'\" \(829 characters\)
sed "s/^X//" >'prob1.c' <<'END_OF_FILE'
Xmain()
X{
X int *left, *right, *doub;
X int l,m, i=0,j,k;
X int nd=0;
X char *malloc();
Xleft=(int *)malloc(500*sizeof(int));
Xright=(int *)malloc(500*sizeof(int));
Xdoub=(int *)malloc(500*sizeof(int));
X
X for(i=0;i<500;i++)doub[i]=0;
X i=0;
X while( scanf("%d%d",&j,&k)==2)
X if(j>=0 && k>=0){left[i]=j; right[i]=k; i++;}
X else break;
X i--;
X for (j=0;j<=i;j++)
X {
X k=left[j];
X for(m=0;m<=i;m++)if(k==right[m]){doub[nd++]=k;break;}
X }
X if(nd){
X/* for(i=0;i<nd;i++)if(doub[i])printf("%d\n",doub[i]);*/
X
X if(nd>=2){
X for(i=0;i<nd-1;i++)
X for(j=i+1;j<nd;j++)
X if(doub[i]>doub[j]){k=doub[i];doub[i]=doub[j];doub[j]=k;}
X else {}
X }else printf("%d\n",doub[0]);
X
X }else{}
X doub[nd]= -1;
X/* for(i=0;i<nd;i++)if(doub[i])
Xprintf("%d\n",doub[i]);
X*/
X
Xk= -1;
X
X for(i=0;i<nd;i++)if(doub[i]!=doub[i+1])
Xprintf("%d\n",doub[i]);
X
X return 0;
X}
END_OF_FILE
if test 829 -ne `wc -c <'prob1.c'`; then
echo shar: \"'prob1.c'\" unpacked with wrong size!
fi
# end of 'prob1.c'
fi
if test -f 'prob13.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'prob13.c'\"
else
echo shar: Extracting \"'prob13.c'\" \(2166 characters\)
sed "s/^X//" >'prob13.c' <<'END_OF_FILE'
Xmain(){
X int oldop,mask,flag;
X#define newline '\n'
X#define null '\0'
X /*
XFrom norris Fri Nov 11 11:06:03 1988
XBinary-binary
X
X Mathematicians refer to addition and subtraction as binary
Xoperations. Since computer scientists like to take things much
Xfarther than they were intended, you are going to write a
Xbinary binary calculator.
X This calculator program will accept infix expressions involving
Xonly + and - and unsigned binary integers. No parentheses or
Xother operations will be present. You must compute the value
Xof the expression and display the result in binary. Negative
Xresults should be printed with a leading minus sign.
X Data considerations:
X Input will consist of an unspecified number of expressions,
X one per line; end-of-file will indicate the end of data. Each
X expression will contain no leading or embedded blanks. No
X expression will contain more than 80 characters. The
X expression values are to be computed left-to-right. No
X number or intermediate value will require more than 15 bits
X of precision. Output should start in column 1 of the
X output file, one result per line, with no leading zeroes.
X
XExample:
X the input expression: 110+11-1+100
X results in the output
X1100
X
X the input expression: 1100-11000+111-10
X results in the output
X-111
X*/
X char line[90];
X int sum,n;
X char *p;
X char *gets();
X while( gets(line)==line ){
X p=line;
X n=0;
X for(p=line,n=0,sum=0,oldop='+';;p++) {
X switch(*p){
X case '-':
X case '+':
X if(oldop=='+')sum += n;
X else sum -=n;
X n=0;
X oldop= *p;
X break;
X case '0':
X n= n* 2;
X break;
X case '1':
X n= n*2+1;
X break;
X case newline:
X case 0:
X if(oldop=='+')sum += n;
X else sum -=n;
X goto out;
X/* n=0; */
X/* oldop= *p;*/
X break;
X default:
X ;
X }
X }
Xout: /*printf("%d\n",sum);*/
X ;
X if(sum==0){
X putchar('0');
X putchar(newline);
X continue;
X }
X if(sum<0){
X putchar('-');
X sum = - sum;
X }
X for(mask=0100000, flag=0; mask; mask >>=1){
X
X if(sum & mask ){
X putchar('1');
X flag=1;
X } else if(flag)putchar('0');
X }
X putchar(newline);
X
X }/*endwhile gets*/
X}/*end main*/
END_OF_FILE
if test 2166 -ne `wc -c <'prob13.c'`; then
echo shar: \"'prob13.c'\" unpacked with wrong size!
fi
# end of 'prob13.c'
fi
if test -f 'prob13.txt' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'prob13.txt'\"
else
echo shar: Extracting \"'prob13.txt'\" \(1400 characters\)
sed "s/^X//" >'prob13.txt' <<'END_OF_FILE'
XProblem 13: Binary-binary.
X
X Mathematicians refer to addition and subtraction as binary
Xoperations. Since computer scientists like to take things much
Xfarther than they were intended, you are going to write a
Xbinary binary calculator.
X This calculator program will accept infix expressions involving
Xonly + and - and unsigned binary integers. No parentheses or
Xother operations will be present. You must compute the value
Xof the expression and display the result in binary. Negative
Xresults should be printed with a leading minus sign.
X Data considerations:
X Input will consist of an unspecified number of expressions,
X one per line; end-of-file will indicate the end of data. Each
X expression may contain leading or embedded blanks; however, no
X number will contain embedded blanks.
X A totally blank line should evoke an output of '0'.
X No expression will contain more than 80 characters. The
X expression values are to be computed left-to-right. No
X number or intermediate value will require more than 15 bits
X of precision. Output should start in column 1 of the
X output file, one result per line, with no leading zeroes.
X
XExample:
X the input expression: 110+11- 1 +100
X results in the output
X1100
X
X the input expression: 1100 - 11000+111-10
X results in the output
X-111
X
X the input expression: <a blank line>
X results in the output
X0
END_OF_FILE
if test 1400 -ne `wc -c <'prob13.txt'`; then
echo shar: \"'prob13.txt'\" unpacked with wrong size!
fi
# end of 'prob13.txt'
fi
if test -f 'prob14.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'prob14.c'\"
else
echo shar: Extracting \"'prob14.c'\" \(1054 characters\)
sed "s/^X//" >'prob14.c' <<'END_OF_FILE'
Xmain(){
X int a[4];
X int numfnd = -1;
X int this, found[10000];
X int t;
X int p,q,r,s,i,j,k,l,n;
X for(i=0;i<10;i++)
X for(j=0;j<10;j++)if(i==j)continue;
X else
X for(k=0;k<10;k++)
X for(l=0;l<10;l++)if(k==l)continue;
X else
X {
X p=i*10+j;
X q=k*10+l;
X
X r=j*10+i;
X s=l*10+k;
X if(p==r || p==s ||q==r||q==s)continue;
X else
X if((n=p*q) == r*s){
X int i,j;
X /*bingo*/
X a[0]=p;
X a[1]=q;
X a[2]=r;
X a[3]=s;
Xxxx:
X for(i=0;i<4;i++)for(j=i;j<4;j++)if(a[i]>a[j]){
X t=a[i];
X a[i]=a[j];
X a[j]=t;
X goto xxx;
X }
X /*printf("%d %d %d %d %d " ,p,q,r,s,n);*/
X this=a[0]*1000000+a[1]*10000+a[2]*100+a[3];
X if(numfnd== -1){
X found[++numfnd]=this;
X printf("%d %d\n",a[0],n);
X continue;
X }
X else{
X t=0;
X for(i=0;i<=numfnd;i++)if(found[i]==this)t=1;
X }
X if(!t)
X {
X found[++numfnd]=this;
X printf("%d %d\n",a[0],n);
X }
X else /*putchar('\n')*/ ;
X }
X }
X
X
X}
END_OF_FILE
if test 1054 -ne `wc -c <'prob14.c'`; then
echo shar: \"'prob14.c'\" unpacked with wrong size!
fi
# end of 'prob14.c'
fi
if test -f 'prob14.txt' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'prob14.txt'\"
else
echo shar: Extracting \"'prob14.txt'\" \(1119 characters\)
sed "s/^X//" >'prob14.txt' <<'END_OF_FILE'
XProblem 14: Reverse products.
X
X
XThe product 64 * 69 = 4416, and so also is the product 46 * 96 with the
Xdigits reversed in both numbers. Write a program that prints all such
Xpairs of two-digit numbers with this property. For purposes of this
Xproblem, numbers less than 10 are to be considered two-digit numbers.
XHowever, exclude the following: numbers having the same two digits
X(e.g., 77), pairs where one of the original numbers is just the
Xreverse of the other (e.g., 46 and 64), and any DUPLICATE sets of
Xnumbers (i.e., the foursome 46, 64, 69, 96 should be found just once).
XThe output for this problem should consist of lines,
Xeach with two values: p = the smallest element of a foursome, and
Xq = the corresponding product value. Thus, the line for this example
Xcase would contain: 46 4416. Moreover, the lines should be
Xordered by values of p, and then by values of q in case of
Xrepetitions of p values.
X
XThere is no input file for this problem.
X
XSample output:
X1 20 <this is tricky: comes from 01*20 == 10*02 >
X1 30
X ...
X ...
X34 2924
X ...
X
XHint: there are fifty output lines in a correct answer.
END_OF_FILE
if test 1119 -ne `wc -c <'prob14.txt'`; then
echo shar: \"'prob14.txt'\" unpacked with wrong size!
fi
# end of 'prob14.txt'
fi
if test -f 'prob15.txt' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'prob15.txt'\"
else
echo shar: Extracting \"'prob15.txt'\" \(1064 characters\)
sed "s/^X//" >'prob15.txt' <<'END_OF_FILE'
XProblem 15: Circular execution.
X
X
XYou and your friends are suddenly rounded up into a circle. You are told
Xthat, starting from the head of the circle, THEY will count to M, execute
Xthat Mth person, close the circle, and repeat this process until just one
Xperson is left to escape. Given that there are N persons and that the
Xrule is to execute every Mth person, you need to decide which position
Xto take in the circle if you are to remain alive.
X
XWrite a program that reads and computes, for four pairs of (M,N) values.
XFor each pair, as your program executes (literally!), have it print out the
Xidentity of each person as he is eliminated. For example, with M = 7 and
XN = 11, the output would be: 7 3 11 9 8 10 2 6 1 4 5
X(showing 5 (the last guy in the list) surviving).
X
XThere will be exactly four M,N pairs in the input datafile, two per line.
XM and N will each be less than or equal to 20.
XSuch as:
X7 11
X9 13
X13 15
X7 14
X
XNote that there is NO requirement that M be less than N.
X
XBe careful that your output consists of exactly four lines.
END_OF_FILE
if test 1064 -ne `wc -c <'prob15.txt'`; then
echo shar: \"'prob15.txt'\" unpacked with wrong size!
fi
# end of 'prob15.txt'
fi
if test -f 'prob16.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'prob16.c'\"
else
echo shar: Extracting \"'prob16.c'\" \(1273 characters\)
sed "s/^X//" >'prob16.c' <<'END_OF_FILE'
Xmain(){
X int ii,jj,kk,a,b,M,N,i,j,k;
X int abin,bbin,nbin[200],bin[200][30];
X
X scanf("%d%d",&M,&N);
X for(i=1;i<=N;i++){
X bin[i][1]=i;
X nbin[i]=1;
X }
X for(kk=1;kk<=M;kk++){
X if(scanf("%d%d",&a,&b)!=2)exit(1);
X ii=jj=0;
X for(i=1;i<=N;i++){
X if(nbin[i]<1)continue;
X for(j=1;j<=nbin[i];j++)
X if(bin[i][j]==a){
X ii=i;
X jj=j;
X }
X }
X if(ii==0||jj==0){
X printf("oops a=%d b=%d ii=%d jj=%d i=%d j=%d nbin[ii]=%d\n"
X ,a,b,ii,jj,i,j,nbin[ii]);
X exit(2);
X }
X /*bin[ii][jj]=0;*/
X abin=ii;
X ii=jj=0;
X for(i=1;i<=N;i++){
X if(nbin[i]<1)continue;
X for(j=1;j<=nbin[i];j++)
X if(bin[i][j]==b){
X ii=i;
X jj=j;
X break;
X }
X }
X if(ii==0||jj==0){
X printf("oops ii=%d jj=%d i=%d j=%d nbin[ii]=%d\n"
X ,ii,jj,i,j,nbin[ii]);
X exit(3);
X }
X bbin=ii;
X for(j=1;j<=nbin[abin];j++)bin[bbin][++nbin[bbin]]=bin[abin][j];
X nbin[abin]=0;
X }
X for(i=1;i<=N;i++)
X {
X k=nbin[i];
X if(k<1)continue;
X if(k>=2){
X int l,m;
X for(l=1;l<k;l++)for(m=l+1;m<=k;m++)if(bin[i][l]>bin[i][m]){
X int t;
X t=bin[i][l];
X bin[i][l]=bin[i][m];
X bin[i][m]=t;
X }
X }
X }
X for(i=1;i<=N;i++)
X for(kk=1;kk<=N;kk++)
X if(nbin[kk]<1)continue; else{
X if(bin[kk][1]==i){
X for(j=1;j<=nbin[kk];j++) printf(" %d ",bin[kk][j]);
X puts("");
X
X }
X }
X
X}
END_OF_FILE
if test 1273 -ne `wc -c <'prob16.c'`; then
echo shar: \"'prob16.c'\" unpacked with wrong size!
fi
# end of 'prob16.c'
fi
if test -f 'prob16.txt' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'prob16.txt'\"
else
echo shar: Extracting \"'prob16.txt'\" \(1059 characters\)
sed "s/^X//" >'prob16.txt' <<'END_OF_FILE'
XProblem 16: Equivalence classes.
X
X
XSuppose that we have a set of N objects {a[i]}. We are also given M statements
Xof the form a[i] == a[j] . Let us assume that the objects have been mapped into
Xthe integers 1 .. N by some manner. For example, with N = 19 and M = 16, we
Xmight have the following objects and relationships:
X 18 = 12 16 = 14 8 = 18 16 = 6
X 6 = 10 9 = 1 17 = 4 16 = 17
X 8 = 2 3 = 13 9 = 11 3 = 8
X 11 = 5 7 = 19 3 = 9 19 = 15
XWrite a program that reads M and N, followed by the M pairings i = j,
Xwith i and j both in the range 1 .. N. Your program should compute which
Xobjects fall into which classes of equivalent objects, and should then
Xprint out these classes, as follows: objects sorted within each class,
Xand classes printed in order of their first members. Thus, for the example
Xabove, the output would be:
X 1 2 3 5 8 9 11 12 13 18
X 4 6 10 14 16 17
X 7 15 19
X
END_OF_FILE
if test 1059 -ne `wc -c <'prob16.txt'`; then
echo shar: \"'prob16.txt'\" unpacked with wrong size!
fi
# end of 'prob16.txt'
fi
if test -f 'prob17.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'prob17.c'\"
else
echo shar: Extracting \"'prob17.c'\" \(787 characters\)
sed "s/^X//" >'prob17.c' <<'END_OF_FILE'
X#include <stdio.h>
Xmain(){
X int z,s,x[4],y[4],tx,ty,xi,yi,abig,area();
X char *p;
X int t=0,i,k;
X while( scanf("%d%d",&x[1],&y[1]) == 2){
X scanf("%d%d",&x[2],&y[2]);
X scanf("%d%d",&x[3],&y[3]);
X t++;
X for(k=1;k<=7;k++){
X scanf("%d%d",&tx,&ty);
X abig=area(x,y);
X s=(int)0;
X for(i=1;i<=3;i++){
X xi=x[i];
X x[i]=tx;
X yi=y[i];
X y[i]=ty;
X s +=area(x,y);
X x[i]=xi;
X y[i]=yi;
X
X }
X z=s-abig;
X if(z<0)z= -z;
X if(z==0){
X/* fprintf(stderr,"yes\n");*/
X p="inside";}
X else {
X/* fprintf(stderr,"no\n");*/
X p="outside";}
X printf("%d %d is %s triangle %d\n",(int)(tx),(int)(ty),p,t);
X/* fprintf(stderr,"\n");*/
X }
X }
X}
Xint area(x,y)
Xint x[],y[];
X{
X int z;
X z= (x[1]*y[2]-x[1]*y[3]+x[2]*y[3]-x[2]*y[1]+x[3]*y[1]-x[3]*y[2]);
X/* z= z ;*/
X if(z<0)z = -z;
X/* fprintf(stderr,"area=%d ",z);*/
X return z;
X}
END_OF_FILE
if test 787 -ne `wc -c <'prob17.c'`; then
echo shar: \"'prob17.c'\" unpacked with wrong size!
fi
# end of 'prob17.c'
fi
if test -f 'prob17.txt' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'prob17.txt'\"
else
echo shar: Extracting \"'prob17.txt'\" \(936 characters\)
sed "s/^X//" >'prob17.txt' <<'END_OF_FILE'
XProblem 17: Point inside triangle.
X
XWhen is a point (s,t) inside a triangle with vertices (x1, y1),
X(x2, y2), (x3, y3)?? For this problem, the input will contain 20
Xlines containing coordinate pairs:
X three lines with coordinates of three vertices of first triangle
X seven lines, each with coordinates of a point to be tested therein
X three lines with coordinates of three vertices of second triangle
X seven lines, each with coordinates of a point to be tested therein
X
XFor example, if the first five lines of input were
X 3 2
X 6 10
X 15 7
X 5 7
X 14 6
Xthe corresponding output would be
X 5 7 is inside triangle 1
X 14 6 is outside triangle 1
X
XSpacing of the output is not important, but you must have the words
X"is", "inside" or "outside", and "triangle" in your output, just as
Xin the example.
X
XThe vertices of the triangle, and the test point, are guaranteed to
Xbe integers.
X
END_OF_FILE
if test 936 -ne `wc -c <'prob17.txt'`; then
echo shar: \"'prob17.txt'\" unpacked with wrong size!
fi
# end of 'prob17.txt'
fi
if test -f 'prob2.txt' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'prob2.txt'\"
else
echo shar: Extracting \"'prob2.txt'\" \(1204 characters\)
sed "s/^X//" >'prob2.txt' <<'END_OF_FILE'
XProblem 2: Character count.
X
XFor all the lines in a file, count the occurrences of the
Xvarious characters in that file.
X
XThe input file will be a text file of unknown length, but
Xwith each line guaranteed to be less than 80 characters long.
X
XThe input file may contain tabs (ascii octal 011), blanks,
Xand all the printable characters, as well as newlines.
X
XDo not attempt to count newlines; only tabs, blanks, and printable
Xcharacters.
X
XYour output should consist of two integers per line. The leftmost
Xshould be the ascii character printed in decimal form, the rightmost
Xshould be the count of the character.
X
XBUT: do not output zero-counts. That is: do not print any line
Xfor which the count is zero.
X
XExample:
Xtime for all
X good men to
Xcome to the aid of
X
X(note that the word "good" is preceded by a tab-character).
X
XShould produce:
X 9 1 <this is the tab>
X 32 8 <this is "blank">
X 97 2 <this is "a">
X 99 1 <etc., and of course, you don't
X 100 2 print these comments>
X 101 4
X 102 2
X 103 1
X 104 1
X 105 2
X 108 2
X 109 3
X 110 1
X 111 7
X 114 1
X 116 4
END_OF_FILE
if test 1204 -ne `wc -c <'prob2.txt'`; then
echo shar: \"'prob2.txt'\" unpacked with wrong size!
fi
# end of 'prob2.txt'
fi
if test -f 'prob4.txt' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'prob4.txt'\"
else
echo shar: Extracting \"'prob4.txt'\" \(864 characters\)
sed "s/^X//" >'prob4.txt' <<'END_OF_FILE'
XProblem 4: Print odds and evens side-by-side.
X
XThe input file will consist of some positive integers. The number
Xof integers will be less than thirty. Each integer will be
Xgreater than or equal to one. The last line of the input file
Xwill contain a negative number, for use as a sentinel. There will
Xbe one integer per line, left justified, beginning in column 1.
X
XThe output is to consist of lines of the form:
Xodd number even number
X
Xwhere the numbers are those from the input file, in the order in
Xwhich they occurred.
X
XIf there are fewer odd numbers than even numbers, pad with -1 .
XIf there are fewer even numbers than odd numbers, pad with -1 .
X
XDo not output a line consisting of -1 -1 .
X
XExample input file:
X9
X8
X12
X13
X2
X4
X-1
X
XThe output should be:
X9 8
X13 12
X-1 2
X-1 4
X
XAnother example file:
X9
X11
X13
X2
X4
X7
X-1
X
XThe output should be
X9 2
X11 4
X13 -1
X7 -1
END_OF_FILE
if test 864 -ne `wc -c <'prob4.txt'`; then
echo shar: \"'prob4.txt'\" unpacked with wrong size!
fi
# end of 'prob4.txt'
fi
if test -f 'prob5.txt' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'prob5.txt'\"
else
echo shar: Extracting \"'prob5.txt'\" \(1051 characters\)
sed "s/^X//" >'prob5.txt' <<'END_OF_FILE'
XProblem 5: count the number of words in a text file.
X
XThe input file will consist of some number of lines.
XThere will be only lowercase letters and blanks (and of course,
Xnewlines) in the input file. (I.e., no tabs).
XEach line will have zero or more non-blank strings separated
Xby one or more blanks. Leading blanks are permitted in the input file.
XA "word" is defined as a "string which does not contain a blank".
XYour program should produce exactly as many lines as there are
Xlines in the input file. Your output should be the integer number
Xrepresenting the number of "words" on the corresponding input line.
X
XExample: if the input file consists of exactly six lines:
Xnow is the time
Xfor all
X thirty days hath
X september
X
X testing testing cqcqcq de k4xe
X
XThen your output would be
X4
X2
X3
X1
X0
X5
X <this line is not part of your output>
XPay particular attention to the fact that a blank line should
Xproduce a zero-count in your output file. To emphasize:
XYou should produce some output for each line of input, even if
Xit is totally blank.
END_OF_FILE
if test 1051 -ne `wc -c <'prob5.txt'`; then
echo shar: \"'prob5.txt'\" unpacked with wrong size!
fi
# end of 'prob5.txt'
fi
if test -f 'prob6.txt' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'prob6.txt'\"
else
echo shar: Extracting \"'prob6.txt'\" \(988 characters\)
sed "s/^X//" >'prob6.txt' <<'END_OF_FILE'
XProblem 6: Count the relationships.
X
XThe input file will contain an unknown number of lines each
Xhaving four positive integers. The last line will be
X -1 -1 -1 -1
X
XDo not output anything for the last line; it's there for use
Xas a sentinel.
X
XThe numbers on each line are guaranteed to be distinct; that is,
Xno number will appear more than once in the quartet of numbers.
X
XFor each line, count the number of times a smaller number appears
Xto the left of a larger number, and also count the number of times
Xa larger number appears to the left of a smaller number;
Xfor example, if the four numbers are
X 7 9 27 23
Xthe "lessthan" count is 5, because 7<9, 7<27, 7<23, 9<27, 9<23,
Xbut 27>23; the "greaterthan" count is 1, because 27>23.
X
XYour output should be: the original four numbers followed by
Xthe lessthan-count and the greaterthan-count all on one line.
X
XEach input line should generate one output line.
X
XFor example, your output line for the above input line would be:
X 7 9 27 23 5 1
X
END_OF_FILE
if test 988 -ne `wc -c <'prob6.txt'`; then
echo shar: \"'prob6.txt'\" unpacked with wrong size!
fi
# end of 'prob6.txt'
fi
if test -f 'sb.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'sb.c'\"
else
echo shar: Extracting \"'sb.c'\" \(1719 characters\)
sed "s/^X//" >'sb.c' <<'END_OF_FILE'
X#include <stdio.h>
X#define newline '\n'
X#define blank ' '
X#define tab '\t'
X#define indent {myputs(line);ilev++;goto lbl;}
X#define undent {ilev--;myputs(line);goto lbl;}
Xint ilev = 0;
Xmain(argc,argv) char **argv;
X{
X char line[512], *a;
X int i;
X
X while(gets(line)==line){
X a=line;
X while(*a){if(*a==newline)*a=0; a++;}
X if(endsin(line,"then")==0){
X indent }
X if(endsin(line,"else")==0){
X
X ilev--; myputs(line); ilev++;goto lbl;
X }
X if(endsin(line,"fi")==0){
X undent }
X if(endsin(line,"done")==0){
X undent }
X if(endsin(line,"do")==0){
X indent }
X if(begins(line,"case")==0){
X indent }
X if(endsin(line,"esac")==0){
X undent }
X myputs(line);
Xlbl: ;
X }
X}
Xmyputs(p)char *p;
X{
X int i;
X while(*p==blank ||*p==tab)p++;
X if(ilev>0)for(i=1;i<=ilev;i++)printf(" ");
X/* printf("%d",ilev);*/
X puts(p);
X}
X
Xendsin(a,b)
Xchar *a, *b;
X{
X char *aa;
X int i;
X aa=a;
X while(*aa==blank || *aa==tab)aa++;
X if(strlen(a)<strlen(b))return -1;
X a = a +strlen(a)-strlen(b);
X i= kindex(a,b);
X if(strlen(aa)==strlen(b))return i;
X a--;
X if(*a==tab||*a==';'||*a==blank)return i; else return -1;
X/* printf("in endsin, a=%s b=%s returning %d\n",a,b,i);*/
X/* fflush(stdout);*/
X/* return i;*/
X
X}
X
X
X
X
X
Xbegins(a,b)
Xchar *a, *b;
X{
X int i;
X while(*a==blank || *a==tab)a++;
X return kindex(a,b);
X
X}
X
X
X
X
Xkindex(s,t)
Xchar s[],t[];
X{
X int c,i,j,k;
X c=s[0];
X if(c==0){return -1;
X/* i=puts("in kindex ... dummy, s[0] is zero");j=i;*/
X/* puts(t);*/
X/* if(i==j)exit(1);*/
X }
X c=t[0];
X if(c==0){return -1;
X/* i=puts("in kindex ... dummy, t[0] is zero");j=i;*/
X/* puts(s);*/
X/* if(j==i)exit(1);*/
X }
X for(i=0;s[i] !='\0'; i++){
X for(j=i,k=0;t[k] !='\0' && s[j]==t[k];j++,k++)
X ;
X if(t[k]=='\0')return (i);
X }
X return(-1);
X}
END_OF_FILE
if test 1719 -ne `wc -c <'sb.c'`; then
echo shar: \"'sb.c'\" unpacked with wrong size!
fi
# end of 'sb.c'
fi
if test -f 'start' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'start'\"
else
echo shar: Extracting \"'start'\" \(1067 characters\)
sed "s/^X//" >'start' <<'END_OF_FILE'
X
X#! /bin/sh
X
X#judges mailbox
XMAIL=$MAIL
X
X#a public dir where score lives
X#(the scoreboard should be local an only readable by judges,
X# cause "score should be setuid judges)
XLOCAL=/usr/contest
X
X#four hours:
XLENGTH=14400
X
Xcd $HOME
Xrm -f /tmp/prob*.txt
X
X
Xrm -f t[0-9]*[0-9]*
Xrm -f keep/*
Xrm -f subdir/*
X
X#version:21
Xecho "21">xxxx
X/bin/cp /dev/null listofteams
X
Xwhile :
Xdo
Xread teamno
Xcase $teamno in
X "") echo null team number;exit;;
X -1)break;
Xesac
Xecho team$teamno>>listofteams
Xread cat
Xread name
X
X
X echo $teamno $cat $name >>xxxx
X echo $teamno $cat $name
X
X
Xdone
Xecho "-1 -1 xx">>xxxx
X#change the following line to y for a live start
Xzork=y
Xcase $zork in
X y)
X for i in 1 2 3 4 5 6 13 14 15 16 17 18
X do
X /bin/cp prob$i.txt /tmp
X done ;;
Xesac
Xchmod og+r /tmp/*.txt
X
X/bin/cp scoreboard scoreboard.old
Xseconds=`${LOCAL}/seconds`
Xecho $seconds >> xxxx
Xecho $seconds > starttime
Xecho endtime = $endtime
Xendtime=`expr $seconds '+' ${LENGTH}`
Xecho endtime = $endtime
Xecho $endtime > endtime
X/bin/cp xxxx scoreboard
Xchmod og-rwx scoreboard
X
X
X${LOCAL}/score
Xn mal
Xn ${MAIL}
END_OF_FILE
if test 1067 -ne `wc -c <'start'`; then
echo shar: \"'start'\" unpacked with wrong size!
fi
chmod +x 'start'
# end of 'start'
fi
echo shar: End of archive 2 \(of 3\).
cp /dev/null ark2isdone
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.