12.10.2020 10:13
avsmal 5 2900 Источник
Вступительное испытание на корпоративную магистерскую программу JetBrains на базе Университете ИТМО начинается с онлайн-теста. Летом мы опубликовали разбор нескольких математических задач из теста 2019 года, а сегодня представляем разбор одного из вариантов прошедшего набора.


Несколько слов о том, как устроен тест. Абитуриенты получают ссылку на закрытый курс на платформе Stepik.org. Далее у них есть несколько недель на то, чтобы приступить к решению. Тест состоит из 12 задач, на них отводится два часа. Решать задачи можно в произвольном порядке, за каждую из них начисляется один балл. Проходной балл меняется от года к году. В этот раз он был довольно низким — задачи получились сложные. Кураторы программы сделали выводы и постараются к следующему набору подготовить задачи полегче.

Задача 1


Найдите уравнение касательной к кривой $xy=6\cdot\exp(2x-3y)$ в точке $(3, 2)$. Ответ запишите в виде $ax+by=c$, где $a, b, c$ — целые несократимые числа и $a>0$ (без пробелов и скобок), например, $2x+3y=7$.

Когда в задаче спрашивается про касательную к графику функции, то это почти всегда связанно с вычислением производной. В данном случае требуется найти производную для неявно заданной функции. Будем считать, что $y$ — это функция от $x$. Продифференциируем обе части равенства $xy=6\cdot\exp(2x-3y)$ по $x$. Получаем

$ y + xy' = (2 - 3y')\cdot 6\cdot \exp(2x - 3y).$

Это позволяет выразить производную $y'$ через $x$ и $y$.

$ y' = \frac{12\cdot \exp(2x - 3y) - y}{x + 18\cdot \exp(2x - 3y)}. $

Теперь можно вычислить значение производной $y'$ в точке $(3,2)$. Обозначим это значение $\alpha$.

$ \alpha = \frac{12\cdot \exp(0) - 2}{3 + 18\cdot \exp(0)} = \frac{10}{21}. $

Это значение задаёт тангенс угла наклона касательной к кривой в точке $(3,2)$. Осталось вспомнить, что уравнение прямой можно задать в виде $y=\alpha x + b$. Зная, что прямая должна проходить через точку $(3,2)$, мы можем вычислить $b$:

$2 = \frac{10}{21}\cdot 3 + b.$

Следовательно, $b=\frac{4}{7}$. Получаем, что уравнение искомой прямой имеет вид:

$y = \frac{10}{21}x + \frac{4}{7}.$

Приводим его к требуемой форме домножив на 21 и получаем:

$10x - 21y = -12.$


Задача 2


На плоскости нарисованы две кривые, заданные многочленами второй степени.


Найдите площадь замкнутой области, которая ограничена этими кривыми. Если такой области нет, то нужно вывести число 0.

Вход
На первой строке три целых числа $a_1$, $b_1$, $c_1$, задающие первую кривую $f(x) = a_1 x^2 + b_1 x + c_1$, на второй строке — три целых числа $a_2$, $b_2$ и $c_2$, задающие кривую $g(x)=a_2x^2+b_2x+c_2$. Все числа по модулю не превосходят $10$.

Выход
Площадь замкнутой области, ограниченная $f(x)$ и $g(x)$.
Ответ должен быть вычислен с точностью 5 знаков после запятой.

Это задача на программирование, но с некоторой математической составляющей. Чтобы вычислить площадь искомой области, можно вычислить площадь под графиками функций $f(x)$ и $g(x)$ на отрезке между точками пересечения и вычесть одну из другой. Можно поступить проще: сразу рассматривать функцию $h(x) = f(x) - g(x)$ и вычислить площадь под графиком этой функции между её корнями. Это немного упростит задачу. Предлагается следующий алгоритм:

  1. вычисляем коэффициенты $h(x) = ax^2 + bx + c$,
  2. проверяем, что получился квадратный многочлен ($a\neq 0$), и что он имеет два различных корня (дискриминант больше нуля), если нет — возвращаем ноль,
  3. вычисляем корни $r_1$ и $r_2$, $r_1<r_2$
  4. вычисляем площадь под графиком $h(x)$ между $r_1$ и $r_2$,

    $ \int\limits_{r_1}^{r_2} h(x)\,dx = (ax^3/3+bx^2/2+cx)\Big|_{r_1}^{r_2}. $

  5. возвращаем модуль этого значения, т.к. при $a>0$ интеграл будет отрицательным.

