14.05.2020 15:11
DeathCookies 2 2400 Источник
Привет! С вами Азат Калмыков, куратор в «ШАД 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}}$ имеет не более одного локального минимума?

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

Заметим, что экспонента всегда положительна, не влияет на знак, поэтому её можно откинуть и считать, что $f(x) = x^4 - (a + 1)x^3 + (a - 2)x^2 + 2ax$. Многочлен легко раскладывается на множители, потому что все его корни можно угадать: это $-1, 0, 2, a$. Значит, $f(x) = (x + 1)x(x - 2)(x - a)$.

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

B. Предел


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

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


Решение
Сначала посчитаем предел, приняв $a = 1$. Поскольку $\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$, от возведения в степень $x$ неравенство сохранится, а при переходе к пределу изменится только строгость знаков. Левую часть можно посчитать сразу как следствие из второго замечательного предела, она равна $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 $, если $x_0=1$?

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

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

.

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

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



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

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



Давайте заметим что, при $x_1=-1$ значение градиента будет таким же по модулю, как в точке $x_0$, но иметь обратный знак. Таким образом, можно понять, что при таком варианте градиентный спуск будет «скакать» туда-сюда из точки $1$ в $-1$ и обратно. Таким образом, можно понять, что при $x_1=-1 \Leftrightarrow \lambda=0.5 $ градиентный спуск уже не найдёт точку минимума (это точка $0$). Но надо показать, что при меньших $ \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$, то получим что $|x_n|$ сходится к нулю. Значит градиент находит минимум.


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$ является собственным для матрицы $A$, если $\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$, по второй — что $a = 2$, проверяем, что третья координата согласуется с ответом. Значит, $a = 2$.

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


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

$ \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$ и минимум достигается в точности в $a = 3$. Тогда, пользуясь формулой $\det(A^{-1}) = \det(A)^{-1}$, получаем, что максимум определителя обратной матрицы достигается в $a = 3$.

F. Проекции


Даны точки $ B(1,2,?3) $ и $C(2,2,1)$, а также плоскости $\alpha$:$2x?2y+z=0$ и $?$:$?x+2y+3z=0$. Найдите координаты точки $A$, если известно, что её ортогональная проекция на $\alpha$ совпадает с проекцией точки $B$, а на $\beta$ — с проекцией точки $С$.

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

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



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

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



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

$\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}$



Подставив параметры в обе системы, убеждаемся, что получили одну и ту же точку $A(3, 0, -2)$, которая и является искомой.

G. Домино


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

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

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



Пусть $A_k$ — событие, что величина примет значение $K$, тогда $\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 до $n$. Сколько раз она принимает значение $k$? Ровно $n - k + 1$: благоприятные исходы — это доминошки $(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)$



Поскольку $n > 0$, получаем, что $n = 6$.

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}$ при $x$ от $\pi/2$ до $2 \arctan e$ и нулю при всех остальных $x$.

Найдите значение, которое эта случайная величина не превосходит с вероятностью $\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. Найдите необходимые значения.

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

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



Формат ввода


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

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

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

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

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


Для каждого запроса на вычисление среднего выведите найденное значение с 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}$. Но вы можете это соотношение не использовать.

Решение
Для простоты сначала рассмотрим вариацию со средним арифметическим. Чтобы вычислять его для отрезка за $О(1)$, необходимо находить сумму на отрезке за $O(1)$.

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

В вариации со средним геометрическим чуть посложнее. Так как теперь вместо суммы у нас умножение, числа могут расти довольно быстро, и произведение чисел на префиксе может быть настолько большим или маленьким, что не будет влезать в стандартные типы данных. Чтобы решить эту проблему, будем считать натуральный логарифм среднего геометрического, а потом просто возведем $e$ в эту степень. Школьная математика гласит, что $\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}$, а сумму логарифмов можно посчитать за $О(1)$ с помощью описанного выше трюка.

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

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


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

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

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

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

Формат ввода


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

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


В первой строке выведите число $m$ ($0 \leq m < n$) — количество элементов, оставшихся в последовательности.

Во второй строке выведите $m$ чисел — числа, оставшиеся в последовательности. Вы не должны переставлять числа, они должны следовать в том порядке, как были в исходной последовательности.

Пример 1


Ввод Вывод
10
1 1 5 2 4 3 3 4 2 5
 5
1 5 2 4 3


Пример 2


Ввод Вывод
1
1000000000
 0


Пример 3


Ввод Вывод
10
1 2 3 3 2 1 4 1 2 0
 5
1 2 3 2 1


