ИТМО

Дан фрагмент таблицы в режиме отображения формул:

(тут должно быть изображение)

Формулу из ячейки A3 скопировали во все ячейки диапазона A3:A30. Формулу из ячейки B2 поместили во все ячейки диапазона B2:J30. В ячейки B1 и C1 поместили некоторые числа, в результате чего в ячейке A1 отобразилось число 69. Определите, какие числа были помещены в эти ячейки. В качестве ответа укажите через пробел два числа — число из ячейки B1 и число из ячейки C1.

Таблица соответствия имён используемых функций:

Пример ввода ответа: 5 7

Известно, что в некоторой сети зарегистрировано 15 узлов с различными адресами. Некоторые из этих узлов также управляют подсетями.

Восстановите карту сети и определите, сколько промежуточных узлов посетит сообщение, передаваемое из узла №2 в узел №13 по кратчайшему пути.

В ответе укажите целое число.

Дан алгоритм:

(тут должно быть изображение)

На вход данному алгоритму была подана строка A из 16 десятичных цифр, массив B изначально заполнен 0. В результате алгоритм вывел следующий результат:

Восстановите строку A.

Примечание: операция % означает взятие по модулю.

Робот перемещается по полю 10×10 клеток. В свой ход робот может пойти на 1 клетку вверх, вправо, вниз или влево. Известен алгоритм перемещения робота:

• Выполнить ход в заданном направлении, если в этом направлении есть клетка, эта клетка не была посещена роботом и сумма координат этой клетки не кратна X.
• Увеличить число X на 1. Если X = 12, изменить значение X на 2.
• Пометить текущую клетку робота как посещённую (повторная пометка не является ошибкой, если робот пропустил свой ход).
• Определить направление следующего шага согласно таблице:

Если робот не может переместиться в свой ход, он может его пропустить (т.е. не совершать перемещение, выполнив все остальные шаги алгоритма). Однако робот может пропустить максимум 4 хода подряд, иначе он проигрывает. Определите, через сколько перемещений робот проиграет, если начальное значение X = 2 и робот начинает своё движение в клетке с координатами { 3; 7 } и делает первый ход вправо.

Строки и столбцы поля нумеруются с ноля, первая координата соответствует номеру строки, вторая — номеру столбца, координаты { 0; 0 } имеет верхний левый угол, координаты { 9; 9 } — правый нижний.

В ответе укажите целое число.

Два набора значений переменных A, B и C называют не эквивалентными, если значение хотя бы одной переменной различается.

Дано логическое выражение. В данном выражении A, B и C — логические переменные, F — функция от этих переменных.

\((((A \to B) \to C) \to ((A \to C) \to B)) \to F\)

Данное логическое выражение истинно при 8 не эквивалентных наборах значений переменных A, B, C, а F — при 7 таких наборах. Определите функцию F, если известно, что функция F содержит все 3 логические переменные и не более чем 3 логические операции. Если таких функций несколько — запишите любую из них.

В ответе запишите формулу, которая содержит логические переменные A, B и C (все 3) и не более чем три логические операции. Если таких функций не существует, запишите в ответ NULL.

Комментарий по вводу ответа: операнды вводятся большими латинскими буквами; логические операции обозначаются, соответственно, как not, and и or. Запись не должна содержать скобок.

Пример записи ответа: A or not B

Вася работает в графическом редакторе с поддержкой нескольких слоёв. Графический редактор настроен так, что значения цветов при наложении слоёв (за исключением фона) складываются друг с другом. В этом графическом редакторе Вася создал картину размером 1920×1080 пикселей из трёх пересекающихся цветных прямоугольников (красного, зелёного и синего) на белом фоне и сохранил её в формате True Color (по 8 бит на каждый из 3 цветовых каналов каждого пикселя). Изначально каждый из прямоугольников находился на собственном слое, однако сохранён был именно итоговый результат, полученный после наложения слоёв.

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

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

Примечание: гарантируется, что все 3 прямоугольника имеют ненулевую площадь и все пересечения непусты.

В ответе укажите целое число.

Дано число \(A = (a_1 a_2 \ldots a_k)_N\). В данном числе \(a_1 \ldots a_k\) — \(K\) цифр числа, \(N\) — основание системы счисления. Известно, что и каждая из цифр \(a_1 \ldots a_k\), и \(N\), будучи переведёнными в десятичную систему счисления, окажутся равны некоторой степени некоторого числа \(X\) (число \(X\) идентично для всех, степень — различается).