Далее идёт реализация этого алгоритма на Питоне

# считываем коэффициенты f(x) и g(x)
a1, b1, c1 = map(int, raw_input().split())
a2, b2, c2 = map(int, raw_input().split())

# вычисляем коэффициенты h(x)
a = a1 - a2
b = b1 - b2
c = c1 - c2

# проверяем наличие корней
d = b * b - 4 * a * c
if a == 0 or d <= 0:
    print(0)
    exit(0)

# вычисляем корни
r1 = (-b - math.sqrt(d)) / (2.0 * a)
r2 = (-b + math.sqrt(d)) / (2.0 * a)

# первообразная для h(x)
def H(x):
    return a*x*x*x/3.0 + b*x*x/2.0 + c*x

# вычисляем определённый интеграл и выводим его модуль в требуемом формате
print("{:.5f}".format(math.fabs(H(r2) - H(r1))))


Задача 3


В пространстве $\mathbb{R}^5$ задано стандартное скалярное произведение, $L$ — подпространство, заданное как линейная оболочка векторов $a_1=(2,0,-1,-2,0)$, $a_2=(1,-1,0,1,-1)$, $a_3=(1,3,0,1,-1)$. Найти ортогональную проекцию вектора $x=(3,1,-1,2,0)$ на подпространство $L$ вектор $x_L$ и ортогональную составляющую $x_M$ этого же вектора ($x_L+x_M=x$).

В ответ напишите сумму координат вектора $x_M$ (например, для вектора $(1,2,3,2,1)$ сумма координат будет 9).

Ответ укажите с точностью до двух знаков после точки. При необходимости округлите по правилам математики.

Заметим, что вектора $a_1$, $a_2$ и $a_3$ — ортогональны (это можно проверить вычислив попарные скалярные произведения), но не нормированы. Давайте найдём проекцию $x$ на каждый из трёх векторов.

$ \mathrm{proj}_{a_1}x = \frac{x\cdot a_1}{|a_1|} = \frac{3}{\sqrt{9}} = 1. $

$ \mathrm{proj}_{a_2}x = \frac{x\cdot a_2}{|a_2|} = \frac{4}{\sqrt{4}} = 2. $

$ \mathrm{proj}_{a_3}x = \frac{x\cdot a_3}{|a_3|} = \frac{8}{\sqrt{12}} = \frac{4\sqrt{3}}{3}. $

Таким образом

$x_L = 1\cdot \frac{a_1}{|a_1|} + 2\cdot \frac{a_2}{|a_2|} + \frac{4\sqrt{3}}{3} \cdot \frac{a_3}{|a_3|} = \frac{1}{3}\cdot a_1 + a_2 + \frac{2}{3} \cdot a_3. $

Осталось выразить $x_M$

$ x_M = x - x_L = x - \frac{1}{3}\cdot a_1 - a_2 - \frac{2}{3} \cdot a_3. $


В ответе нужно записать сумму координат $x_M$. Можно было бы сначала вычислить $x_M$, а потом сложить его координаты, но можно ещё проще: воспользуемся тем, что сумма координат суммы векторов, равна сумме сумм координат каждого из слагаемых.
Для получения ответа, вычислим суммы координат для каждого из векторов отдельно и сложим их с соответствующими коэффициентами:

$ 5 - \frac{1}{3}\cdot (-1) - 0 - \frac{4}{3} \cdot 4 = 5 + 1/3 - 8/3 = 8/3 \approx 2.67. $


Задача 4


