Разбор тестового варианта 2024 года на магистерскую программу «Программное обеспечение высоконагруженных систем» в ИТМО

Чтобы получить допуск на экзамен при поступлении на магистерской программе «Программное обеспечение высоконагруженных систем», которую ИТМО делают вместе с Яндекс Образованием, для начала нужно пройти онлайн тест. Здесь представлен тест 2024 года, а также мое личное решение к нему.

Сразу хочу сказать, что автор (то есть я) публикую это решение как абитуриент и ни сколько не претендую на полную корректность и строгость решения. И так как это онлайн тест и на него никто не накладывает никаких ограничений, помимо того, что его должен решать я, а не кто-то другой, то оставляю за собой полное право пользоваться онлайн “помощниками” такими, как сервисы построения графиков и вычисления производных. Допускаю, что многие задачи можно решить аналитически и без использования кода. Но зачем, когда время сильно ограничено :)

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

A. Новогодний корпоратив

Решение:

Пусть - количество C++ и Python разработчиков в команде

Пусть - количество C++ и Python разработчиков в команде

Тогда в ответе требуется указать

При том 

Тогда вероятность, что ведущий выберет разработчика C++:

Тогда нам достаточно найти максимальное значение функции

на

Онлайн поиск экстремумов функции дает такой результат по поводу стационарных точек:

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

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

#include <iostream>
#include <vector>

double prob(double x, double y) {
    return (double)1/2 * ((9 - y) / (9 - y + x) + y / (y + 6 - x));
}

void solve(const std::vector<int>& x_values, const std::vector<int>& y_values) {
    double x_max = 0, y_max = 0, max = 0;
    for (auto x: x_values) {
        for (auto y: y_values) {
            double probability = prob(x, y);
            std::cout << "P(" << x << ", " << y << ") = " << probability << std::endl;
            if (probability > max) {
                max = probability;
                x_max = x, y_max = y;
            }
        }
    }

    std::cout << "maximum reaches if x = " << x_max << ", y = " << y_max << " and P = " << max << std::endl;
}

int main() {
    std::vector<int> x = { 0, 1, 2, 3, 4, 5, 6 };
    std::vector<int> y = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    solve(x, y);
}

Программа выдвет максимум

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

Значит ответ: 0, 8. Что значит, что в первой группе всего 1 плюсовик, а во второй группе 8 плюсовиков и 6 питонистов.

Проверим по исходной формуле для вероятности, что мы нигде по пути не ошиблись:

Ответ: 08

B. Сложный проект

Решение:

Так как при каждой починке 2х багов одного типа для одной операционки добавляются по 1му багу для каждого типа второй, то значит сумма багов не изменяется, следовательно она всегда равна , следовательно ограничено сверху количеством композиций длины 4 для числа 7 с возможными нулями, что равно количеству сочетаний с повторениями из 8 по 3:

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

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

#include <iostream>
#include <vector>
#include <set>

int to_int(const char state[4]) {
    return state[0] * 1000 + state[1] * 100 + state[2] * 10 + state[3] * 1;
}

void solve(const char state[4], std::set<int>& states) {
    for (int i = 0; i < 4; i++) {
        if (state[i] >= 2) {
            char new_state[4] = { state[0], state[1], state[2], state[3] };
            
            new_state[i] -= 2;
            if (i < 2) {
                new_state[2] += 1;
                new_state[3] += 1;
            } else {
                new_state[0] += 1;
                new_state[1] += 1;
            }

            if (states.count(to_int(new_state)))
                continue;
            
            std::cout << to_int(new_state) << std::endl;

            states.insert(to_int(new_state));
            solve(new_state, states);
        }
    }
}

int main() {
    const char begin_state[4] = { 2, 0, 2, 3 };    
    std::set<int> states = { to_int(begin_state)};

    solve(begin_state, states);

    std::cout << states.size() << std::endl;
}

Ответ:

C. Путешественник Петя

Решение:

Очевидно, что время дороги зависит от того в какой точке Петя пересечет ручей.

