Представим, что число меняется по следующему алгоритму: если число чётно, его делят на 2, а если нечётно — вычитают 1. Из числа N после выполнения четырёх шагов алгоритма получилось число 12.

Определите наименьшее возможное значение N.

Модель искусственного интеллекта различает цифры 0 и 1 по следующему алгоритму: если линия, которой нарисована цифра, ограничивает некоторую часть плоскости, цифра определяется как 0, иначе — как 1. В частности, цифру 0 она определяет как 0, а цифру 1 — как 1. Полученная последовательность цифр интерпретируется как число в двоичной системе счисления. Какое число модель определит по записи 293676? Ответ запишите в десятичной системе счисления.

Модель искусственного интеллекта различает пиксельные цифры 3 и 8. Для каждой цифры у модели есть эталонное изображение:

Расстоянием между двумя изображениями называется число клеток, цвет которых на этих изображениях различается. Модель сравнивает новое изображение с обоими эталонами и выбирает цифру с меньшим расстоянием. Если расстояния равны, модель выбирает цифру 8.

Модели предложили изображение ниже. Строки и столбцы пронумерованы сверху вниз и слева направо соответственно.

За одно изменение можно поменять цвет одной клетки: белый на чёрный или чёрный на белый.

Найдите расстояние от данного изображения до эталона 3.

Найдите расстояние от данного изображения до эталона 8.

Какую цифру выберет модель?

Сколько клеток данного изображения обладают следующим свойством: изменение цвета этой клетки изменит ответ модели с 3 на 8?

Может ли изменение клетки, цвет которой совпадает в двух эталонах, изменить ответ модели?
Да
Нет

Правило выбора при равенстве расстояний изменили: теперь в случае равенства модель выбирает цифру 3. Какое минимальное число клеток данного изображения нужно изменить, чтобы модель выбрала цифру 8?

Приёмная комиссия обрабатывает заявки. Каждая заявка описывается четырьмя признаками со значениями «да» или «нет»:

• А — есть подпись;
• Б — оплачен взнос;
• В — заявка подана онлайн;
• Г — приложена фотография.

Заявку принимают ровно тогда, когда одновременно есть подпись и оплачен взнос. Признаки В и Г на верный ответ не влияют. Всего существует 16 различных заявок — по одной для каждого набора значений признаков.
Сравниваются две модели искусственного интеллекта. Модель П отвечает «принять» ровно тогда, когда заявка подана онлайн. Модель Р отвечает «принять» ровно тогда, когда есть подпись.

Сколько заявок должно быть принято по правилам приёмной комиссии?

Сколько заявок примет модель П?

Сколько заявок примет модель Р?

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

Качество моделей сравнивают на валидационной выборке — некотором наборе различных заявок. Какое наибольшее число заявок может содержать валидационная выборка, на которой модель П ошибается реже, чем модель Р?

Модель должна обработать 9 запросов, длины которых равны 34, 8, 17, 11, 46, 21, 4, 41 и 20 токенам соответственно.
Вы можете произвольным образом разбить эти запросы на 3 батча (группы) по 3 запроса в каждом так, чтобы каждый запрос попал ровно в один из батчей. Вычислительные затраты на обработку одного батча равны длине самого длинного запроса в этом батче.

Найдите минимальные суммарные вычислительные затраты на обработку всех запросов при оптимальном разбиении на батчи.

Кластеризация без ML

Ограничение по времени: 3 секунды
Ограничение по памяти: 256 мегабайт

Кластеризация — это разбиение объектов на группы, кластеры, так, чтобы похожие объекты попадали в одну группу, а непохожие — в разные. Обычно кластеры ищет алгоритм, но в этой задаче разбиение складывается само, и его остаётся только измерить.
Биологи выращивают колонию бактерий в стопке из k одинаковых слоёв питательной среды. Каждый слой — прямоугольник из n строк и m столбцов клеток, и в каждой клетке живёт ровно одна бактерия: синяя, красная или зелёная. Все слои устроены одинаково: в клетке (i, j) любого слоя живёт бактерия одного и того же цвета.
Две бактерии соседние, если их клетки имеют общую грань: это либо соседи по стороне в одном слое, либо клетки с одинаковыми координатами в соседних слоях. Соседние бактерии срастаются в двух случаях:

• обе красные или обе зелёные и лежат в одном слое;
• обе синие и лежат в соседних слоях.

Других срастаний нет: в частности, две синие бактерии одного слоя не срастаются никогда.
Кластер — это множество бактерий, связанных срастаниями, возможно, через цепочку других бактерий.
Граница кластеров состоит из единичных граней клеток, каждая из которых либо разделяет бактерии из разных кластеров, либо отделяет бактерию от внешнего пространства.

Помогите биологам посчитать, из скольких граней состоит граница кластеров.

Формат входных данных
В первой строке даны три целых числа n, m и k — количество строк и столбцов в слое и количество слоёв (1 <= n, m <= 2 * 10^5; n * m <= 2 * 10^5; 1 <= k <= 1000).
В каждой из следующих n строк дано по m символов, каждый из которых равен B, R или G. j-й символ i-й из этих строк задаёт цвет бактерии в клетке (i, j) каждого слоя: B — синяя, R — красная, G — зелёная.

Формат выходных данных
Выведите одно целое число — количество граней в границе кластеров.

Система оценивания
Тесты из условия не оцениваются. Помимо них в задаче 12 тестов, каждый из которых оценивается в 1 балл.

Замечание
В первом примере колония состоит из двух слоёв, каждый из них такой:
R R G
R B G
Сначала посчитаем грани внутри каждого слоя. Наружу по периметру выходят 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.

Примеры
Ввод:
2 3 2
RRG
RBG
Вывод:
45

Ввод:
1 1 1
R
Вывод:
6

Ввод:
1 2 1
BB
Вывод:
11