\documentclass[a4paper]{article} \setlength{\textwidth}{19cm} \setlength{\textheight}{27cm} \setlength{\oddsidemargin}{-15mm} \setlength{\evensidemargin}{-17mm} \setlength{\topmargin}{-32mm} \setlength{\baselineskip}{3em} \usepackage[T2A]{fontenc} \usepackage[cp1251]{inputenc} \usepackage[russian]{babel} \usepackage{amssymb} \usepackage{amsmath} \usepackage{cmap} \renewcommand{\theenumi}{\Alph{enumi}} \newcommand{\comptask}{\stepcounter{enumi}\theenumi$^*$} \newcommand{\imptask}{\stepcounter{enumi}\theenumi$^\circ$} \makeatletter \def\verbsettings{\topsep=0pt\partopsep=0pt \parsep=2pt\parskip=0pt\parindent=0pt\@totalleftmargin=0pt \renewcommand{\baselinestretch}{0.8}\hsize=} \def\myAlpha#1{{\@tempcnta=\csname c@#1\endcsname\relax \advance\@tempcnta by -1\relax\@tempcntb=\@tempcnta\relax \divide\@tempcntb by 26\relax\multiply\@tempcntb by 26\relax \advance\@tempcnta by -\@tempcntb\relax\divide\@tempcntb by 26\relax \advance\@tempcnta by 65\relax \ifnum\@tempcntb>0\advance\@tempcntb by 64\relax\char\@tempcntb\fi \char\@tempcnta}} % macro dlya odno- i dvuznachnykh bukvennykh napisanij \def\@listi{} \def\@listI{} \itemsep=0pt \parskip=0pt \topsep=0pt \partopsep=0pt \parsep=0pt % ubivaem vse vertikalnye otstupy \def\theenumi{\myAlpha{enumi}} % enumi --- eto schyotchik pervogo urovnya enumerate % theenumi --- tak budet pechatat'sya znachenie schyotchika \def\labelenumi{\theenumi.} % tak dobavlyaetsya znak prepinaniya \makeatother \begin{document} \thispagestyle{empty} \Large \center\textbf{Массивы.} \bigskip \flushleft \normalsize \emph{Обозначения}: \parЭлементы массива --- целые числа, если не указано иное. \parПримеры ввода массива с клавиатуры и создания массива, заполненного случайными значениями, можно посмотреть в \texttt{python-book}. \parФраза \emph{"за один проход по массиву"} означает, что основной алгоритм должен быть записан при помощи цикла или циклов, суммарное количество итераций которых не больше, чем размер массива. \parСимволом $^{\circ}$ помечены ключевые задачи, они используются в более сложных алгоритмах, как вспомогательные. \parСимволом $^{*}$ помечены более сложные задачи.\par\textbf{Внимание!} Все задачи листочка требуется решить без применения к массивам и их срезам встроенных функций \texttt{max}, \texttt{min}, \texttt{find}, \texttt{count} и т.п., сложения списков и их срезов, а также без использования вспомогательных массивов, строк и иных структур данных (если только создание массива не требуется в условии задачи). \parИспользование \texttt{max}, \texttt{min}, \texttt{abs} и прочих функций, принимающих на вход скаляры (т.е. не списки), разрешается и поощряется. \parКроме того, изменять данный массив разрешается только в случае, если в условии задачи это указано явно (т.е. сказано, что разрешается его изменять или само изменение является целью задачи). \bigskip Считывать массив целых чисел, записанных в одну строку через пробел, можно так: \par\texttt{x = list(map(int, input().split()))} \bigskip \parВыводить массив целых чисел в одну строку через пробел можно так: \par\texttt{print(' '.join(map(str, x)))} \bigskip \large \begin{enumerate} \setlength{\itemsep}{7pt} \item\emph{Максимальный элемент и его номер} \parДан список чисел. Выведите значение наибольшего элемента в списке, а затем индекс этого элемента в списке. Если наибольших элементов несколько, выведите индекс первого из них. \parВ первой строке вводится натуральное число $N$, во второй --- $N$ целых чисел через пробел. \parПрограмма должна вывести два числа --- ответ на вопрос задачи. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\verbsettings3cm \begin{verbatim} 5 1 2 3 2 1 \end{verbatim} \vskip2pt } & \raise5pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt\makeatletter\@totalleftmargin=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 3 2 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item\emph{Поменять местами максимальный и минимальный элементы} \parВ массиве поменять местами минимальный и максимальный элементы. Если минимальных несколько, взять тот, который имеет наименьший индекс. Если максимальных несколько, взять тот, который имеет наибольший индекс. \parВ первой строке вводится натуральное число $N$, во второй --- $N$ целых чисел через пробел. \parПрограмма должна изменить массив в соответствии с условием задачи и вывести его. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\verbsettings3cm \begin{verbatim} 5 3 4 5 2 1 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 3 4 1 2 5 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item\emph{Линейный поиск} \parНапишите программу, которая выводит номера элементов массива, равных данному числу. \parВ первой строке задается одно натуральное число $N$, не превосходящее $1000$ --- размер массива. \parВо второй строке вводятся $N$ чисел --- элементы массива (целые числа, не превосходящие по модулю $1000$). \parВ третьей строке содержится одно целое число $x$, не превосходящее по модулю $1000$. \parВывести номера элементов, равных данному, в порядке возрастания в одну строку через пробел. Нумерация элементов начинается с единицы. Если таких элементов нет, ничего выводить не нужно. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 5 1 2 3 4 5 3 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 3 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \newpage \item\emph{Наименьший нечётный элемент} \parНайдите значение наименьшего нечётного элемента массива. Если в массиве нет нечётных элементов --- выведите число $0$. Решите задачу при помощи одного прохода по массиву. \parВ первой строке вводится натуральное число $N$, во второй --- $N$ целых чисел через пробел. \parПрограмма должна вывести единственное число --- ответ на вопрос задачи. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 5 0 1 2 3 4 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 1 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item\emph{Больше своих соседей} \parДан список чисел. Определите, сколько в этом списке элементов, которые больше двух своих соседей (т.е. таких элементов $x_i$, что $x_{i-1}x_{i+1}$) и выведите количество таких элементов. Первый и последний элементы не имеют обоих соседей, поэтому учитываться не должны. \parВ первой строке вводится натуральное число $N$, во второй --- $N$ целых чисел через пробел. \parПрограмма должна вывести единственное число --- ответ на вопрос задачи. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 5 1 2 3 4 -2 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 1 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item\emph{Переставить соседние} \parПереставьте соседние элементы массива (\texttt{A[0]} c \texttt{A[1]}, \texttt{A[2]} c \texttt{A[3]} и т.д.). Если элементов нечётное число, то последний элемент остается на своем месте. \parВ первой строке вводится натуральное число $N$, во второй --- $N$ целых чисел через пробел. \parПрограмма должна изменить массив в соответствии с условием задачи и вывести его. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 5 1 2 3 4 5 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 2 1 4 3 5 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item\emph{Наибольшая сумма двух соседних} \parНайдите наибольшее значение суммы двух соседних элементов в данном массиве. Можно считать, что в массиве есть не менее двух элементов. \parНа вход подаётся натуральное число $N (2\leqslant N\leqslant10^5)$. Затем на вход подаётся строка, в которой через пробел записаны $N$ целых чисел. Каждое число не превосходит по модулю $10^9$. \parПрограмма должна вывести единственное число --- ответ на вопрос задачи. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 5 1 2 6 -5 4 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 8 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item\emph{Арифметическая прогрессия} \parВыяснить --- являются ли целочисленные элементы данного массива элементами какой-то арифметической прогрессии, идущими подряд? Если да, вывести разность этой арифметической прогрессии, иначе вывести слово \texttt{NO}. Можно считать, что массив содержит не менее двух чисел. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 5 1 3 5 7 9 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 2 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \\ \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 5 1 2 3 4 6 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} NO \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item\emph{Ближайшее число} \parНапишите программу, которая находит в массиве элемент, самый близкий по величине к данному числу. \parЕсли таких чисел несколько --- выведите любое. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 5 1 2 3 4 5 6 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 5 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \newpage \item\emph{Сколько различных элементов в упорядоченном массиве} \parДан массив, упорядоченный по неубыванию элементов в нём. Определите, сколько в нём различных элементов. Размер массива не превышает $10^5$. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 6 1 2 2 3 3 3 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 3 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item\emph{Максимальный элемент и их количество} \parНайдите за один проход по массиву наибольшее значение в этом массиве и количество элементов, имеющих такое значение. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=4cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 7 8 7 7 5 5 8 5 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 8 2 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item\emph{Циклический сдвиг вправо} \parЦиклически сдвиньте элементы списка вправо (\texttt{A[0]} переходит на место \texttt{A[1]}, \texttt{A[1]} на место \texttt{A[2]}, $\dots$, последний элемент \texttt{A[N - 1]} переходит на место \texttt{A[0])}. \parПостарайтесь обойтись $N+1$ оператором присваивания (присваивание вида \texttt{a,b=b,a} считается за два). \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 5 1 2 3 4 5 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 5 1 2 3 4 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item\emph{Заменить на полусумму соседей} \parЗамените все элементы массива, кроме первого и последнего на полусумму его соседних элементов (соседа слева и соседа справа). \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 5 3 5 2 1 7 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=4cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 3 2.5 3.0 4.5 7 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item[\imptask]\emph{Нули --- в конец} \parНапишите программу, которая выполняет "<сжатие массива"> --- переставляет все нулевые элементы в конец массива. При этом все ненулевые элементы располагаются в начале массива в том же порядке. \parВ первой строке вводится натуральное число $N\leqslant10^5$, во второй --- $N$ целых чисел через пробел. \parПрограмма должна \emph{сначала} изменить массив в соответствии с условием задачи и вывести его. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 6 1 0 2 0 3 4 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 1 2 3 4 0 0 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item\emph{Пары равных элементов} \parДан массив чисел. Посчитайте, сколько в нем пар элементов, равных друг другу. Считается, что любые два элемента, равные друг другу, образуют одну пару, которую необходимо посчитать. \parИзменять массив нельзя, размер массива не превосходит $100$. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 5 1 2 3 2 3 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 2 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item\emph{Самое частое число} \parДан массив. Не изменяя его и не используя дополнительные массивы, определите, какое число в этом списке встречается чаще всего. \parЕсли таких чисел несколько, выведите любое из них. \parРазмер массива не превосходит $10^3$. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 6 1 2 3 2 3 3 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 3 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \newpage \item\emph{Сколько различных элементов (общий случай)} \parДан массив. Посчитайте, сколько в нём различных элементов, не изменяя самого массива и не используя вспомогательные массивы. \parКоличество $N$ элементов в массиве не превосходит $10^5$ и в общем случае (с учётом ограничений в задаче) любое решение будет работать долго: количество операций пропорционально $N^2$. Тем не менее тесты составлены таким образом, чтобы рациональное решение проходило по времени. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 5 3 2 1 2 3 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 3 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item\emph{Уникальные элементы} \parДан целочисленный массив. Выведите те его элементы, которые встречаются в массиве только один раз. Элементы нужно выводить в том порядке, в котором они встречаются в массиве. \parКоличество $N$ элементов в массиве не превосходит $10^5$ и в общем случае (с учётом ограничений в задаче) любое решение будет работать долго: количество операций пропорционально $N^2$. Тем не менее тесты составлены таким образом, чтобы рациональное решение проходило по времени. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 6 1 2 2 3 3 3 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 1 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item\emph{Медиана} \parВ массиве --- нечётное число элементов, при этом все элементы различны. \parНайдите медиану списка: элемент, который стоял бы ровно посередине списка, если список отсортировать. \parПри решении этой задачи нельзя модифицировать данный список (в том числе и сортировать его), использовать вспомогательные списки. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3.5cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 7 6 1 9 2 3 4 8 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 4 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item[\imptask]\emph{Строительство школы} \parВ деревне все дома расположены вдоль одной улицы по одну сторону от неё. По другую сторону от этой улицы пока ничего нет, но скоро все будет --- школы, магазины, кинотеатры и т.д. \parДля начала в этой деревне решили построить школу. Место для строительства школы решили выбрать так, чтобы суммарное расстояние, которое проезжают ученики от своих домов до школы, было минимально. \parПлан деревни можно представить в виде прямой, в некоторых целочисленных точках которой находятся дома учеников. Школу также разрешается строить только в целочисленной точке этой прямой (в том числе разрешается строить школу в точке, где расположен один из домов --- ведь школа будет расположена с другой стороны улицы). \parНапишите программу, которая по известным координатам домов учеников поможет определить координаты места строительства школы. \parСначала а вход программе подаётся натуральное число $N$ --- число домов, в следующей строке записаны $N$ целых чисел --- координаты домов в порядке \emph{возрастания}. \parПрограмма должна вывести целое число --- координату школы, суммарное расстояние от которой до всех домов наименьшее. Если таких координат несколько --- выведите любую. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 4 10 20 30 40 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 30 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \newpage \item[\imptask]\emph{Является ли массив подпоследовательностью другого} \parДаны два массива. Определить, является ли второй массив подпоследовательностью первого. Выведите \texttt{YES}, если вторая последовательность является подпоследовательностью первой, иначе выведите \texttt{NO}. \parСуммарное количество операций должно быть пропорционально сумме длин массивов, а не их произведению. \parНа вход подаётся натуральное число $N (1\leqslant N\leqslant3\cdot10^5)$. Затем на вход подаётся строка, в которой через пробел записаны $N$ целых чисел. Каждое число не превосходит по модулю $10^9$. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 3 1 2 3 2 1 3 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} YES \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item[\imptask]\emph{Все простые в диапазоне} \parДаны два числа $M$ и $N$, $2 \leqslant M \leqslant N \leqslant 10^6$. \parВывести все простые числа от $M$ до $N$ включительно. \parЕсли в указанном диапазоне простых чисел нет --- вывести число $-1$. \parДля решения задачи надо получить массив логических переменных \texttt{primes}, такой, что \texttt{primes[k] = True} т и т.т., когда $k$ --- простое число. Сперва все значения равны \texttt{True}, затем при помощи решета Эратосфена изменить этот массив, чтобы он соответствовал его определению. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 2 5 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 2 3 5 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item[\imptask]\emph{Разворот части массива} \parПереставьте в обратном порядке элементы массива, находящиеся между указанными индексами (включая и элементы с указанными индексами). \parРешение следует оформить в виде функции с тремя параметрами: массив, левая граница и правая граница. Фунция должна изменять переданный массив в соответствии с условием. \parНа вход подаётся три строки: в первой размер массив $N$, во второй $N$ целых чисел через пробел, в третьей два числа, разделённые пробелом: индексы левой и правой границ, соответственно. \bigskip \parДля чтения нескольких целочисленных переменных, записанных в одной строке через пробел можно пользоваться следующей конструкцией: \par\texttt{a, b = map(int, input().split())} \bigskip \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=5cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 10 0 5 2 4 9 -1 3 9 7 8 3 7 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=5cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 0 5 2 9 3 -1 9 4 7 8 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item\emph{Разворот чётного подмассива} \parВ данном массиве обратить подмассив чётных чисел. Время работы должно быть пропорционально длине массива. \parНа вход подаётся натуральное число $N (1\leqslant N\leqslant10^5)$. Затем на вход подаётся строка, в которой через пробел записаны $N$ целых чисел. Каждое число не превосходит по модулю $10^9$. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=5cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 10 6 10 3 6 3 8 2 3 7 3 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=5cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 2 8 3 6 3 10 6 3 7 3 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \newpage \item[\comptask]\emph{Большой сдвиг} \parДан список из $N~(1\leqslant N\leqslant10^5)$ целых чисел и число $K~(|K|\leqslant10^5)$. Циклически сдвиньте список на $|K|$ элементов вправо, если $K$ положительное и влево, если отрицательное число. \parРешение должно иметь сложность $O(N)$. В частности, время работы алгоритма не должно зависеть от $K$. Количество вспомогательной памяти $O(1)$. \parВ этой задаче полезно ``подвигать'' элементы при циклических сдвигах на 2, 3, 4, 5, 6 в массиве из 12 элементов. Это может навести вас на соответствующий математический факт и алгоритм. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 5 5 3 7 4 6 3 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 7 4 6 5 3 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \item\emph{Минимальное число, непредставимое в виде суммы} \parДан упорядоченный по неубыванию массив натуральных чисел. Найти минимальное натуральное число, не представимое в виде суммы нескольких элементов списка. Каждый элемент списка может быть взят не более одного раза. Список содержит не более $10^5$ элементов. \parПридумайте очевидный инвариант для цикла и решение появится само собой. \normalsize \begin{tabular}{|c|c|} \hline Input & Output\\ \hline \raise5pt\vtop{\hsize=3cm\topsep=0pt\partopsep=0pt\parsep=2pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 5 1 1 2 5 15 \end{verbatim} \vskip2pt } & \raise6pt\vtop{\hsize=2cm\topsep=0pt\partopsep=0pt\parsep=0pt\parskip=0pt\parindent=0pt \renewcommand{\baselinestretch}{0.8} \begin{verbatim} 10 \end{verbatim} \vskip2pt }\\ \hline \end{tabular} \large \end{enumerate} \newpage %\large\textbf{Задачи на использование встроенных функций работы со строками и массивами.} % %\begin{enumerate} %\setlength{\itemsep}{-2pt} %\setcounter{enumi}{22} % \item{Вывести количество слов в строке, содержащей только латинские буквы и пробелы.} % \item{Дана строка, содержащая предложения, заканчивающиеся точкой. Каждое предложение состоит из слов, содержащих только латинские буквы. %\parВывести строку, содержащую исходные предложения без лишних пробелов. При этом все слова, кроме тех, с которых начинаются предложения, должны быть записаны только строчными буквами. Первое слово каждого предложения должно начинаться с заглавной буквы, остальные буквы --- строчные.} % \item{Задача 5 листочка по строкам (IP-адрес)} % \item{Задача 7 листочка по строкам (слова из данной строки, записанные в обратном порядке)} % \item{Дана строка. Вывести подстроку, заключённую между первым и последним символами \texttt{\#}.} %\end{enumerate} \end{document}