Тогда можно написать зависимость от :

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

Это точка , Плюс на построенном графике видно, что это точка минимума.

Ответ:

P.S.: Важно дописывать 0 в ответе, так как просят округлять до 3 знаков после запятой, ответ 215.43 системой проверки принимается как неверный.

D. Скучающий аналитик

Решение:

Всего на дашборде 9 квадратов 2х2. Пронумеруем квадраты, идя по слева-направо и сверху-вниз.

Пусть - событие, что -й квадрат закрашен в лиловый цвет. Тогда:

Тогда можно посчитать вероятность обратного события к искомому, что хотя бы 1 квадрат будет окрашен в лиловый цвет, по формуле включений-исключений:

Тогда искомая вероятность будет равна 

Такое слишком сложно посчитать руками, так что напишем программу. Идея алгоритма состоит в том, чтобы пронумеровать все клетки дашборда и искать вероятности всех пересечений. При нахождении очередного пересечения событий, нужно возвести 1/2 в степень количества клеток, которые присутствуют в объединении квадратов, соответствующих событий в пересечении. Алгоритм на питоне (так как там есть пакет работы с дробями):

from fraction import Fraction

squares = [
    {1, 2, 5, 6},
    {2, 3, 6, 7},
    {3, 4, 7, 8},
    {5, 6, 9, 10},
    {6, 7, 10, 11},
    {7, 8, 11, 12},
    {9, 10, 13, 14},
    {10, 11, 14, 15},
    {11, 12, 15, 16}
]

def calc_union_num(intersect):
    return len(set.union(*intersect))

def calc_prob_intersections(n, cur, interset):
    sum_prob = Fraction(0)
    for i in range(cur, len(squares)):
        interset.append(squares[i])
        if len(interset) == n:
            union_num = calc_union_num(interset)
            prob = Fraction(1, 2 ** union_num)
            sum_prob += prob
        else:
            sum_prob += calc_prob_intersections(n, i + 1, interset)
        
        interset.pop()
    
    return sum_prob

prob = Fraction(9, 2 ** 4)
for i in range(2, 9+1):
    intesect_set = []
    prob += Fraction(-1 if i % 2 == 0 else 1) * calc_prob_intersections(i, 0, intesect_set)

print("P(UAi) = ", prob)
answer = Fraction(1) - prob
print("1 - P(UAi) = ", Fraction(1) - prob)
print("answer = ", answer.numerator + answer.denominator)

Искомая вероятность : 

Тогда ответ: 

E. Сложные поверхности

Решение:

Во-первых, так как справа от знака равенства у нас сумма четных степеней, то

То есть ограничено снизу числом 0.

Избавимся от степеней с помощью замен . Тогда уравнение перепишется так:

Найдем частные производные:

Найдем  и , при которых частные производные обращаются в ноль:

Подставим найденные  и  в исходное уравнение и найдем :

Отсюда получаем, что  и . Но мы помним, что неотрицательно, так

что остается значение и . Проверим значение , что оно является

максимумом… Хотя, в принципе, можно и не проверять, потому что раз в условии сказано, что максимальное значение функция принимает, то значит у функции есть экстремум, который является максимумом, в котором значения частных производных равны нулю. Очевидно, остальные значения (только ), в которых частные производные обращаются в ноль нам не подходят, так как есть больше. Ну а максимумом не может быть точка, у которой не выполняется необходимое условие экстремума функции.

Итак, максимум достигается в точках ,надо найти, при каких x, y такие значения принимаются:

Можно заметить, что есть 4 точки, в которых принимает максимальное значение, а значит в сумме координат всех точек значения  и  сократятся из-за противоположности знаков и получится ответ, состоящий из максимального значения функции, помноженного на 4, то есть

Ответ:

F. Вкусные пончики

На мной взгляд - самая интересная задачка из теста с практикой-бытовой точки зрения :)

Решение:

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

