\documentclass[10pt,a4paper]{article} \usepackage{fancyhdr} \renewcommand{\headrulewidth}{0pt} \renewcommand{\footrulewidth}{0pt} \fancyhead{} \fancyfoot[C]{Copyright {\textcopyright} 2015 Camil Staps} \pagestyle{fancy} \usepackage{enumitem} \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsthm} \usepackage{amsfonts} \DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n} \usepackage[hidelinks]{hyperref} \usepackage{url} \newcommand*\PM{\pazocal M} \newcommand*\PP{\pazocal P} \newcommand*\PR{\pazocal R} \newcommand*\round[1]{\lfloor #1\rceil} \newcommand*\seq[1]{\left\langle #1\right\rangle} \providecommand*{\lemmaautorefname}{Lemma} \newtheorem{lemma}{Lemma} \newtheorem{theorem}{Theorem} \numberwithin{lemma}{section} \numberwithin{theorem}{section} \newenvironment{thmproof}[3][]{% \begin{samepage} \begin{#2}% \def\templabel{#1}% \def\tempname{#2}% \def\temptheorem{theorem}% \ifx\templabel\empty\else\ifx\tempname\temptheorem\label{thm:#1}\else\label{lem:#1}\fi\fi% #3% \end{#2}% \begin{proof}% }{\end{proof}\end{samepage}} \newcommand{\refeq}[2][]{\begin{equation}\label{eq:#1}#2\end{equation}} \usepackage{algorithm} \usepackage{algorithmic} \providecommand*{\algorithmautorefname}{Algorithm} \renewcommand*{\sectionautorefname}{Section} \renewcommand*{\subsectionautorefname}{subsection} \renewcommand*{\subsubsectionautorefname}{subsection} \usepackage{minted} \title{Maximising the Rounding Advantage of a Division of a List Into Sublists} \author{Camil Staps} \begin{document} \maketitle \thispagestyle{fancy} \begin{abstract} Given a list of $n$ numbers $a_0, a_1, \dots, a_{n-1}$, we consider one of its partitions in $k+1$ (possibly empty) pairwise disjoint substrings such that the sum of the sums of the substrings, rounded to multiples of $5$, is minimal. This paper describes an algorithm to find the minimal sum for such a partition. It can easily be extended to find such a partition as well. \end{abstract} \section{Report organisation} \autoref{sec:notation} will define the notation used throughout this report. In \autoref{sec:algorithm} I will describe the algorithm and argue its correctness. When we have seen the algorithm, \autoref{sec:implementation} will go into details about its implementation in C. \autoref{sec:analysis} will contain a complexity analysis, both time- and space-wise, of the algorithm and its C implementation. We finish in \autoref{sec:future-work} with a discussion about possible future work. \input{notation} \input{algorithm} \input{implementation} \input{analysis} \input{future-work} \end{document}