swaddling5212 14 мая 2020 в 18:11

Полный разбор первой части экзамена в ШАД 2020

9 мин

18K

Алгоритмы*Занимательные задачкиМатематика*

Привет! С вами Азат Калмыков, куратор в «ШАД Helper». Мы продолжаем наш цикл статей, в которых разбираем задачи для поступления в ШАД. На этот раз мы (я, Николай Проскурин и Александр Курилкин) посмотрим на решения первого этапа отбора в ШАД в этом году, который закончился совсем недавно. Итак, приступим.

A. Локальный минимум

При каких значениях параметра a первообразная функции $f(x)=\left(x^{4}-(a+1) x^{3}+(a-2) x^{2}+2 a x\right) \exp ^{\frac{\sin x^{2}+2}{5 x^{2}+2}}$ имеет не более одного локального минимума?

Решение

Заметим, что производная от первообразной — это исходная функция. Значит, нам нужно исследовать на смену знака нашу исходную функцию. Конкретно, надо понять, сколько раз функция меняет знак с минуса на плюс (то есть посчитать количество точек локального минимума).

Заметим, что экспонента всегда положительна, не влияет на знак, поэтому её можно откинуть и считать, что $inline$ . Многочлен легко раскладывается на множители, потому что все его корни можно угадать: это $inline$ . Значит, $inline$ .

Если многочлен имеет четыре различных корня, то он меняет знак в порядке $+ \to - \to + \to - \to +$ , и потому имеет хотя бы два локальных минимума. Значит, нам могут подойти только $inline$ . Прямая проверка показывает, что все они являются ответами.

B. Предел

Определите, при каком значении $inline$ данный предел равен $\frac{1}{e}$ :

$\lim _{x \rightarrow +\inf }\left(\cos \sqrt{\frac{1}{x}}\right)^{\frac{x}{a}}$

Решение

Сначала посчитаем предел, приняв $inline$ . Поскольку $\sqrt{\frac{1}{x}} \to 0$ , мы можем разложить функцию в ряд Тейлора в нуле:

$\cos{\sqrt{\frac{1}{x}}} = 1 - \frac{1}{2!x} + \frac{1}{4!x^2} - \frac{1}{6!x^3} + \ldots$

Ограничим ряд сверху и снизу и воспользуемся теоремой о двух милиционерах. Заметим, что сумма больше первых двух слагаемых, так как группируя последующие слагаемые по два, мы получим бесконечное число положительных чисел, которые мы откидываем. Аналогично, сверху сумму можно оценить суммой первых трёх слагаемых. Значит:

$1 - \frac{1}{2x} < \cos{\sqrt{\frac{1}{x}}} < 1 - \frac{1}{2x} + \frac{1}{24x^2}$

Поскольку $x \to +\infty$ , от возведения в степень $inline$ неравенство сохранится, а при переходе к пределу изменится только строгость знаков. Левую часть можно посчитать сразу как следствие из второго замечательного предела, она равна $e^{-1/2}$ . Покажем, что правая равна тому же:

$\lim_{x \to +\infty} \left( 1 - \frac{1}{2x} + \frac{1}{24x^2} \right)^x = \exp\left(\lim_{x \to +\infty} x \ln\left( 1 - \frac{1}{2x} + \frac{1}{24x^2} \right)\right) =$

$= \exp\left(\lim_{x \to +0} \frac{\ln\left( 1 - \frac{x}{2} + \frac{x^2}{24} \right)}{x}\right)$

Применяя правило Лопиталя, получаем требуемое. Значит:

$\lim_{x \to +\infty} \left(\cos{\sqrt{\frac{1}{x}}}\right)^x = e^{-1/2} \Rightarrow \lim_{x \to +\infty} \left(\cos{\sqrt{\frac{1}{x}}}\right)^{x/a} = e^{-1/2a}$

Откуда $a = \frac{1}{2}$ .

Примечание: зная, что степенной ряд можно бесконечно дифференцировать в области сходимости, можно было пропустить шаг с оценкой ряда и сразу применить Лопиталя.

C. Локальный минимум

При какой минимальной длине шага градиентный спуск не сможет найти минимум функции $x^4+\cos 2$ , если $inline$ ?

Решение

Вспомним, что шаг градиентного спуска при константной длине шага считатеся следующим образом:

$x_k+1 = x_k - \lambda \triangledown f(x_k)$

.

В нашем случае градиент — это обычная одномерная производная, так что наша задача проще градиентного спуска в общем случае.

$\triangledown f(x_k) = 4x_k^3$

$inline$ нам известно, давайте посчитаем $inline$ :

$x_1 = x_0 - \lambda 4x_0^3 = 1 - 4\lambda$