Известно, что все цифры числа различны и записаны по возрастанию, а \(N\) — наименьшее возможное. Определите максимальное количество идущих подряд нолей в числе \(B\), получаемом в результате перевода числа \(A\) в систему счисления с основанием \(X\), если \(K = 1000\).

В ответе укажите целое число.

Корнедуд — маг-архивариус Гильдии Каталогов. В его архиве заклинания лежат в каталоге: у каждого заклинания есть значение силы. По уставу архива Корнедуд может просматривать только первые три заклинания от начала каталога — это называется «тройной просмотр». Его работа заключается в проведении некоторого ритуала.

Силы заклинаний:

4, 3, 5, 3, 4, 3, 2, 2, 4, 3, 5, 3, 4, 3, 2, 2, 4, 3, 5, 3, 4, 3, 2, 2, 4, 3, 5, 3, 4, 3, 2, 2

Ритуал выполняется 20 раз:

• Корнедуд смотрит только на первые 3 заклинания.
• Из этих трёх он выбирает самое сильное заклинание. Если максимумов несколько — выбирает то, которое стоит раньше среди этих трёх. Его сила = t. Это заклинание вычёркивается из каталога (удаляется).
• Каталог смещается:
  • если t чётное — циклически сдвигаем вправо на t позиций;
  • если t нечётное — циклически сдвигаем влево на t позиций.

Циклический сдвиг на t позиций означает, что элементы, выходящие за край каталога, возвращаются с другой стороны, сохраняя порядок. Например, для каталога [1, 2, 3, 4, 5] циклический сдвиг влево на 2 позиции даёт [3, 4, 5, 1, 2], а циклический сдвиг вправо на 2 позиции — [4, 5, 1, 2, 3]. После сдвига началом каталога считается первый элемент получившегося списка.

В ответ следует указать единственное число: какая сила будет у двадцатого выбранного заклинания.

В учебной группе M3107 ребята сдают выполненные работы в электронную систему. Работа каждого студента характеризуется тремя числами:

• Score — базовый балл за работу по шкале от 0 до 100 (чем больше, тем лучше). Это то, сколько поставил преподаватель за качество решения без штрафов.
• Delay — опоздание в минутах: если студент сдал вовремя, то Delay = 0; если сдал на 7 минут позже дедлайна (времени сдачи), то Delay = 7.
• Attempts — количество попыток сдачи (сколько раз отправлял решение). Если сдал с первого раза — Attempts = 1. Если пересдавал/перезагружал ещё 2 раза — Attempts = 3.

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

• за каждую минуту опоздания снимается 2 балла;
• за каждую дополнительную попытку (кроме первой) снимается 5 баллов;
• итоговый балл не может быть меньше 0.

Рейтинг строится по следующим правилам:

• больше Final — студент выше в рейтинге;
• если Final одинаковый — выше тот, у кого меньше Delay;
• если и Delay одинаковый — выше тот, у кого меньше Attempts;
• если всё одинаково — сравниваем ID, выше будет тот, у кого ID меньше.

Вам дан список из 10 студентов. Каждый студент описывается строкой из 4 целых чисел, записанных последовательно через пробел: ID, Score, Delay, Attempts.

В ответ запишите первые 5 значений ID в рейтинге (сверху вниз), через пробел.

Дана блок-схема алгоритма:

(тут должно быть изображение)

На вход алгоритму дали следующую строку:

• Её длина = 7.
• Состоит только из символов «a» и «b».
• Начинается с символа «a».

Нужно выяснить, какую строку подали на вход, если на выходе мы получили следующий массив arr: [3, 2, 2, 2, 1, 1, 1].

Примечание. Обозначения некоторых операций:

• [k]*n — создаётся массив из n элементов, каждый из которых равен k. Пример: [3]*5 = [3, 3, 3, 3, 3].
• arr[i:j] — берётся подпоследовательность с i-го элемента (включительно) по j-й (не включительно). Для строк — берётся подстрока с i-го символа (включительно) по j-й (не включительно).
• len(s) — возвращает длину строки (количество символов в строке).

Вам дана экосистема, в состоянии которой происходят циклические изменения. Она обладает следующими параметрами:

• O — кислород в конце итерации.
• A — количество водорослей типа A в конце итерации.
• B — количество водорослей типа B в конце итерации.
• U — количество улиток в конце итерации.
• K — количество креветок в конце итерации.

После каждой итерации мы записываем новое состояние системы. Состояние системы на каждой итерации меняется по следующим правилам (именно в таком порядке):

1) Водоросли добавляют кислород:

