%%% AUTHOR: Jordi Saludes <saludes@grec.upc.es>
%%% DATE: 12/9/1996
%%% FILE: knst.tex
%%% knapsack test macros.
\catcode`@=11
%% Shift Register
%% from H. van der Meer, TUB 15, 1
\newcount\@SR
\def\@SRconst{2097152}
\def\SRset#1{\global\@SR#1\relax}%
\def\@SRadvance{\bgroup
 \ifnum\@SR<\@SRconst\relax
  \@A=0
 \else\@A=1\fi
 \ifodd\@SR
  \advance\@A by1 \fi
 \global\divide\@SR by2
 \ifodd\@A
  \global\advance\@SR\@SRconst\relax\fi
 \egroup}
%% Arithmetic
\newcount\@A
\newcount\@B
\newcount\@C
\newcount\@x \@x=0\relax
\newcount\@y \@y=0\relax
\newcount\@w
\newcount\key
\newcount\df \df=1\relax
\def\qtnno{\the\@x\relax}
\def\inc@#1{\advance#1 by1\relax}
\def\mod@A#1{\@B=\@A \divide\@B by#1
 \multiply\@B by#1
 \advance\@A by-\@B\relax}
\def\gcd#1#2{{\@A=#1 \@C=#2
 \loop\mod@A\@C
  \ifnum\@A>0
  \@B=\@C \@C=\@A \@A=\@B
 \repeat
 \ifnum\@C=1\else
  \errmessage{Invalid stepper/version
number "#1"}\fi}}
\def\adv@w{{\inc@\@y
 \global\multiply\@w by \@y}}
\def\labelno{{\@A=\@B
 \mod@A\key\multiply\@A by\df \the\@A}}
%% Boxing and unboxing
\newtoks\pfootline
\newtoks\pheadline
\newbox\lqtn@bx
\newbox\lanw@bx
\newbox\canw@bx
\newbox\cqtn@bx
\def\new@page{\unvbox\lqtn@bx
 \vfill\penalty-10000
 \global\@w=\verno \adv@w}
\def\append@bx#1#2{%
 \setbox#1=\vbox{\unvbox#1 #2}}
\def\prepend@bx#1#2{%
 \setbox#1=\vbox{#2\unvbox#1}}
\def\add@anw{\@SRadvance
 \iffix@anw
  \global\append@bx{\lanw@bx}{\theanw}%
 \else
  \ifodd\@SR
   \global\prepend@bx{\lanw@bx}{\theanw}%
  \else
   \global\append@bx{\lanw@bx}{\theanw}%
  \fi\fi}%
\def\add@qtn{\@SRadvance
 \iffix@qtn
  \global
   \append@bx{\lqtn@bx}{\unvbox
     \cqtn@bx}%
 \else
  \ifodd\@SR
   \global
    \prepend@bx{\lqtn@bx}{\unvbox
      \cqtn@bx}%
  \else
   \global
    \append@bx{\lqtn@bx}{\unvbox
      \cqtn@bx}%
  \fi\fi}
\def\fix{\global\fix@anwtrue\relax}%
\def\fixqtn{\global\fix@qtntrue\relax}%
\def\qtn{\global\inc@\@x
 \@y=0 \@B=0
 \ifplain\else
  \ifnum\@x>\botqtn
   \new@page\@next\fi\fi
 \rightanw=0 
 \global\fix@anwfalse
 \setbox\cqtn@bx=\vbox\bgroup
  \noindent\qtn@pr}
\def\endqtn{\egroup\add@anw
 \ifplain\ifnum\rightanw=0
  \immediate\write16{There is no
   option marked in question
   \the\@x}\fi\fi
 \setbox\cqtn@bx=\vbox{\box\cqtn@bx
  \preanwskip\box\lanw@bx
  \qtnskip}%
 \adv@w\wr@anw
 \ifplain
  \ifnum\@w>\key
   \message{*}\new@page\fi
 \else
  {\@A=\@w \mod@A\key \global\@w=\@A}\fi
 \mark{\noexpand
  \themark{\the\@x}{\the\@w}}
 \message{.}\add@qtn}
\def\Anw{\ifnum\rightanw>0
  \errmessage{There are several
  options marked in question
  \the\@x}\fi
 \global\rightanw=\@y
 \global\inc@\rightanw
 \anw}
\def\anw{\egroup
 \ifnum\@y=0\else
  \add@anw\fi
 \advance\@B by\@w\relax\inc@\@y
 \setbox\canw@bx=\vtop\bgroup
  \relax\noindent}
\newif\ifplain
\plainfalse
\newcount\verno \verno=0
\newcount\rightanw
\newif\iffix@anw
\newif\iffix@qtn
\fix@qtnfalse
\let\read@line=\relax
\let\@read=\relax
\def\theanw{\hbox{\vrule
 height10pt width\z@\relax
 \anwprompt\ \box\canw@bx\hfill}}
\newcount\verno
\newwrite\anwfile
\newwrite\auxfile
\newdimen\labelw
\def\test#1{\key=#1
 \setbox3=\hbox{\multiply\key by\df
  \the\key}%
 \labelw=\wd3\relax
 \ifnum\verno<1\relax
  \immediate
   \openin\auxfile=\jobname.aux\relax
  \read\auxfile to\@read \@read
  \immediate\closein\auxfile\relax\fi
 \gcd{\the\verno}{\the\key}
 \@SRadvance
 \global\@w=\verno
 \header
 \setbox\lqtn@bx=\vbox{}
 \ifplain
  \message{Plain version}\SRset{0}%
  \global\@w=1
 \else
  \message{Version \the\verno}
  \immediate
   \openin\anwfile=\jobname.ans\relax
 \fi\@next}
\def\endtest{
 \ifplain
  \write\anwfile{\string
   \Key\space\the\key\space
   \the\df\space}%
  \closeout\anwfile
 \else
  \closein\anwfile\fi
 \unvbox\lqtn@bx\vfill\supereject\end}
\def\stepversion#1{\gcd{#1}{\the\key}%
 \immediate
  \openout\auxfile=\jobname.aux\relax
 {\ifnum\@SR=0
   \@SR=\@SRconst
   \divide\@SR by3\fi
 \@SRadvance
 \@A=\verno
 \multiply\@A by#1\relax
 \mod@A\key\relax
 \immediate\write\auxfile{\string
  \verno=\the\@A\space
  \string\SRset{\the\@SR}}}%
 \immediate\closeout\auxfile}
\def\plainversion{\plaintrue\verno=1
 \let\newpage=\new@page
 \def\wr@anw{\immediate
   \write\anwfile{\string\opts
    \space\the\@x\space\the\@y\space
    \the\rightanw\space\the\@w\space}}
 \immediate
  \openout\anwfile=\jobname.ans\relax
 \def\qtn@pr{\llap{\qtnprompt}}
\def\anwprompt{\hbox to\labelw{\hss
 \ifnum\rightanw=\@y
  $\bullet$\ \fi}}
\footline=\pfootline
\headline=\pheadline
\let\@next=\relax
\output={\botmark\plainoutput}
\def\add@qtn{\unvbox\cqtn@bx\penalty-50}}
\def\themark#1#2{\immediate
 \write\anwfile{\string\pagebot
  \space #1\space}%
 \global\divide\@w by#2\relax}
\let\wr@anw=\relax
\let\qtn@pr=\relax
\def\@next{\read\anwfile to\@read
 \@read}
\def\Key #1 #2 {\@next}
\def\opts #1 #2 #3 #4 {\@next}
\def\pagebot #1 {\def\botqtn{#1}}
\def\botqtn{1000}
\let\newpage=\relax
%% Style commands
\def\qtnprompt{\bf\qtnno.\ }
\pfootline={\hss
 Plain version $\dots$\hss}
\pheadline={\ifnum\folio>1
 \thetitle\hss\folio\else\hss\fi}
\footline={Page \folio. Version
 {\tt\the\verno}.
 $\Sigma=$\hskip7em
 $\Sigma/\the\df=$\hfill}
\def\date#1{\def\thedate{#1}}
\def\title#1{\def\thetitle{#1}}
\def\header{
 \line{\bf\thetitle\hfill\thedate}%
 \smallskip
 \line{Name:\ \dotfill}%
 \medskip
{\baselineskip=9pt
 \noindent\small
 Each question has
 only one right answer.
 For each page, add the numbers at
 the left side of 
 your answers and write the total by
 the $\Sigma$. Divide the total
 by~\the\df. If your addition is right,
 the quotient must be integer
 (But this does not mean
 that your choices were correct).
 Do not forget to write down your name,
 but do not write anything else in the
 exam sheet.\par}
 \medskip}
\df=7
\def\anwprompt{\hbox to\labelw{\it
 \hss\labelno\ $\diamond$}}
\def\qtnskip{\vskip 20pt plus25pt }
\let\preanwskip=\smallskip
\font\small=cmr8