Обозначим за $w(k)$ — комлексный корень степени $k$ из единицы с минимальным положительным аргументом (аргумент = угол в полярной форме комплексного числа). Например, $w(4) = i$.

Найдите минимальное положительное целое $x$, являющееся решением следующего уравнения.

$ \left(w(28)\cdot w(14)\right)^x = w(7)^4. $


По определению $w(k)$ можно вывести явную формулу: $w(k) = e^{\frac{2\pi}{k}\cdot i}$ (тут мы используем показательную форму записи комплексного числа, это соответствует $w(k) = \cos(2\pi/k) + i\sin(2\pi/k)$). Подставляем это в уравнение и получаем:

$ \left(e^{\frac{2\pi}{28}\cdot i}\cdot e^{\frac{2\pi}{14}\cdot i}\right)^x = \left(e^{\frac{2\pi}{7}\cdot i}\right)^4 \quad\implies\quad e^{\frac{3x\pi}{14}\cdot i} = e^{\frac{8\pi}{7}\cdot i}. $

Остаётся решить уравнение на показатели. Тут нужно помнить, что $e^{2\pi i} = 1$. Поэтому, получаем уравнение

$ \frac{3x\pi}{14}\cdot i = \frac{8\pi}{7}\cdot i + 2\pi k\cdot i. $

Домножаем на $14$ и делим на $\pi i$. Получается следующее уравнение в целых числах, где нас интересует решение с минимальным положительным целым $x$.

$ 3x = 16 + 28k. $

Проверив $k=0,1,2$, находим ответ $x = 24$ при $k=2$.

Задача 5


Маленькому мальчику Ване на кружке по системам счисления задали следующую задачу: перевести число $X$ в системе счисления $s_1$ в систему счисления $s_2$. Недолго думая, он позвал на помощь своего лучшего друга Петю, который славился тем, что замечательно умел считать до $10$ на пальцах. После нескольких бессонных ночей ребята общими усилиями справились с задачей.

Однако, на следующем занятии Ване задали похожую задачу, где $X$, к сожалению, превышало $10$. Тогда ребята решили обратиться к старшей сестре Пети с просьбой написать универсальную программу, которая решает задачу для любых $X$, $s_1$ и $s_2$. Ваша цель – выполнить просьбу Вани и Пети.

Входные данные
Во входных данных вашей программе дается три числа: исходное число $X$, основания систем счисления $s_1$ и $s_2$ ($2 \le s_1,s_2 \le 10$). Число $X$ в десятичной системе счисления не превышает $2 \times 10^9$.

Выходные данные
В выходных данных должно быть число $X$, записанное в системе счисления $s_2$, или $-1$, если входные данные некорректны (число $X$ во входных данных не является корректной записью числа в системе счисления $s_1$).

Это задача на перевод числа из одной системы счисления. Если нам дано число $x = \overline{a_{n-1}a_{n-2}\dotsc a_{0}}$ в системе счисления с основанием $s_1$, то его значение можно вычислить, как

$ x = a_{n-1}s_1^{n-1} + a_{n-2}s_1^{n-2} + \dotsb + a_0. $

Это же можно вычислить по схеме Горнера:

$ x = (\dotsc(a_{n-1}s_1 + a_{n-2})s_1 + \dotsb + a_1)s_1 + a_0. $

Для того, чтоб перевести $x$ в число $\overline{b_{n-1}b_{n-2}\dotsc b_{0}}$ в системе счисления по основанию $s_2$, нужно повторить эту процедуру в обратном порядке. Тогда цифра $b_i$ будет вычисляться по формуле

$ b_i = \lfloor x / s_2^i\rfloor \bmod s_2. $



Ниже представлена реализация этой идеи на Питоне.
# считываем входные данные
xstr, b, c = raw_input().split()
s1 = int(b)
s2 = int(c)

# проверяем входные данные и преобразуем в число
x = 0
for c in xstr:
    if int(c) >= s1:
        print(-1)
        exit()

    x = x * s1 + int(c)

