Добрый вечер, камрады! Сегодня для разбора предлагается нехитрый тервер.

По силам он будет любому 9класснику.

Подсказки: проведите экватор через C, D. Далее поймите, что решение задачи сводится к поиску вероятности попадания пересечения экватора и кратчайшей дуги, соединяющей AB на случайную дугу CD

Пишите решения в комментарии!!!

Добрый вечер, камрады. А вот и решение прошлого номера.

Задания с ШАД МТС очень простые, студенты наших курсов решают такое за 300 наносекунд💪💪.

Обсудить же задания можно в нашем чате.

@matesha_shad

Вот вам пара задач с первого этапа AI Masters. Попадаются те же задачи, поэтому очень полезно отрешать заранее. И не забываем про наши курсы!

Вот и задание экзамена.
Как прошло, товарищи?

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

Олимпиада ШАДа.
Вторая задача олимпиады. Полное условие с тестами оставлю в комментариях.

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

Решение:
Давайте отсортируем окружности по возрастанию радиуса. То есть после сортировки получим r[i] <= r[j] для всех i < j.
В условии сказано, что окружности не пересекаются.

Давайте построим граф на этих окружностях.
Пусть окружности - это вершинки графа. Проведем ориентированное ребро от вершины i в вершину j если окружность j находится внутри i.

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

- А в чем преимущество дерева ?
- В том что если все поддерева вершины i находится строго внутри окружности i.

Теперь как посчитать ответ ?
Мы фиксируем вершинку дерева, пусть это вершина v. Давайте найдем все такие подмножества окружности содержащий v из которых можно построить вложенную цепочку.
Можно легко заметить, что мы должны просто взять подмножество предков вершины v размера k - 1.
Пусть количество предков вершины v равно, тогда в ответ добавляем C(count_parents, k - 1).

Время работы алгоритма O(N ^ 2)
Код в комментариях.

Вот и задание сегодняшней олимпиады.
Как прошло, товарищи?

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

ШАД be like:

— Напишите "Hellow world"

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

Выкладываем все задания отборочного этапа ШАД 2024 года, по многочисленным просьбам.

Задания из единого банка, многие попадались на собесе в прошлом году. Очень полезно будет их прорешать.

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