Давайте заметим что, при $inline$ значение градиента будет таким же по модулю, как в точке $inline$ , но иметь обратный знак. Таким образом, можно понять, что при таком варианте градиентный спуск будет «скакать» туда-сюда из точки $inline$ в $inline$ и обратно. Таким образом, можно понять, что при $x_1=-1 \Leftrightarrow \lambda=0.5$ градиентный спуск уже не найдёт точку минимума (это точка $inline$ ). Но надо показать, что при меньших $\lambda$ она будет найдена.

Это можно понять и интуитивно, но давайте попробуем доказать строго. Можно доказать что $|x_{n+1}| \leq |x_n||1-4\lambda|$ по индукции. Здесь нам важно, что $0.5 > \lambda > 0 \Rightarrow |1 - 4\lambda| < 1$

База: $|x_1| = |1 - 4\lambda| \leq 1 |1 - 4\lambda| = x_0 |1-4\lambda|$

Переход. $|x_{n+1}| = |x_n - 4\lambda x_n^3| = |x_n| |1-4\lambda x_n^2|$ . За счёт предположения индукции можем получить что $x_n < 1 \Rightarrow x_n^2 < 1$ . Тогда $|x_{n+1}| \leq |x_n||1-4\lambda|$ . Всё доказано.

Пользуясь доказанным, можно получить, что $|x_n|\leq |x_0||1-4\lambda|^n = |1-4\lambda|^n$ . Так как знаем, что $|1-4\lambda| < 1$ , то получим что $inline$ сходится к нулю. Значит градиент находит минимум.

D. Собственный вектор

Определите, при каких значениях параметра a вектор $\left(\begin{array}{l} 1 \\ 1 \\ a \end{array}\right)$ является собственным вектором матрицы

$\left(\begin{array}{ccc} a & 1 & -1 \\ 1 & 2 & -1 \\ 0 & 0 & 1 \end{array}\right)$

Решение

По определению, вектор $v \neq 0$ является собственным для матрицы $inline$ , если $\exists \lambda$ : $Av = \lambda v$ . Получаем уравнение:

$\begin{pmatrix} a & 1 & -1 \\ 1 & 2 & -1\\ 0 & 0 & 1\\ \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ a \\ \end{pmatrix} = \begin{pmatrix} 1 \\ 3 - a \\ a \\ \end{pmatrix} = \lambda \begin{pmatrix} 1 \\ 1 \\ a \\ \end{pmatrix}$

По первой координате получаем. что $\lambda = 1$ , по второй — что $inline$ , проверяем, что третья координата согласуется с ответом. Значит, $inline$ .

E. Определитель

При каких значениях параметра $inline$ максимален определитель матрицы, обратной к этой?

$\left(\begin{array}{ccc} a & -7 & -3 \\ 6 & -10 & -a^{2} \\ 0 & a & 9 \end{array}\right)$

Решение

Посчитаем определитель исходной матрицы:

$\det(a) = \begin{vmatrix} a & -7 & -3 \\ 6 & -10 & -a^2 \\ 0 & a & 9 \\ \end{vmatrix} = a \begin{vmatrix} -10 & -a^2 \\ a & 9 \\ \end{vmatrix} - 6 \begin{vmatrix} -7& -3 \\ a & 9 \\ \end{vmatrix} = a^4 - 108a + 376$

$\det'(a) = 4a^3 - 108 = 0 \Leftrightarrow a = 3$

Несложно понять, что производная строго возрастает, значит, точка, в которой производная обнуляется, это точка минимума функции $\det(a)$ , откуда $\det(a) \geq \det(3) > 0$ и минимум достигается в точности в $inline$ . Тогда, пользуясь формулой $\det(A^{-1}) = \det(A)^{-1}$ , получаем, что максимум определителя обратной матрицы достигается в $inline$ .

F. Проекции

Даны точки $inline$ и $inline$ , а также плоскости $\alpha$ : $inline$ и $inline$ : $inline$ . Найдите координаты точки $inline$ , если известно, что её ортогональная проекция на $\alpha$ совпадает с проекцией точки $inline$ , а на $\beta$ — с проекцией точки $inline$ .

Решение

Если $inline$ имеет ту же проекцию на плоскость, что и $inline$ , то она лежит на прямой, перпендикулярной плоскости и содержащей $inline$ . Эту прямую можно задать параметрически, поскольку мы знаем точку и направляющий вектор, который совпадает с вектором нормали к $\alpha$ и потому равен $\overline{n}_1(2, -2, 1)$ . Система для прямой:

$\begin{cases} x = 2t_1 + 1\\ y = -2t_1 + 2\\ z = t_1 - 3\\ \end{cases}$