# переводим в заданную систему счисления
res = ""
if x == 0:
    res = "0"
else:
    while x > 0:
        res = str(x % s2) + res
        x = x // s2
     
print(res)


Задача 6


Про студентов магистерской программы Software Engineering известно, что они дружат друг с другом так, что каждый студент дружит не более чем с 3 другими, и для любых двух студентов верно, что они либо дружат друг с другом, либо есть студент, который дружит с ними обоими.

Какое максимальное число студентов на магистерской программе Software Engineering?

Задача на комбинаторику и теорию графов. Рассмотрим одного студента. Он сам дружит не более, чем с тремя студентами. Каждый его друг имеет не более 2 других друзей. Других студентов по условию быть не может. Получаем, что всего не более $1 + 3 + 3\cdot 2 = 10$ студентов. Осталось проверить, что такую граф существует, но это несложно сделать на листочке.


Левая вершина — рассматриваемый студент, правее три его друга и шесть друзей друзей. Цвета рёбер значения не имеют и нужны только для понятности картинки.

Задача 7


Сколько различных решений имеет следующее уравнение $x_1+x_2+x_3+x_4=50,$
если известно, что $x_1\in\{1,2,3,\dotsc\}$, $x_2\in\{2,3,4,\dotsc\}$, $x_3\in\{0,1,2,3,\dotsc\}$, $x_4\in\{0,1,2,3,\dotsc\}$?

Это простая задачка на три цикла — числа небольшие, результат можно быстро посчитать короткой программой.

count = 0
for x1 in range(1,51):
    for x2 in range(2,51):
        for x3 in range(51):
                if x1 + x2 + x3 <= 50:
                    count = count + 1
print(count)

Но писать программу необязательно, ответ не так сложно вычислить аналитически (на тесте такого требования не было). Для этого заметим, что исходная задача эквивалентна следующей.
Сколько различных решений имеет следующее уравнение $x_1+x_2+x_3+x_4=47,$
если известно, что $x_1,x_2,x_3,x_4\in\{0,1,2,3,\dotsc\}$?
(Мы вычли $1+2$ из правой части и добились того, чтобы все переменные начинались с нуля.)

Это уже типовая задача. Нам нужно разбить последовательность $n=47$ предметов на 4 части. Для этого нужно вставить $k = 3$ перегородки. По формуле для разбиения получаем

$\binom{n+k}{k} = \binom{50}{3} = \frac{50\cdot 49\cdot 48}{3!} = 50\cdot 49\cdot 8 = 1960.$



Задача 8


Найти длину кривой $x^{2/3}+y^{2/3}=9$, заключённой в первой четверти.

Ответ укажите с точностью до двух знаков после точки. При необходимости округлите по правилам математики.

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