• если O ≤ 25, то \( O_{tmp} = O + 4 \cdot A + 7 \cdot B \);
• если O > 25, то \( O_{tmp} = O + 4 \cdot A \) (водоросли B «не работают»).

\( O_{tmp} \) — это сколько кислорода получилось после работы водорослей на данной итерации, до того как улитки и креветки начали дышать.

2) Улитки и креветки тратят кислород:

\( O_{after} = O_{tmp} - 3 \cdot U - 1 \cdot K \).

\( O_{after} \) — это сколько кислорода осталось в конце итерации после дыхания животных (то есть после того, как улитки и креветки потратили кислород).

3) Проверка условий:

• Если \( O_{after} < 8 \) — креветки погибают, и экосистема не может дальше функционировать.
• Если \( O_{after} > 40 \) — экосистема перенасыщается и не может дальше функционировать.

4) Выбираем ровно одно действие \( d_i \):

• \( d_i = 0 \) — ничего не делать;
• \( d_i = 1 \) — посадить 1 водоросль A (A увеличится на 1);
• \( d_i = 2 \) — посадить 1 водоросль B (B увеличится на 1);
• \( d_i = 3 \) — убрать 1 улитку (можно только если улиток было хотя бы 1).

В конце итерации получаем следующие значения:

• \( O_i = O_{after} \)
• \( K_i = K \)
• \( A_i = A + 1 \) (если \( d_i = 1 \), иначе A)
• \( B_i = B + 1 \) (если \( d_i = 2 \), иначе B)
• \( U_i = U - 1 \) (если \( d_i = 3 \), иначе U)

Вам нужно выбрать действия на каждой итерации. Выбирайте действия так, чтобы экосистема прожила максимальное количество итераций. Итерация i считается прожитой, даже если после проверки условий на этой итерации экосистема перестаёт функционировать. В ответ запишите максимальное количество итераций, которое сможет прожить экосистема.

Стартовые данные: \( O_0 = 31,\ A_0 = 3,\ B_0 = 0,\ U_0 = 7,\ K_0 = 6 \).

В ИТМО запустили внутренний сервис «ПропускИТМО» — через него подают заявки на разовый вход: гости на хакатон, ассистенты на семинар, подрядчики, доставщики и т. п.

Все эти заявки стекаются на пост охраны конкретного корпуса. На посту стоит старенький принтер, который подключён к локальной системе и печатает не по одной заявке, а пакетами, чтобы охранник мог сразу выдать несколько пропусков и отметить людей в журнале. Пакет — это накопленная очередь заявок, которую принтер печатает одним разом (максимум 6 заявок). Очистить пакет — означает удалить из него все заявки, то есть сделать пакет пустым.

На пост охраны корпуса ИТМО за одну смену пришли 24 заявки на печать разовых пропусков в таком порядке:

Правила печати:

• Принтер печатает пакетами максимум по 6 заявок.
• Заявки обрабатываются поочерёдно (сверху вниз).
• Множество сигнальных букв: {Е, О, Г}.
• Если в текущем пакете в какой-то момент встречаются 3 подряд идущие фамилии, которые начинаются на буквы из описанного множества сигнальных букв (например, подряд шли фамилии, начинающиеся на Е, О и Е соответственно), то принтер печатает накопленный пакет сразу, не дожидаясь накопления 6 заявок, после чего очищает его.
• Если таких фамилий не было, но заявок уже 6, то печатаем пакет и очищаем его.
• Когда все 24 заявки обработаны и остаются ненапечатанные заявки в пакете, пакет печатается, после чего обработка списка завершается.

В ответ укажите одно число — сколько пакетов было напечатано за смену.

Имеется поле 10×10. У каждой клетки есть координата (x, y), где x — номер строки на поле, y — номер столбца на поле. Левая верхняя клетка имеет координаты (1, 1).

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

Данный алгоритм выглядит следующим образом:

• Рассматриваем клетки в любом порядке. Если в текущей клетке шаров больше, чем 1, то мы начинаем избавляться от лишних шаров по очереди. Причём действует правило: пока шар не нашёл пустую клетку или не удалился, другие шары не могут начинать перемещение.
• За один шаг шар может переместиться в любую из 4-х соседних по ребру клеток. Если на поле есть пустая клетка, шар будет стремиться в неё попасть.
• Шар может временно встать в клетку, где уже есть шары, чтобы продолжить дальше свой путь, но никакой шар, покинувший стартовую клетку, не может снова на неё вступить.
• Если на очередном шаге шар нашёл пустую клетку — он остаётся там (шар нашёл свою клетку). Клетка считается пустой, если в ней нет ни одного шара.
• Если у шара нет возможности найти пустую клетку, то он доходит до любой угловой клетки (исходные угловые клетки и любые другие угловые клетки) и удаляется вместе с ней. Это значит, что данная угловая клетка навсегда пропадает с поля, и шары, которые были в ней, соответственно тоже пропадают. Угловой считается клетка, у которой две смежные стороны не граничат с другими клетками.

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

