\documentclass[12pt]{extreport}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}        % Кодировка входного документа;
                                    % при необходимости, вместо cp1251
                                    % можно указать cp866 (Alt-кодировка
                                    % DOS) или koi8-r.

\usepackage[english,russian]{babel} % Включение русификации, русских и
                                    % английских стилей и переносов
%%\usepackage{a4}
%%\usepackage{moreverb}
\usepackage{amsmath,amsfonts,amsthm,amssymb,amsbsy,amstext,amscd,amsxtra,multicol}
\usepackage{indentfirst}
\usepackage{verbatim}
\usepackage{tikz} %Рисование автоматов
\usetikzlibrary{automata,positioning}
\usepackage{multicol} %Несколько колонок
\usepackage{graphicx}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[stable]{footmisc}

\usepackage[linesnumbered]{algorithm2e}   

%% \voffset-5mm
%% \def\baselinestretch{1.44}
\renewcommand{\theequation}{\arabic{equation}}
\def\hm#1{#1\nobreak\discretionary{}{\hbox{$#1$}}{}}
\newtheorem{Lemma}{Лемма}
\theoremstyle{definiton}
\newtheorem{Remark}{Замечание}
%%\newtheorem{Def}{Определение}
\newtheorem{Claim}{Утверждение}
\newtheorem{Cor}{Следствие}
\newtheorem{Theorem}{Теорема}
\theoremstyle{definition}
\newtheorem{Example}{Пример}
\newtheorem*{known}{Теорема}
\def\proofname{Доказательство}
\theoremstyle{definition}
\newtheorem{Def}{Определение}

%% \newenvironment{Example} % имя окружения
%% {\par\noindent{\bf Пример.}} % команды для \begin
%% {\hfill$\scriptstyle\qed$} % команды для \end






%\date{22 июня 2011 г.}
\let\leq\leqslant
\let\geq\geqslant
\def\MT{\mathrm{MT}}
%Обозначения ``ажуром''
\def\BB{\mathbb B}
\def\CC{\mathbb C}
\def\RR{\mathbb R}
\def\SS{\mathbb S}
\def\ZZ{\mathbb Z}
\def\NN{\mathbb N}
\def\FF{\mathbb F}
%греческие буквы
\let\epsilon\varepsilon
\let\es\varnothing
\let\eps\varepsilon
\let\al\alpha
\let\sg\sigma
\let\ga\gamma
\let\ph\varphi
\let\om\omega
\let\ld\lambda
\let\Ld\Lambda
\let\vk\varkappa
\let\Om\Omega
\def\abstractname{}

\def\R{{\cal R}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\D{{\cal D}}

%классы сложности
\def\REG{{\mathsf{REG}}}
\def\CFL{{\mathsf{CFL}}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Problems macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%% Enumerations %%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\Rnum}[1]{\expandafter{\romannumeral #1\relax}}
\newcommand{\RNum}[1]{\uppercase\expandafter{\romannumeral #1\relax}}

%%%%%%%%%%%%%%%%%%%%% EOF Enumerations %%%%%%%%%%%%%%%%%%%%%

\usepackage{xparse}
\usepackage{ifthen}
\usepackage{bm} %%% bf in math mode
\usepackage{color}
%\usepackage[usenames,dvipsnames]{xcolor}

\definecolor{Gray555}{HTML}{555555}
\definecolor{Gray444}{HTML}{444444}
\definecolor{Gray333}{HTML}{333333}


\newcounter{problem}
\newcounter{uproblem}
\newcounter{subproblem}
\newcounter{subrproblem}
\newcounter{prvar}


\def\pr{\medskip\noindent\stepcounter{problem}{\bf \theproblem .\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}
\def\pru{\medskip\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^\circ$\!\!.\;}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}}
\def\prstar{\medskip\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^*$\negthickspace.}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}\;}
\def\prpfrom[#1]{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem~(№#1 из задания).  }\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }
\def\prp{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem .  }\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }

\def\prpvar{\medskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem \;$\langle${\rm\Rnum{\theprvar}}$\rangle$.}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}\;}
\def\prpv{\medskip\noindent\stepcounter{prvar}{\bf Задача \theproblem \,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$.  }\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }
\def\prv{\medskip\noindent\stepcounter{prvar}{\bf \theproblem\,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}.\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }

