Олимпиада ВсОШ по Информатике (ИИ) 7-8 класс по Москве
📌 Задание 1 Представим, что число меняется по следующему алгоритму: если число чётно, его делят на 2, а если нечётно — вычитают 1. Из числа N после выполнения четырёх шагов алгоритма получилось число 12. Определите наименьшее возможное значение N.
📌 Задание 2 Модель искусственного интеллекта различает цифры 0 и 1 по следующему алгоритму: если линия, которой нарисована цифра, ограничивает некоторую часть плоскости, цифра определяется как 0, иначе — как 1. В частности, цифру 0 она определяет как 0, а цифру 1 — как 1. Полученная последовательность цифр интерпретируется как число в двоичной системе счисления. Какое число модель определит по записи 293676? Ответ запишите в десятичной системе счисления.
📌 Задание 3.1 Модель искусственного интеллекта различает пиксельные цифры 3 и 8. Для каждой цифры у модели есть эталонное изображение.
Расстоянием между двумя изображениями называется число клеток, цвет которых на этих изображениях различается. Модель сравнивает новое изображение с обоими эталонами и выбирает цифру с меньшим расстоянием. Если расстояния равны, модель выбирает цифру 8.
Модели предложили изображение ниже. Строки и столбцы пронумерованы сверху вниз и слева направо соответственно.
За одно изменение можно поменять цвет одной клетки: белый на чёрный или чёрный на белый.
Найдите расстояние от данного изображения до эталона 3.
📌 Задание 3.2 Найдите расстояние от данного изображения до эталона 8.
📌 Задание 3.3 Какую цифру выберет модель?
📌 Задание 3.4 Сколько клеток данного изображения обладают следующим свойством: изменение цвета этой клетки изменит ответ модели с 3 на 8?
📌 Задание 3.5 Может ли изменение клетки, цвет которой совпадает в двух эталонах, изменить ответ модели?
Напишите только цифру верного ответа.
1 — ДА
2 — НЕТ
📌 Задание 3.6 Правило выбора при равенстве расстояний изменили: теперь в случае равенства модель выбирает цифру 3. Какое минимальное число клеток данного изображения нужно изменить, чтобы модель выбрала цифру 8?
📌 Задание 4.1 Приёмная комиссия обрабатывает заявки. Каждая заявка описывается четырьмя признаками со значениями «да» или «нет»:
• А — есть подпись;
• Б — оплачен взнос;
• В — заявка подана онлайн;
• Г — приложена фотография.
Заявку принимают ровно тогда, когда одновременно есть подпись и оплачен взнос. Признаки В и Г на верный ответ не влияют. Всего существует 16 различных заявок — по одной для каждого набора значений признаков.
Сравниваются две модели искусственного интеллекта. Модель П отвечает «принять» ровно тогда, когда заявка подана онлайн. Модель Р отвечает «принять» ровно тогда, когда есть подпись.
Сколько заявок должно быть принято по правилам приёмной комиссии?
📌 Задание 4.2 Приёмная комиссия обрабатывает заявки. Каждая заявка описывается четырьмя признаками со значениями «да» или «нет»:
• А — есть подпись;
• Б — оплачен взнос;
• В — заявка подана онлайн;
• Г — приложена фотография.
Заявку принимают ровно тогда, когда одновременно есть подпись и оплачен взнос. Признаки В и Г на верный ответ не влияют. Всего существует 16 различных заявок — по одной для каждого набора значений признаков.
Сравниваются две модели искусственного интеллекта. Модель П отвечает «принять» ровно тогда, когда заявка подана онлайн. Модель Р отвечает «принять» ровно тогда, когда есть подпись.
Сколько заявок примет модель П?
📌 Задание 4.3 Приёмная комиссия обрабатывает заявки. Каждая заявка описывается четырьмя признаками со значениями «да» или «нет»:
• А — есть подпись;
• Б — оплачен взнос;
• В — заявка подана онлайн;
• Г — приложена фотография.
Заявку принимают ровно тогда, когда одновременно есть подпись и оплачен взнос. Признаки В и Г на верный ответ не влияют. Всего существует 16 различных заявок — по одной для каждого набора значений признаков.
Сравниваются две модели искусственного интеллекта. Модель П отвечает «принять» ровно тогда, когда заявка подана онлайн. Модель Р отвечает «принять» ровно тогда, когда есть подпись.
Сколько заявок примет модель Р?
📌 Задание 4.4 Приёмная комиссия обрабатывает заявки. Каждая заявка описывается четырьмя признаками со значениями «да» или «нет»:
• А — есть подпись;
• Б — оплачен взнос;
• В — заявка подана онлайн;
• Г — приложена фотография.
Заявку принимают ровно тогда, когда одновременно есть подпись и оплачен взнос. Признаки В и Г на верный ответ не влияют. Всего существует 16 различных заявок — по одной для каждого набора значений признаков.
Сравниваются две модели искусственного интеллекта. Модель П отвечает «принять» ровно тогда, когда заявка подана онлайн. Модель Р отвечает «принять» ровно тогда, когда есть подпись.
Разделим все заявки на четыре группы. Определите размеры этих групп в каждом из случаев.
1. Обе модели ответили верно
2. Только модель П ответила верно
3. Только модель Р ответила верно
4. Обе модели ошиблись
Ответ на каждый пункт вводите в отдельное поле для ответа в том порядке, в котором они даны в задании.
📌 Задание 4.5 Приёмная комиссия обрабатывает заявки. Каждая заявка описывается четырьмя признаками со значениями «да» или «нет»:
• А — есть подпись;
• Б — оплачен взнос;
• В — заявка подана онлайн;
• Г — приложена фотография.
Заявку принимают ровно тогда, когда одновременно есть подпись и оплачен взнос. Признаки В и Г на верный ответ не влияют. Всего существует 16 различных заявок — по одной для каждого набора значений признаков.
Сравниваются две модели искусственного интеллекта. Модель П отвечает «принять» ровно тогда, когда заявка подана онлайн. Модель Р отвечает «принять» ровно тогда, когда есть подпись.
Качество моделей сравнивают на валидационной выборке — некотором наборе различных заявок. Какое наибольшее число заявок может содержать валидационная выборка, на которой модель П ошибается реже, чем модель Р?
📌 Задание 5 Модель должна обработать 9 запросов, длины которых равны 34, 8, 17, 11, 46, 21, 4, 41 и 20 токенам соответственно.
Вы можете произвольным образом разбить эти запросы на 3 батча (группы) по 3 запроса в каждом так, чтобы каждый запрос попал ровно в один из батчей. Вычислительные затраты на обработку одного батча равны длине самого длинного запроса в этом батче.
Найдите минимальные суммарные вычислительные затраты на обработку всех запросов при оптимальном разбиении на батчи.
📌 Задание 6 Кластеризация без ML
Ограничение времени: 3000 мс. Ограничение памяти: 256 МБ.
Кластеризация — это разбиение объектов на группы, кластеры, так, чтобы похожие объекты попадали в одну группу, а непохожие — в разные. Обычно кластеры ищет алгоритм, но в этой задаче разбиение складывается само, и его остаётся только измерить.
Биологи выращивают колонию бактерий в стопке из k одинаковых слоёв питательной среды. Каждый слой — прямоугольник из n строк и m столбцов клеток, и в каждой клетке живёт ровно одна бактерия: синяя, красная или зелёная. Все слои устроены одинаково: в клетке (i, j) любого слоя живёт бактерия одного и того же цвета.
Две бактерии соседние, если их клетки имеют общую грань: это либо соседи по стороне в одном слое, либо клетки с одинаковыми координатами в соседних слоях. Соседние бактерии срастаются в двух случаях:
• обе красные или обе зелёные и лежат в одном слое;
• обе синие и лежат в соседних слоях.
Других срастаний нет; в частности, две синие бактерии одного слоя не срастаются никогда. Кластер — это множество бактерий, связанных срастаниями, возможно, через цепочку других бактерий.
Граница кластеров состоит из единичных граней клеток, каждая из которых либо разделяет бактерии из разных кластеров, либо отделяет бактерию от внешнего пространства. Помогите биологам посчитать, из скольких граней состоит граница кластеров.
Входные данные
В первой строке даны три целых числа n, m и k — количество строк и столбцов в слое и количество слоёв (1 ≤ n, m ≤ 2 · 10⁵; n · m ≤ 2 · 10⁵; 1 ≤ k ≤ 1000).
В каждой из следующих n строк дано по m символов, каждый из которых равен B, R или G. j-й символ i-й из этих строк задаёт цвет бактерии в клетке (i, j) каждого слоя: B — синяя, R — красная, G — зелёная.
Выходные данные
Выведите одно целое число — количество граней в границе кластеров.
Система оценки
Тесты из условия не оцениваются. Помимо них в задаче 12 тестов, каждый из которых оценивается в 1 балл.
Пример 1
Входные данные:
2 3 2
RRG
RBG
Выходные данные:
45
Пример 2
Входные данные:
1 1 1
G
Выходные данные:
6
Пример 3
Входные данные:
1 2 1
BB
Выходные данные:
11
Примечание
В первом примере колония состоит из двух слоёв, каждый из них такой:
RRG
RBG
Сначала посчитаем грани внутри каждого слоя. Наружу по периметру выходят 2 · (2 + 3) = 10 граней. Внутри слоя границей являются 4 грани: между R и G в первой строке, между R и B и между B и G во второй строке и между R и B в среднем столбце. Две клетки R в первом столбце срослись, и грани между ними в границе нет. Получается 14 граней на слой, 28 на два слоя.
Теперь грани между слоями. Снизу и сверху колонии наружу выходят по 6 граней. Между слоями лежат 6 граней, и границей являются 5 из них: только в клетке B синие бактерии срослись в вертикальную нить. Всего 6 + 6 + 5 = 17 граней, а ответ равен 28 + 17 = 45.