Определите, сколько шаров на поле останется после выполнения алгоритма балансировки.

Дана строка ABCCCABBBC. Над ней выполняется следующий алгоритм:

• Если в строке чётное число букв А, то в конец строки добавляется символ А.
• Если в строке нечётное число букв А, то в конец строки добавляется символ, которого меньше всего в строке на данный момент. Например, для строки АААВВС будет добавлен символ С, получится строка АААВВСС. Если символов, которых в строке меньше всего, несколько (их количества совпадают), тогда в конец строки дописывается символ, идущий в алфавите раньше. Например, для строки AAABBCC будет добавлен символ В, так как он идёт в алфавите раньше С — в результате получится строка AAABBCCB.

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

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

В течение семестра первокурсник может находиться в одном из состояний:

• 0 — «всё хорошо»
• 1 — «всё нормально»
• 2 — «я отчисляюсь»
• 3 — «ладно, передумал»
• 4 — «семестр закрыт»

На состояние влияют события в его жизни. События бывают двух типов:

• A — «контрольная / экзамен»
• B — «сон / культурные мероприятия»

Как меняется состояние, задаётся таблицей ниже.

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

Пример, как пользоваться таблицей:

• Если студент был в состоянии 0 и случилось событие A, то по таблице он перейдёт в состояние 1.
• Если студент был в состоянии 1 и случилось событие B, то по таблице он перейдёт в состояние 2.

Изначально, при поступлении в ВУЗ, студент находится в состоянии 0.

Вам дана последовательность событий, происходивших в жизни студента:

ABBABAABABBABAABABBABAABABBABAABABBABAABABBABAABABBABAABABBABAAB

Вам нужно записать в ответ два числа через пробел:

• Конечное состояние студента после обработки всей последовательности;
• Сколько раз студент оказывался в состоянии 2 (после очередного события из последовательности).

Настя работает с детьми в кружке МОТИ и учит их архитектуре компьютера. Она объясняет кэш как «быстрый шкафчик», куда заглядывает процессор, когда ему нужно что-то взять.

Есть 5 терминов, которые описывают работу «шкафчика»:

• Ситуация, когда процессору что-то потребовалось, и это что-то оказалось в шкафчике, называется hit (попадание).
• Время, которое тратится на обращение к шкафчику при попадании (hit), называется hit time (время попадания) и измеряется в наносекундах.
• Ситуация, когда процессору понадобились данные, но в шкафчике их не оказалось, называется miss (промах) — тогда приходится идти на склад.
• Вероятность того, что при обращении к шкафчику произойдёт промах, называется miss rate (доля промахов) и выражается в процентах.
• Время, которое дополнительно тратится при промахе на поход на склад, называется miss penalty (штраф промаха) и измеряется в наносекундах.

На сегодняшнем занятии Настя говорит: «Представим, что процессор делает 100 обращений к памяти. Каждый раз он сначала заглядывает в шкафчик и тратит hit time. Если происходит промах, то в дополнение к этому времени он тратит ещё и miss penalty на поход на склад. Среднее время доступа к памяти — это общее время, потраченное на все обращения, делённое на их количество.»

После этого Настя показывает детям несколько разных шкафчиков с разными характеристиками:

Задание:

• Для каждого шкафчика найдите среднее время доступа к памяти.
• Определите, какой шкафчик самый быстрый в среднем.
• Укажите его среднее время доступа к памяти.

Формат ответа: буква самого быстрого шкафчика и его среднее время доступа к памяти, записанные слитно, без пробелов. Среднее время указывается в наносекундах (ns), десятичная дробь записывается через точку (например, 1.5). Округлять до одного знака после запятой. Пример записи ответа: «A1.1».

Используя поиск информации в глобальной сети Интернет, определите, что является ключевым отличием наиболее распространённой модифицированной Гарвардской архитектуры, используемой во многих современных процессорах (например, в ядрах ARM), от её «чистой» формы.