\def\prpstar{\medskip\noindent\stepcounter{problem}{\bf Задача $\bf\theproblem^*$\negthickspace.  }\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }
\def\prdag{\medskip\noindent\stepcounter{problem}{\bf Задача $\theproblem^{^\dagger}$\negthickspace\,.  }\setcounter{subproblem}{0}\setcounter{subrproblem}{0} }
\def\upr{\medskip\noindent\stepcounter{uproblem}{\bf Упражнение \theuproblem .}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}\;}
%\def\prp{\vspace{5pt}\stepcounter{problem}{\bf Задача \theproblem .  } }
%\def\prs{\vspace{5pt}\stepcounter{problem}{\bf \theproblem .*   }
\def\prsub{\medskip\noindent\stepcounter{subproblem}\setcounter{subrproblem}{0}{\sf \thesubproblem .}\;}
\def\prsubr{\medskip\noindent\stepcounter{subrproblem}{\bf \asbuk{subrproblem})}\;}
\def\prsubstar{\medskip\noindent\stepcounter{subproblem}{\rm $\thesubproblem^*$\negthickspace.}\;}
\def\prsubrstar{\medskip\noindent\stepcounter{subrproblem}{$\text{\bf \asbuk{subrproblem}}^*\text{\textbf{)}}\mathbf{}$}\;}