$ \int\limits_a^b \sqrt{1 + (y')^2}\, dx. $

В нашем случае, $a = 0$, $y = (9 - x^{2/3})^{3/2}$. Для вычисления $b$, точки пересечения с осью абсцисс, нужно подставить $y=0$: получаем $x = 9^{3/2} = 3^3 = 27$. Вычислим $y'$:

$ y' = -\frac{2}{3}\cdot \frac{3}{2}\cdot x^{-1/3}\cdot \sqrt{9 - x^{2/3}} = -\sqrt{9x^{-2/3} - 1}. $

Вычисляем интеграл:

$ \int\limits_0^{27} \sqrt{1 + 9x^{-2/3} - 1}\, dx = \int\limits_0^{27} \sqrt{9x^{-2/3}} \, dx = \int\limits_0^{27} 3x^{-1/3} \, dx = \left(\frac{9}{2}\cdot x^{2/3}\right)\Bigg|_0^{27} = 81/2 = 40.5 $


Задача 9


На вход программе подаётся строка, содержащая слова, разделённые пробелом. Слово – это последовательность латинских символов, окружённая пробелами или границами строк.

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

Вход
Строка, содержащая последовательность строчных латинских символов, разделённых пробелами.

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

Выведите эту информацию в том порядке, в котором слова встречаются в тексте в первый раз.

Это чисто программистская задача на использование массивов, словарей и сортировок. Ниже представлено решение этой задачи на Питоне с комментариями.
# считываем входную строку и разбиваем на слова
words = raw_input().split()

# заводим необходимые словари
idx  = {}  # хранит номер последнего вхождения слова
dist = {}  # хранит минимальное расстояние между повторениями
first = {} # хранит номер первого вхождения

# проходим по словам и вычисляем минимальное расстояние для каждого слова
for i in range(len(words)):
    if words[i] in idx:
        if dist[words[i]] > i - idx[words[i]] - 1:
            dist[words[i]] = i - idx[words[i]] - 1
    else:
        first[words[i]] = i
        dist[words[i]] = 2 * len(words)  # замена +бесконечности

    idx[words[i]] = i 

# массив для хранения слов, которые встречаются более одного раза
good = []
for k in dist:
    if dist[k] < len(words):
        good.append((k, dist[k], first[k]))
        
# упорядочиваем массив по номеру первого вхождения
good.sort(key=lambda t: t[2])

# выводим результат
for t in good:
    print("{}: {}".format(t[0], t[1]))


Задача 10


В студенческом общежитии ИТМО очень сложно устроена локальная сеть — местный администратор не любит роутеры, потому сетевые кабели протянуты напрямую между некоторыми компьютерами (для этого в некоторые компьютеры пришлось установить дополнительные сетевые карты).

Вам, как новичку в общежитии, хочется выяснить как все устроено. Поэтому вы можете выбрать любые два компьютера и получить ответ на вопрос “проложен ли между ними провод?”. Вам бы хотелось узнать — можно ли в общежитии передать информацию с любого компьютера до любого другого по проводам.

Какое минимальное количество вопросов необходимо задать чтобы гарантированно получить ответ, если всего в общежитии установлено 32 компьютера?

Задача на теорию графов. Тут нужно показать, что какую бы стратегию мы не выбрали, нам придётся перебрать все пары компьютеров, т.е. задать $32\cdot 31/2 = 496$ вопросов. До этого нетрудно догадаться, и для ответа на тест этого достаточно. Тем не менее, давайте постараемся разобраться, почему это так.

Довольно легко придумать следующую простую идею, которая всё объясняет: если мы про какую-то пару компьютеров не спросили, например, не спросим про пару $\{12,17\}$, то давайте рассмотрим сеть, в которой компьютер $17$ соединён только с компьютером $12$. Если не спросить про $\{12,17\}$, то мы не можем быть уверены, что $17$ соединён хоть к каким-то компьютером. Это рассуждение объясняет, почему нужно спросить про все пары компьютеров, и приводит к правильному ответу. Только вот это рассуждение не является корректным. Проблема заключается в том, что мы неявно предполагаем, что наши вопросы не зависят от ответов на предыдущие вопросы. Когда мы предлагаем рассмотреть сеть, в которой компьютер $17$ соединён только с компьютером $12$, то это уже другая сеть, нежели та, на которой мы не спросили про пару $\{12,17\}$. На разных сетях вопросы могут быть устроены по-разному. Другими словами, это рассуждение позволяет доказать, что не существует пары компьютеров $\{a,b\}$, про которую мы не спросим ни для какой конфигурации сети. При этом, если для каждой конфигурации сети существует какая-то пара, про которую мы не спрашиваем, то это не противоречит нашему рассуждению.

Корректное объяснение может выглядеть, например, так. Предположим, что вместо честного ответа на вопросы об устройстве сети, нам отвечают таким образом, чтобы заставить нас задавать как можно больше вопросов (такое доказательство называется рассуждением о противнике (adversary argument)). Как ему это сделать? Можно придерживаться следующей стратегии: отвечать «Да» только в том случае, если ответ «Нет» будет означать, что сеть несвязна. Давайте покажем, что при такой стратегии ответов нам всегда придётся спросить про все пары компьютеров. Рассмотрим граф, в котором вершины соответствуют компьютерам, а рёбра — тем парам, для которых мы получили ответ «Да». Заметим, что при такой стратегии ответов на вопросы получившийся граф будет ациклическим. Действительно, если в какой-то момент в графе появился цикл, то это означает, что мы получили ответ «Да» на вопрос про некоторую пару $\{a,b\}$, про которую можно было ответить «Нет», ведь $\{a,b\}$ уже связаны другими рёбрами, т.е. ответ «Нет» на вопрос о $\{a,b\}$ не означает несвязность сети. Теперь предположим, что мы убедились в связности сети не спросив про все пары. Это значит, что полученный граф представляет собой дерево содержащее все 32 вершины. Пусть $\{a,b\}$ — пара компьютеров, про которую мы не спросили. Давайте добавим ребро $\{a,b\}$ к дереву. Так как в дереве уже были пути между всеми парами вершин, то новое ребро добавит цикл.


Рассмотрим этот цикл и выберем на нём ребро, про которое мы спрашивали последним. Пусть это ребро $\{c,d\}$. Спрашивая про пару $\{c,d\}$ мы получили ответ «Да». По нашей стратегии нам отвечают «Да» только, если ответ «Нет» означал бы несвязность графа. Но это противоречит тому, что про пару $\{a,b\}$ мы ничего не спрашивали: можно было бы ответить «Нет» на вопрос о $\{c,d\}$ и всё равно добиться связности графа за счёт ответа «Да» на вопрос об $\{a,b\}$. Это противоречит предположению о выбранной стратегии ответов на вопросы.

Задача 11


Школьник Ваня приболел, и его мама решила вызвать врача домой. У врача есть статистика по району, где живет Ваня. У $90\%$ больных детей этого района — грипп, у остальных $10\%$ — ветрянка. Других болезней в этом районе не зафиксировано.

Один из основных симптомов ветрянки – это сыпь, она появляется в $95\%$ случаях заболевания ветрянкой. Однако, во время гриппа она тоже возможна и появляется в $8\%$ случаях.

Осмотрев Ваню, врач обнаружил сыпь. Какова вероятность того, что у Вани ветрянка?

Ответ укажите с точностью до двух знаков после точки. При необходимости округлите по правилам математики.

Это задача на теорию вероятностей и формулу Байеса. Обозначим следующие события: $A$ — у Вани грипп, $B$ — у Вани ветрянка.

$\Pr[A] = 0.9,\quad \Pr[B] = 0.1.$

Пусть $C$ — это наличие сыпи. Известно, что

$\Pr[C\mid B] = 0.95,\quad \Pr[C\mid A] = 0.08.$


Нас просят оценить условную вероятность $\Pr[B\mid C]$. По теореме Байеса:

$\Pr[B\mid C] = \frac{\Pr[C\mid B]\cdot\Pr[B]}{\Pr[C]}.$

Вероятность выпадения сыпи можно вычислить по формуле полной вероятности:

$ \Pr[C] = \Pr[C\mid B]\cdot\Pr[B] + \Pr[C\mid A]\cdot\Pr[A] = 0.95\cdot 0.1 + 0.08\cdot 0.9 = 0.167. $

В результате получаем:

$\Pr[B\mid C] = \frac{0.95\cdot 0.1}{0.167} \approx 0.57.$


Заключение


Надеемся, что этот разбор поможет абитуриентам программы подготовиться к онлайн-тесту. Для самостоятельной проверки предлагаем прорешать второй вариант. Все материалы вступительных испытаний опубликованы на сайте программы. Там же вы сможете найти полное описание процесса поступления. Не забывайте, что за успешным прохождением онлайн-теста следует устный этап вступительного испытания.

P.S. Внимательный читатель заметит, что в разборе 11 задач, а в тесте их должно быть 12. Одна из задач оказалась технически сложной, и мы решили её не разбирать, чтобы никого не пугать.