Решение
Заведем unordered_set (C++) / HashSet (Java) / set (Python), куда будем класть уже встреченные числа. Пройдемся по массиву справа налево, для очередного числа проверим, есть ли оно в множестве встреченных чисел. Если нет, то добавим его в это множество. Если же есть, то добавим в конец вектора-ответа. В конце сделаем reverse вектора ответа за $O(n)$. Проверка на нахождение числа в хеш-таблице работает за $О(1)$, поэтому общая асимптотика по времени $O(n)$.

Код: gist.github.com/Azatik1000/2fef745e23c23eb020f21878980cae08

L. Доска объявлений


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

Костя решил развесить объявления о том, как наиболее правильно мыть руки.

Он нашел доску объявлений размером $W ? H$, а его объявление имеет ширину a и пока неизвестную высоту не менее b. Костя хочет разместить объявление, чтобы оно не накрывало никакое уже размещенное на доске объявление. У нового объявления может быть общая граница с наклеенными или доской объявлений, но площадь пересечения с другими объявлениями должна быть нулевой.

Вам даны координаты наклеенных объявлений. Определите координаты области, где Костя может приклеить свое объявление так, чтобы высота объявления была как можно больше. Если таких областей несколько, то подойдет любая из них.

Про координаты. Левый нижний угол доски объявлений имеет координаты $(0, 0)$, а правый верхний — $(W, H)$. Для каждого уже наклеенного объявления нам известны координаты левого нижнего угла и правого верхнего углов.

Гарантируется, что подходящая область на доске объявлений всегда существует.

Формат ввода


В первой строке заданы размеры доски объявлений $W$, $H$ и размер объявления Кости $a$, $b$ ($1 \leq W$, $H \leq 100?000$, $1 \leq a \leq W$, $1 \leq b \leq H$).

Во второй строке записано число $n$ ($0 \leq n \leq 100$) — количество уже приклеенных объявлений.

Далее в $n$ строках записаны координаты объявлений $(x_{ld}, y_{ld})$ и $(x_{ru}, y_{ru})$ ($0 \leq x_{ld} < x_{ru} \leq W, 0 \leq y_{ld} < y_{ru} \leq H$). Объявления могут перекрываться, т.е. иметь ненулевую площадь пересечения.

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


Выведите координаты левого нижнего $(x_{ld}, y_{ld})$ и правого верхнего $(x_{ru}, y_{ru})$ углов области, куда Костя может приклеить объявление. Область должна иметь ширину $a$ и наибольшую подходящую высоту (гарантируется, что не менее $b$). Никакая часть найденной области не должна быть занята наклеенными объявлениями.

Все числа должны быть целыми и неотрицательными.

Если подходящих областей несколько, выведите любую из них.

Пример 1


Ввод Вывод
11 8 2 7
4
1 5 3 7
2 2 4 5
5 3 9 4
5 3 7 8
 9 0 11 8


Пример 2


Ввод Вывод
11 8 7 3
4
1 5 3 7
2 2 4 5
5 3 9 4
5 3 7 8
 4 0 11 3


Пример 3


Ввод Вывод
11 8 4 4
4
1 5 3 7
2 2 4 5
5 3 9 4
5 3 7 8
 7 4 11 8


Решение
Найдем область максимальной высоты, в которую можно наклеить наше объявление. Заметим, что произведение $W * n$ не очень большое.

Переберем ширину $x$ (от $0$ до $W - a$), на которой будет находиться левая граница нашего объявления. Рассмотрим только те объявления, у которых ненулевая часть их площади находится на высоте от $x$ до $x + a$, остальные никак не мешают нам наклеить наше объявление. Для тех, которые попали в «полосу» от $x$ до $x + a$, выпишем пары $y$-координаты их нижней и верхней границ. Эти пары образуют отрезки, ни с одним из которых не должен пересекаться отрезок $(y_1, y_2)$, где $y_1$ и $y_2$ — это $y$-координаты нижней и верхней границы соответственно той области, куда мы наклеим наше объявление. Осталось максимизировать $y_2$ — $y_1$.

Для этого объединим все выписанные отрезки, добавив к ним для удобства $(0, 0)$ и $(h, h)$, соответствующие границам доски. Чтобы это сделать, отсортируем все отрезки по нижей, а при равенстве по верхней границе, и пройдемся по ним в отсортированном порядке. Если нижняя граница очередного отрезка ниже верхней границы последнего отрезка, то расширим последний до верхней границы очередного отрезка, иначе добавим в объединение очередной отрезок. После того, как мы получили объединение отрезков, ответом является максимальная разность между концами двух соседних в отсортированном порядке отрезков в объединении.

При максимизации ответа запоминаем подходящие границы и таким образом нходим ответ. Итого $O(W * n * \log n)$ по времени и $O(n)$ по памяти.

Код: gist.github.com/Azatik1000/2c07ebdd866ce20a4b5f5e6ee7408ad7