\newcommand{\bracketspace}[1]{\phantom{(}\!\!{#1}\!\!\phantom{)}}

\DeclareDocumentCommand{\Prpvar}{ O{null} O{} }{
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem
% 	\ifthenelse{\equal{#1}{null}}{  }{ {\sf $\bm\langle$\bracketspace{#1}$\bm\rangle$}}
%	~\!\!(\bracketspace{{\rm\Rnum{\theprvar}}}).  }\setcounter{subproblem}{0}\setcounter{subrproblem}{0}
%	\;(\bracketspace{{\rm\Rnum{\theprvar}}})}\setcounter{subproblem}{0}\setcounter{subrproblem}{0}
%
	\,{\sf $\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}}.

}
%\DeclareDocumentCommand{\Prpvar}{ O{level} O{meta} m }{\prpvar}


\DeclareDocumentCommand{\Prp}{ O{null} O{null} }{\setcounter{subproblem}{0}\setcounter{subrproblem}{0}
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача \theproblem
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.}

\DeclareDocumentCommand{\Pr}{ O{null} O{null} }{\setcounter{subproblem}{0}\setcounter{subrproblem}{0}
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf\theproblem
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.}


\DeclareDocumentCommand{\Prstar}{ O{null} O{null} }{\setcounter{subproblem}{0}\setcounter{subrproblem}{0}
		\medskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf$\mathbf{\theproblem^*}$
		~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
		 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.}

%\DeclareDocumentCommand{\Prp}{ O{level} O{meta} }

\DeclareDocumentCommand{\Prps}{ O{null} O{null} }{\setcounter{subproblem}{0}\setcounter{subrproblem}{0}
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача $\bm\theproblem^* $
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}

\DeclareDocumentCommand{\Prpd}{ O{null} O{null} }{\setcounter{subproblem}{0}\setcounter{subrproblem}{0}
	\medskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача $\bm\theproblem^\dagger$
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}


\def\prend{
	\bigskip
%	\bigskip
}


\def\prskip{
	\medskip
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% EOF Problems macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




%\usepackage{erewhon}
%\usepackage{heuristica}
%\usepackage{gentium}

\usepackage[portrait, top=3cm, bottom=1.5cm, left=3cm, right=2cm]{geometry}

\usepackage{fancyhdr}
\pagestyle{fancy}
\renewcommand{\headrulewidth}{0pt}
\lhead{\fontfamily{fca}\selectfont {Основные алгоритмы 2019} }
%\lhead{ \bf  {ТРЯП. } Семинар 1 }
%\chead{\fontfamily{fca}\selectfont {Вариант 1}}
\rhead{\fontfamily{fca}\selectfont Домашнее задание 13}
%\rhead{\small 01.09.2016}
\cfoot{}

\usepackage{titlesec}
\titleformat{\section}[block]{\Large\bfseries\filcenter {\setcounter{problem}{0}}  }{}{1em}{}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Обозначения и операции %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
                                                                    
\newcommand{\divisible}{\mathop{\raisebox{-2pt}{\vdots}}}           
\let\Om\Omega


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Shen Macroses %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\w}[1]{{\hbox{\texttt{#1}}}}
\usepackage{wrapfig}
\def\bin{\mathrm{bin}}



\begin{document}	
\pr На вход задачи подаётся число $n$ и последовательность целых чисел $a_1, \ldots, a_n$. Необходимо найти номера $i$ и $j$ ($1\leq i<j\leq n$), такие что сумма $\sum\limits_{k=i}^ja_k$ максимална. 

\prsub Постройте линейный алгоритм, решающий задачу. 

\prsub Постройте онлайн-алгоритм (достаточно выполнить только этот пункт).



\pr Фирма производит программное обеспечение для банкоматов разных стран мира. Иногда, купюры какого-то вида заканчиваются и банкомату нужно определить, возможно ли выдать клиенту требуемую сумму. Вход задачи: число $n$, номиналы купюр $v_1,\ldots v_n$ и сумма клиента $s$.

\prsub  Постройте алгоритм, решающий задачу за $O(ns)$.

\prsubstar Постройте алгоритм, решающий задачу за $O(na\log a)$, где $a = \min a_i$.



\pr Рассмотренный нами алгоритм вычисления расстояния редактирования строк длины $m$ и $n$ заполняет таблицу размера $O(mn)$. При больших $m$ и $n$ такому алгоритму просто не хватит памяти. Как можно обойтись меньшим объёмом памяти? 

\prsub Допустим, что нас интересует только расстояние редактирования, но не соответсвующее оптимальное выравнивание. Покажите, что тогда в каждый момент не нужно хранить всю таблицу и можно обойтись объёмом памяти $O(n)$.

\prsub Теперь допустим, что мы хотим найти и оптимальное выравнивание. Легко видеть, что это эквивалентно поиску кратчайшего пути из вершины $(0,0)$ в вершину $(n,m)$ в соответсвующем графе: вершины графа "--- клетки таблицы, а стоимость ребра "--- $1$ или $0$, в зависимости от конкретного перехода. Любой такой путь должен проходить через вершину $(k, m/2)$ для некоторого $k$. Модифицируйте алгоритм поиска расстояния редактирования, чтобы он заодно выдавал и $k$. Считайте, что $m$ "--- степень двойки.

\prsubstar Рассмотрим теперь следующий рекурсивный алгоритм.
 
\begin{figure}[h]


\begin{algorithm}[H]%algorithm2e
	\SetKwFunction{KwPrint}{print}
%	\SetKwFunction{KwFn}{Fn}
	\SetKwInOut{Input}{Вход}\SetKwInOut{Output}{Выход}
	\SetKwProg{Fn}{Function}{ :}{end}

	\SetKwFunction{FindPath}{FindPath}
%	\Multiply($x,y$){ %\tcc*[h]{Рекурсивный алгоритм умножения ([\textbf{ДПВ}] раздел 1.1.2)}
\Fn{\FindPath{$(0,0)\to (n,m)$}}{ %\tcc*[h]{}

	Вычислить $k$ (cм. предыдущий пункт)\;
  
	\FindPath{$(0,0)\to (k,m/2)$}\;
	\FindPath{$(k,m/2)\to (n,m)$}\;
	
	\KwRet{объединение найденных двух путей}
}	
	
\end{algorithm}
\end{figure}

Покажите, что по данной схеме алгоритм можно реализовать так, чтобы время его работы было $O(nm)$, а память "--- $O(n)$.

\prend

\Pr[null][Шень 2.1.1.] Постройте алгоритм, который, получив на вход числа $n$ и $k$, выводит все последовательности длины $k$ целых чисел от $1$ до $n$.

\prend

\pr В одном языке программирования операция разрезания строки на две части реализовано через копирование. Разрезать строку $w=uv$ на две части $u$ и $v$ будет стоить длину строки $O(|w|)$, где $|w|$ "--- длина строки $w$, вне зависимости от длин строк $u$ и $v$. Постройте алгоритм, который получив на вход строку $w=u_1u_2\ldots u_k$ и номера позиций $i_1 = |u_1|, i_2 = |u|_1+ |u_2|, \ldots, i_k = |u_1| +\ldots + |u_k|$ строит последовательность разрезов строки $w$, которая приводит к разрезанию $w$ на подстроки $u_1, \ldots, u_k$ и использует для этого минимальное число операций.

Заметьте, что в зависимости от порядка разрезов меняется общее число операций: если строку длины $20$ нужно разрезать на строки с номерами позиций $3$, $10$, то отрезав сначала строку в позиции $3$ будет затрачено $20+17=37$ операций, а отрезав сначала строку в позиции $10$, будет потрачено $20+10=30$ операций.

\prend                                                                                                                              

\pr Алиса и Боб играют в следующую игру. Есть $n$ карт, на $i$-й карте записано число $1 \leq a_i \leq n$ (числа могут повторяться!).

Игроки ходят по очереди, первой ходит Алиса. На каждом ходу игрок выбирает карту и выбрасывает её. Кроме того, он выбрасывает все карты, на которых число меньше, чем на выбранной. Формально, если игрок выбирает карту с номером $i$, он выбрасывает эту карту, а также каждую карту с номером $j$, такую что $a_j < a_i$.

Игрок проигрывает, если он не может сделать ход, то есть если не осталось карт. 

\prsub Постройте алгоритм, который определяет победителя, если игроки играют оптимально.

\prsub Постройте жадный алгоритм, решающий эту задачу.

\prend


\Pr[null][Шень 8.1.4] Дан выпуклый $n$-угольник (заданный координатами своих
вершин в~порядке обхода). Его разрезают на треугольники
диагоналями, для чего необходимо $n-2$ диагонали (это можно
доказать индукци\-ей по~$n$). Стоимостью разрезания назовём
сумму длин всех использованных диагоналей. Постройте полиномиальный алгоритм, который находит
минимальную стоимость разрезания. (Пере\-бор не
подходит, так как число вариантов не ограничено
многочленом.)


\end{document}
  