1. Память для инструкций и память для данных физически и логически полностью разделены.
2. Наличие на уровне процессора раздельных, независимых кэшей для инструкций и данных, которые работают с единым адресным пространством основной оперативной памяти (ОЗУ).
3. Использование только одного канала для обмена с памятью, как в архитектуре фон Неймана.
4. Отказ от принципа хранимой программы (принципа фон Неймана), согласно которому команды и данные хранятся в одной и той же памяти и обрабатываются процессором одинаково.

В ответ запишите номер правильного варианта.

Татьяна Олеговна делает брелоки из бисера. Брелоки представляют собой нить, на которую нанизаны 12 бусин. Татьяна использует только белые, серые и чёрные бусины. С одной стороны этой нити расположено крепление для ключей. Раньше Татьяна записывала схемы брелоков с помощью последовательностей нулей, единиц и двоек, где «0» означал белую бусину, «1» — чёрную, а «2» — серую. Крепление для ключей всегда предполагается в левой части схемы.

Пример схемы брелока, состоящего из 10 чёрных бусин и 2 белых, в котором часть брелока, ближайшая к креплению, чёрная, а вторая часть — белая: 111111111100 — итого запись содержит 12 символов, по одному на каждую бусину.

Но вот однажды Татьяна придумала, как можно сократить запись: вместо того, чтобы записывать подряд 10 «1», она решила записывать число бусин одного цвета, которые идут подряд (например, 10), ставить дефис «-», после чего записывать цвет бусинки («1» — чёрный, «0» — белый, «2» — серый). Между такими блоками ставится запятая. Подряд не может записываться два блока, описывающих бусины одного и того же цвета, — они должны быть объединены в один блок. В блоке не может быть 0 или отрицательное число бусин. Таким образом, запись схемы брелока из примера выше сокращается до 10-1,2-0 — итого 8 символов, что на 4 символа меньше исходной записи.

Однако выяснилось, что в некоторых случаях новая запись становится даже длиннее, чем исходная, например брелок из чередующихся белых и чёрных бусин. Исходная форма записи: 010101010101 — 12 символов. Новая форма записи: 1-0,1-1,1-0,1-1,1-0,1-1,1-0,1-1,1-0,1-1,1-0,1-1 — 47 символов.

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

Склад 7×7: стоят 7 стеллажей в ряд, у каждого стеллажа 7 полок по высоте. На каждой полке изначально лежит от 0 до 3 ящиков. Стеллажи нумеруются начиная с 1. Робот начинает со стеллажа 1 и двигается по столбцам слева направо. Приехав к очередному стеллажу, он проходит полки сверху вниз и для каждой полки пытается увеличить число ящиков на 1: если на полке меньше 5, добавляет один; если уже 5, пропускает и идёт дальше. Максимальная вместимость каждой полки — 5 ящиков.

Если в текущем стеллаже в какой-то момент оказалось 3 полки со значением 5, робот убирает все ящики с этого стеллажа (обнуляет его). После завершения визита робот едет к следующему стеллажу; когда робот прошёл все стеллажи слева направо, он возвращается к первому и продолжает руководствоваться теми же правилами, пока не израсходует заданное число ходов. Ход — это один визит к одному стеллажу (полная обработка стеллажа сверху вниз).

Изначальная конфигурация полок дана ниже (строки — полки сверху вниз, столбцы — стеллажи слева направо):

Всего робот делает 14 ходов, после чего останавливается. В ответ укажите одно число: сколько раз за эти 14 ходов произойдёт обнуление какого-либо стеллажа.

Внутри кампуса ИТМО настроили систему доставки между разными корпусами; для сокращения их решили обозначать цифрами, начиная с единицы. Корпуса соединены односторонними дорогами, по данным дорогам можно двигаться лишь в одном направлении. По этим дорогам ездит один курьер-робот. Им по очереди управляют два игрока: сначала 1 ход делает Света, потом 1 ход делает Богдан, потом снова Света и т. д. В начале игры робот стоит в корпусе 1.

За один ход игрок обязан выбрать одну из исходящих из текущего корпуса дорог и перевезти робота по ней в следующий корпус. Важный момент: т. к. при создании системы старались сэкономить деньги, у робота оказались плохие колёса, из-за этого после того, как он проезжает по выбранной дороге, она становится непригодной для дальнейшей эксплуатации и больше никогда не может быть использована.

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

Схема соединения корпусов дорогами:

(тут должно быть изображение)

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

Кто из игроков может победить в этой игре независимо от ходов противника, и какое максимальное количество его ходов ему может на это потребоваться? В ответ запишите через пробел два числа: сначала номер игрока (Света — 1, Богдан — 2, если невозможно сказать — 0), а затем максимальное количество ходов, которое может потребоваться этому игроку для победы.