Аналогично, $inline$ лежит на прямой, проходящей через $inline$ и перпендикулярной $\beta$ . Вектор нормали: $\overline{n}_2(-1, 2, 3)$ , система:

$\begin{cases} x = -t_2 + 2\\ y = -2t_2 + 2\\ z = 3t_2 + 1\\ \end{cases}$

Пересечение прямых и будет являться искомой точкой. Для её нахождения нужно определить $inline$ и $inline$ , для этого достаточно приравнять первые два уравнения систем:

$\begin{cases} 2t_1 + 1 = -t_2 + 2\\ -2t_1 + 2 = 2t_2 + 2\\ \end{cases} \Leftrightarrow \begin{cases} 3 = t_2 + 4\\ -2t_1 + 2 = 2t_2 + 2\\ \end{cases} \Leftrightarrow \begin{cases} t_2 = -1\\ t_1 = 1\\ \end{cases}$

Подставив параметры в обе системы, убеждаемся, что получили одну и ту же точку $inline$ , которая и является искомой.

G. Домино

В далёком созвездии Тау-Кита на каждой половинке костяшки домино стоит от $inline$ до $inline$ точек, причём для каждой пары чисел $inline$ таких, что $inline$ и $inline$ целые от $inline$ до $inline$ , существует ровно одна доминошка, содержащая оба этих числа. Космический турист прилетел и выбрал наугад перевёрнутую костяшку. При каком $inline$ математическое ожидание модуля разности количеств точек на одной и на другой половине этой доминошки будет равно $inline$ ?

Решение

Обозначим случайную величину за $\xi$ , вероятностное пространство за $\Omega$ и образ случайной величины за $\xi(\Omega)$ . Будем считать матожидание по формуле:

$E(\xi) = \sum_{k \in \xi(\Omega)} k \Pr[\xi = k] = 2$

Пусть $inline$ — событие, что величина примет значение $inline$ , тогда $\Pr[\xi = k] = \frac{|A_k|}{|\Omega|}$ . Домножив на $|\Omega|$ , получаем:

$\sum_{k \in \xi(\Omega)} k |A_k|= 2 |\Omega|$

Посчитаем $|\Omega|$ . Во-первых, в него входят доминошки с одинаковыми числами на половинках. Во-вторых, в него входят все возможные пары различных чисел, причем каждая по одному разу. Значит,

$|\Omega| = n + 1 + \frac{n(n + 1)}{2}$

.

Теперь посчитаем сумму. Понятно, что величина принимает значения от 0 до $inline$ . Сколько раз она принимает значение $inline$ ? Ровно $inline$ : благоприятные исходы — это доминошки $(0, k), (1, k + 1), \ldots, (n - k, n)$ . Значит:

$\sum_{k \in \xi(\Omega)} k |A_k| = \sum_{k = 0}^n k(n - k + 1) = (n + 1)\sum_{k = 0}^n k - \sum_{k = 0}^n k^2 = \frac{n(n + 1)^2}{2} -$

$- \frac{n(n + 1)(2n + 1)}{6} = \frac{n(n + 1)(n + 2)}{6}$

Получаем уравнение:

$\frac{n(n + 1)(n + 2)}{6} = (n + 1)(n + 2)$

Поскольку $inline$ , получаем, что $inline$ .

H. Экзамен

Два друга решили вместе пойти на экзамены в ШАД и договорились встретиться у входа с 14:00 до 15:00, но не договорились во сколько именно. Момент времени прихода каждого из них распределён равномерно на этом отрезке времени, но друзья нетерпеливые, поэтому через 15 минут ожидания они отчаиваются дождаться и заходят одни. Известно, что они встретились.

Найдите вероятность того, что оба пришли до 14:45.

Решение

Для того, чтобы решить эту задачу, нам нужно немного порисовать. А именно, давайте нарисуем квадрат 60x60. Ось x будет обозночать время прихода первого, y — второго.

Событие «друзья встретились» изображено на рисунке красной областью. Событие «каждый пришёл до 14:45» обозначено пересечением 2 зелёных областей. Пользуясь тем, что время прихода каждого из друзей распределено равномерно, можем понять, что вероятность того, что «каждый пришёл до 14:45» при условии, что «друзья встретились» это отношение площади пересечения всех 3 областей к площади красной области. Применяя теорему пифагора и простой счёт, можем получить ответ $\frac{5}{7}$ .

I. Случайная величина

Плотность распределения случайной величиы $\xi$ равна $p(x)=\frac{1}{\sin x}$ при $inline$ от $\pi/2$ до $2 \arctan e$ и нулю при всех остальных $inline$ .

Найдите значение, которое эта случайная величина не превосходит с вероятностью $\frac{1}{2}$ .

Решение