Заметим, что перед нами тор и его объем вычисляется с помощью определенного интеграла как объем фигуры вращения вокруг оси . Но так же мы можем с помощью определенного интеграла посчитать объем Сашиной части (заштрихована зеленым цветом). Это такая же фигура вращения, которая на плоскости ограничена сверху функцией , а снизу .

Тогда объем фигуры:

Тор имеет объем

Тогда ответ на задачу:

Ответ:

Интересное наблюдение: ответ не зависит от .

G. Встреча друзей

Есть 3 идеи как решить задачу:

1. 

   Сохраняем всех друзей в массив вместе с пометкой вышел ли человек или нет. На каждом выходе искать слева людей, которые не вышли и искать справа людей которые не вышли. Каждый такой поиск за , всего поисков операций. Но, как правило, в таких задачах решения за квадрат не будут приняты, так как не успеют за установленный лимит.

2. 

   Заведем дерево (std::map в C++) друзей, с ключом номер друга. Тогда при каждом выходе друга достаточно слева поискать и справа, каждый поиск за , но поиск самого выходящего за . После поиска удаляем текущего, кто выходит, из дерева за  . Всего поисков столько же как и в предыдущем примере . Главное не забыть учесть пограничных ребят в дереве, а то можно словить сегфолт.

#include <iostream>
#include <iterator>
#include <string>
#include <map>

using map_t = std::map<int, std::string>;

int main() {
    int n;
    std::cin >> n;

    map_t friends;
    for (int i = 1; i <= n; i++) {
        friends[i] = {};
        std::cin >> friends[i];
    }
    
    for (int i = 0; i < n - 3; i++) {
        int id;
        std::cin >> id;

        auto it = friends.find(id);
        if (it == friends.begin())
            std::cout << std::prev(friends.end())->second;
        else
            std::cout << std::prev(it)->second;
        std::cout << " ";

        auto it_right = std::next(it);
        if (it_right == friends.end())
            std::cout << friends.begin()->second;
        else
            std::cout << std::next(it)->second;

        std::cout << std::endl;

        friends.erase(it);   
    }
}

3. 

   Задачу можно решить и за линейное время, если хранить друзей в двунаправленном списке, плюс в массиве хранить указатели на друга в списке. Поиск самого выходящего за  (так как храним отображение индекс → элемент списка в массиве), поиск слева и справа , всего поисков .​

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <iterator>
#include <utility>
#include <unordered_map>


struct node_t {
    std::string name;
    node_t *next = nullptr;
    node_t *prev = nullptr;
};

void add(node_t *head, node_t *new_node) {
    
    new_node->prev = head->prev;
    head->prev->next = new_node;

    head->prev = new_node;
    new_node->next = head;
}

void remove(node_t *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;

    delete node;
}

int main() {
    int n;
    std::cin >> n;

    std::unordered_map<int, node_t*> ptrs(n);
    node_t *head = nullptr;
    for (int i = 0; i < n; i++) {
        node_t* new_node = new node_t;
        std::cin >> new_node->name;

        if (!head) {
            head = new_node;
            head->next = head;
            head->prev = head;
        }
        else
            add(head, new_node);
        
        ptrs[i] = new_node;
    }

    for (int i = 0; i < n - 3; i++) {
        int idx;
        std::cin >> idx;

        idx--;
        auto node = ptrs[idx];
        std::cout << node->prev->name << " " << node->next->name << std::endl;
        remove(node);
        ptrs.erase(idx);
    }

    for (auto [_, node]: ptrs)
        delete node;


    return 0;
}

H. Точки и плоскость

Решение:

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

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

