\documentclass[11pt]{article}

% Define some commands for names to be used in this document
%-----------------------------------------------------------------
\newcommand{\myname}{Bill Slough}
\newcommand{\course}{MAT 4370}       
\newcommand{\assignment}{Programming Challenge}                  
\newcommand{\probs}{The Trip}          
\newcommand{\duedate}{Sample Solution}              
%-----------------------------------------------------------------

% Declare some LaTeX packages for this document
%-----------------------------------------------------------------
\usepackage{clrscode}
\usepackage{amsmath}            % AMS enhancements for mathematical formulas
\usepackage{amsthm}             %     ... for theorem environments
\usepackage{amssymb,latexsym}   %     ... for additional mathematical symbols
\usepackage{graphicx}           % For graphics inclusion (e.g., PDF files)
\usepackage{verbatim}           % Useful for including code snippets
\usepackage{enumerate}          % Makes enumerated lists simpler to control
\usepackage[left=1in,right=1in,top=0.75in,bottom=0.5in]{geometry} % sets margins
\usepackage[colorlinks=true,linkcolor=blue,urlcolor=blue]{hyperref}
\usepackage[dvipsnames,usenames]{color}    % Colors! 
\usepackage{url}
\usepackage{ifthen}
\usepackage{listings}           % Program listings
\usepackage{xcolor}
\usepackage{fix-cm}
%-----------------------------------------------------------------

% Define the desired format for the title to appear on the first page
%-----------------------------------------------------------------
\newcommand{\mytitle}{
\begin{flushleft}
\bfseries
\assignment                  \hspace*{\fill}              \myname\\
\probs    \hspace*{\fill}    \course    \hspace*{\fill}   \duedate\\
\rule[10pt]{\linewidth}{1pt}
\end{flushleft}
}
%-----------------------------------------------------------------

% Define the desired page headings for all pages except the first
%-----------------------------------------------------------------
\pagestyle{myheadings}
\markright{\course{} \assignment: \myname}
%-----------------------------------------------------------------