Выразим искомую величину через плотность и воспользуемся универсальной тригонометрической подстановкой:

$\Pr(\xi \leq x) = \int\limits_{\pi/2}^x \frac{dt}{\sin{t}} = \int\limits_{1}^{\tan{x/2}} \frac{du}{u} = \ln{\tan{\frac{x}{2}}}$

Получили уравнение:

$\ln{\tan{\frac{x}{2}}} = \frac{1}{2} \Leftrightarrow \tan{\frac{x}{2}} = e^{1/2} \Leftrightarrow x = 2 \tan^{-1}{e^{1/2}}$

J. Найти среднее

Условие

Ограничение времени	2 секунды
Ограничение памяти	256Mb
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

Костя разрабатывает модуль статистики для высоконагруженного сервиса. Накопилось много исторических данных: n вещественных чисел $a_0, a_1, \dots, a_{n-1}$ .

Из-за частого обращения к его модулю за вычислением среднего геометрического эту функцию необходимо ускорить!

На вход поступают множество запросов по поиску среднего на интервале индексов от l до r. Найдите необходимые значения.

Для запроса от $inline$ до $inline$ необходимо вернуть величину:

$\sqrt[r-l+1]{a_{l} \cdot a_{l+1} \cdot \ldots \cdot a_{r}}$

Формат ввода

В первой строке входных данных записано число $inline$ ( $1 \leq n \leq 300 000$ ).

Во второй строке записаны n вещественных чисел $inline$ ( $0.01 \leq a_i \leq 100$ ) с двумя десятичными знаками.

В третьей строке входных данных записано число $inline$ ( $1 \leq q \leq 100 000$ ) — количество запросов.

Далее в $inline$ строках записано по два целых числа $inline$ и $inline$ ( $0 \leq l_i \leq r_i < n$ ) — $inline$ -й запрос на вычисление среднего.

Формат вывода

Для каждого запроса на вычисление среднего выведите найденное значение с 6 верными знаками после точки.

Ответы должны следовать в соответствии с порядком запросов.

Пример 1

Ввод	Вывод
8 79.02 36.68 79.83 76.00 95.48 48.84 49.95 91.91 10 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 1 7 2 7	79.020000 53.837288 61.391865 64.756970 69.986085 65.913194 63.352986 66.369195 64.735454 71.164108

Пример 2

Ввод	Вывод
1 1.00 1 0 0	1.000000

Пример 3

Ввод	Вывод
8 1.34 1.37 1.40 1.44 1.91 1.95 1.96 1.97 5 1 4 2 7 4 6 0 3 2 6	1.515518 1.752724 1.939879 1.387008 1.712233

Примечания

Костя считает, что его реализация функции эффективно использует соотношение $xy = e^{\ln x + \ln y}$ . Но вы можете это соотношение не использовать.

Решение

Для простоты сначала рассмотрим вариацию со средним арифметическим. Чтобы вычислять его для отрезка за $inline$ , необходимо находить сумму на отрезке за $inline$ .

Это делается с помощью следующего трюка. Насчитаем массив sums, где $sums[i] = a[0] + a[1] + \dots + a[i]$ . Так как $inline$ , то это можно сделать за $inline$ . Теперь сумма на отрезке с $inline$ по $inline$ — это просто $inline$ . Чтобы вычислить среднее арифметическое на отрезке, нужно еще поделить эту сумму на $inline$ . Итого $inline$ на запрос и $inline$ на предподсчёт.

В вариации со средним геометрическим чуть посложнее. Так как теперь вместо суммы у нас умножение, числа могут расти довольно быстро, и произведение чисел на префиксе может быть настолько большим или маленьким, что не будет влезать в стандартные типы данных. Чтобы решить эту проблему, будем считать натуральный логарифм среднего геометрического, а потом просто возведем $inline$ в эту степень. Школьная математика гласит, что $\ln ((a[l] \cdot ... \cdot a[r])^{\frac{1}{r - l + 1}}) = \frac{\ln a[l] \cdot \dots \cdot a[r]}{r - l + 1} = \frac{\ln a[l] + \dots + \ln a[r]}{r - l + 1}$ , а сумму логарифмов можно посчитать за $inline$ с помощью описанного выше трюка.

Код: gist.github.com/Azatik1000/0b0d8496785169a8ac0d35a8c9e8e59f

K. Удалить последнего

Условие

Ограничение времени	2 секунды
Ограничение памяти	256Mb
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

Дан массив $inline$ из $inline$ целых чисел. Некоторые числа в последовательности могут повторяться.

Удалите из последовательности последние вхождения каждого из элементов, остальные элементы нужно оставить в последовательности.

Обратите внимание, если элемент встречается только один раз, то его нужно удалить.