Воспользуемся тем фактом, что точки лежат на одной прямой. Тогда для каждой точки из запроса мы можем найти точку пересечения перпендикуляра, опущенного из этой точки на ту самую прямую, на которой лежат исходные точки, и так как расстояние точки из запроса до любой точки на прямой это длина гипотенузы прямоугольного треугольника, образованного перпендикуляром, самой прямой и отрезком, соединяющим точку из запроса с точкой на прямой, то достаточно найти ближайшую на прямой точку к точке пересечения перпендикуляра и прямой (обозначим ее за ), потому что второй катет (сам перпендикуляр) не меняет длины, то есть длина гипотенузы зависит только от расстояния между  и точкой на прямой. На прямой можно найти ближайшую точку к , отсортировав массив точек на прямой лексикографически по паре , с помощью бинарного поиска точки лексикографически не меньшую точки P ( в C++ это можно сделать с помощью std::lower_bound). Потом не забыть взять предыдущую точку и сравнить ее длину до  с длиной от найденной, ну и не забыть еще пограничные ситуации, когда  оказывает меньше всех точек на прямой или больше всех.

Надо бы еще понять, как найти ту самую точку  для некоторой точки  из запроса, для начала нужно взять две различные точки  и  из исходного массива, которые задают саму прямую, а дальше нам поможет ангем (или вот эта ссылочка):

Примечание: все точки в формуле есть вектора, то есть все операции стоит рассматривать как операции над векторами.

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

Приведен код на C++, но скорее всего проще было бы его реализовать на Python, если бы у автора было больше навыков с библиотеками вроде numpy для работы с векторами.

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <iterator>
#include <utility>
#include <cmath>
#include <optional>

double operator*(const std::vector<double>& lhs, const std::vector<double>& rhs) {
    double res = 0;
    for (double i = 0; i < std::min(lhs.size(), rhs.size()); i++)
        res += lhs[i] * rhs[i];
    return res;
}

std::pair<double, double> find_perpendicular_point(const std::pair<double, double>& line_point_1, const std::pair<double, double>& line_point_2, const std::pair<double, double>& point) {
    std::vector<double> line_vector = { line_point_2.first - line_point_1.first, line_point_2.second - line_point_1.second };
    std::vector<double> vector = { point.first - line_point_1.first, point.second - line_point_1.second };

    double P = line_vector * vector;

    std::pair<double, double> result;
    result.first = line_point_1.first + line_vector[0] * P / (line_vector[0] * line_vector[0] + line_vector[1] * line_vector[1]);
    result.second = line_point_1.second + line_vector[1] * P / (line_vector[0] * line_vector[0] + line_vector[1] * line_vector[1]);

    return result;
}

double distance(const std::pair<double, double>& lhs, const std::pair<double, double>& rhs) {
    return std::sqrt((lhs.first - rhs.first) * (lhs.first - rhs.first) + (lhs.second - rhs.second) * (lhs.second - rhs.second)) ;
}

int main() {
    int n;
    std::vector<std::pair<int, int>> points;

    std::cin >> n;

    std::optional<std::pair<int, int>> first_point, second_point;

    while (n--) {
        std::pair<int, int> pair;
        std::cin >> pair.first >> pair.second;
        points.emplace_back(pair);
    }
    std::sort(points.begin(), points.end());

    first_point = points[0];
    if (points.size() > 1 && points.back() != *first_point)
        second_point = points.back();

    int m;
    std::cin >> m;
    while (m--) {
        std::pair<int, int> point;
        std::cin >> point.first >> point.second;

        if (!second_point) {
            std::cout << first_point->first << " " << first_point->second << std::endl;
            continue;
        }
    
        auto intersect_point = find_perpendicular_point(*first_point, *second_point, point);
        auto lower_point = std::lower_bound(points.begin(), points.end(), intersect_point);

        if (lower_point == points.begin()) {
            std::cout << lower_point->first << " " << lower_point->second << std::endl;
        } else if (lower_point == points.end()) {
            std::cout << points.back().first << " " << points.back().second << std::endl;
        } else {
            auto left_lower_point = std::prev(lower_point);

            if (distance(*left_lower_point, point) <= distance(*lower_point, point))
                std::cout << left_lower_point->first << " " << left_lower_point->second << std::endl;
            else 
                std::cout << lower_point->first << " " << lower_point->second << std::endl;

        }
    }

    return 0;
}

Всем успехов при поступлении!