% Define an exercise environment, with two parameters:
%   -- how to refer to it: Exercise, Problem, etc. (optional) 
%   -- the exercise number
%-----------------------------------------------------------------
\newenvironment{exercise}[2][Exercise]
 {\begin{trivlist}\item[\hspace{0pt} \textbf{#1}~\textbf{#2.}]}
 {\end{trivlist}}
%-----------------------------------------------------------------

% Define a command to check for the existence of the student name
%-----------------------------------------------------------------
\newcommand{\checkname}
{
\ifthenelse{\equal{\myname}{Joe College}}
{
  \vspace*{\fill}
  \begin{center}
    {\LARGE \bf Your name is {\color{BrickRed} \myname}?\\[3pt]
    Please change \texttt{\color{BrickRed} \textbackslash myname} and re-process.}
  \end{center}
  \vspace*{\fill}
  \end{document}
  \newpage
}
{}
}

%\setlength{\parindent}{0in}

%
% Document begins here...
%-----------------------------------------------------------------
\begin{document}
\thispagestyle{empty}   % No page headings for page 1...
\mytitle                % Instead, put the customized title on this page
\checkname

\renewcommand{\qedsymbol}{}  % Suppress "end-of-proof" symbol
                             % throughout proof environments

\vspace{-0.3in}
\begin{exercise}{UVa \#10137 (The Trip)}
The problem is described at:
\begin{quote}
 \url{http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1078}.
\end{quote}
\end{exercise}


\subsection*{Lessons Learned}
\begin{itemize}\renewcommand{\itemsep}{0pt}
 \item I spent more time thinking than I did actual programming ---
   and this had a nice payoff: my program was accepted by the judge on
   the second submission.
 \item \textbf{Floating point arithmetic requires great care.} 
  Because every penny matters in this problem, it is much safer to
   work with integer types. 
 \item A few students asked me for help in finding a counter-example;
   i.e., could we find a data set that would show incorrect output
   for their program.
   This turned out to be much more difficult than I expected.  
\textbf{Devising good test cases is hard work!} 
  \item Programming---in C or any other language---is an exacting and
    challenging activity.  Good planning and sound
    algorithms are required. The fact that our programs must correctly respond to
    an infinite possibility of inputs is one of the most challenging aspects.
\end{itemize}

\subsection*{Explanation}
As a starting point, let's consider a few concrete examples.  Suppose
five students go on a trip with the following costs, in cents:
$$20 \hspace{20pt} 18 \hspace{20pt} 16 \hspace{20pt} 4 \hspace{20pt} 2$$
This is the easiest situation, since the average cost is 
$(20 + 18 + 16 + 4 + 2)/5 = 60/5 = 12.$ (This is the easiest situation
because 60 is evenly divisible by 5 --- there are no remaining pennies
to worry about.) To find out how much money
must change hands, look at it from the perspective of all the students
who overpaid.  In this example, three people overpaid and require
reimbursements of $20-12$, $18-12$ and $16-12$, for a total of $8+6+4=18$.

For a second example, consider these costs:
$$20 \hspace{20pt} 18 \hspace{20pt} 16 \hspace{20pt} 5 \hspace{20pt}3$$
The total cost is now 62, giving an average of $62/5$ --- a quotient
of $12$ with remainder $2$. To equalize costs, three students will pay
$12$ and two students will pay $13$.  To minimize the amount of
money which changes hands, we will penalize two of students who are
already over the average, asking them to pay an extra penny.

Here's a slightly different way to think of it.  Let everyone pay
$\lfloor 62/5 \rfloor$, then distribute the extra cost (to the over-payers) from a
pool of $62 \bmod 5 = 2$ pennies. As in the first example, we can
account for the money that needs to trade hands from the perspective
of those who overpaid. As a first step, ignore the pool of extra
costs. The three people who overpaid would expect reimbursements of $20-12$, $18-12$,
and $16-12$.  We adjust this by considering the pool of 2 pennies,
asking two of the three to pay one penny more. The total reimbursement
is thus $8 + 6 + 5 - 1 - 1 =16$. (We will decrease the pool by one penny each time
we consider an over-payer; when the pool reaches 0, any remaining
over-payers will not be assessed the extra penny cost.) 

As a third example, suppose we have these costs:
$$62 \hspace{20pt} 0 \hspace{20pt} 0 \hspace{20pt} 0 \hspace{20pt}0$$
In this case, as before, we have an average of 12 with a pool of 2 cents.
The amount to redistribute is thus $(62 - 12) - 1 = 49$.  This example
shows that the pool is not necessarily reduced to 0 as a result of
considering all the over-payers. 

\subsection*{Coding Details}
As already mentioned, performing all arithmetic with integer values is
the easiest way of maintaining accuracy to the penny.  Although the
input values ``look like'' they should be read as floating point
values, we can consider them to be pairs of integers and use C's
\verb!scanf! format specifier to read a pair of integers from each
line of the input.  In the following snippet of code, all the
variables are of type \verb!int!.  

\lstset{language=c, 
        basicstyle=\small, 
        numberstyle=\tiny, 
        frame=none 
        }

\begin{lstlisting} 
    /* Collect and save the data for the current trip */
    for (i = 0; i < n; i++) {
      scanf("%d.%d", &d, &c);
      amt[i] = 100*d + c;
\end{lstlisting}

As an alternative, we could read the inputs as a floating
point type, representing dollars and cents, and then convert
to an integer type representing the number of cents. (For
example, $1.23$ would be converted to 123.) Due to possible
errors involved in storing floating point values, we need to
carefully round when the conversion to an integer type is
performed:

\lstset{language=c, 
        basicstyle=\small, 
        numberstyle=\tiny, 
        frame=none 
        }

\begin{lstlisting}
 
    double amtPaid;         /* amount one student paid */ 

    /* Collect and save the data for the current trip */
    for (i = 0; i < n; i++) {
      scanf("%lf", &amtPaid);
      amt[i] = 100*amtPaid + 0.5; /* number of cents paid by this student */
\end{lstlisting}

~\\
\vspace{10pt}
The complete program is shown on the following page.

\newpage
\vspace*{-0.5in}
\subsection*{Source Code}
\enlargethispage{0.4in}
% Set listing options...
\lstset{language=c, 
        basicstyle=\fontsize{8}{10}\selectfont, 
        numbers=left,
        numberstyle=\tiny, 
        frame=none, 
        %backgroundcolor=\color{yellow!10}
       }

\lstinputlisting{trip.c}
\end{document}
