\section{Задача A. <<Банк>>}

\begin{frame}[t]{Задача A. <<Банк>>}
  \begin{center}
    \LARGE Задача A. <<Банк>>
  \end{center}

  $$\includegraphics[width=8cm]{pics/bank.png}$$
\end{frame}

\begin{frame}[t]{}
  \vspace{3cm}
  \begin{itemize}
    \item Идея задачи --- Виталик Аксёнов
    \item Подготовка тестов --- Виталик Аксёнов
    \item Разбор задачи --- Виталик Аксёнов
  \end{itemize}
\end{frame}

\subsection{Постановка задачи}

\begin{frame}[t]{Постановка задачи}
Входные данные:
\begin{itemize}
	\item Сначала каждому гному нужно провести $a_i$ времени у одного из $m$ сотрудников.
	\item Известно, что гном приходит в банк во время $t_i$.
	\item После сотрудника гному нужно провести $b_i$ времени у главного бухгалтера.
	\item Есть 2 очереди~--- одна к сотрудникам и одна к бухгалтеру.
	\item Первый гном из первой очереди идёт к первому освободившемуся сотруднику.
\end{itemize}
Нужно для каждого гнома сказать, в какое время он выйдет из банка.
\end{frame}

\subsection{Решение}

\begin{frame}[t]{Первая очередь}
\begin{itemize}
	\uncover<1->%
	{%
	\item Первым делом узнаем для каждого гнома время, в которое он встанет во вторую очередь. \\
	}%
	\uncover<2->%
	{%
	\item Будем обрабатывать гномов последовательно, по времени прихода.
    \item Пусть сейчас обрабатываем гнома под номером $i$. \\
	}%
	\uncover<3->%
	{%
	\item Найдём того сотрудника, у которого пусто пустое или у которого находится гном, с минимальным временем
      перехода во вторую очередь. Пусть это время равно $t$. \\
	}%
	\uncover<4->%
	{%
    \item Отправим $i$-го гнома к выбранному сотруднику. А время его перехода во вторую очередь равно $t2_i = \max\{t_i, t\} + a_i$. \\
	}%
\end{itemize}
\end{frame}

\begin{frame}[t]{Вторая очередь}%
\begin{itemize}
    \uncover<1->{
    \item Отсортируем гномов по времени прихода во вторую очередь. Чтобы не потерять входные
      номера гномов нам нужно их отсортировать <<вместе>> с гномами.
    }
    \uncover<2->{
    \item Аналогично первой очереди обрабатываем гномов последовательно.
    \item Возьмём $i$-го гнома из очереди, а его номер будет равен $ind_i$.
    }
    \uncover<3->{
    \item $\begin{cases}
            ans_{ind_i} = \max\{ans_{ind_{i-1}}, t2_{ind_i}\} + b_{ind_i}, & i \geq 2\\
      ans_{ind_i} = t2_{ind_i} + b_{ind_i}, & i = 1
    \end{cases}
    $.
    }
\end{itemize}
\end{frame}

