На предприятии каждой изготовленной детали присваивается серийный номер, состоящий из 431 символа. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным количеством бит. Известно, что для хранения 154789 серийных номеров требуется не менее 43 Мбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.

Составим неравенство для поиска кол-ва бит на символ: (431 * i / 8) * 154789 >= 43 * \(2^{20}\) Получаем 6 бит (минимальное). Мощность алфавита N = \(2^6\) лежит в диапазоне от 33 до 64, берем минимальную 33.

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов \(A=\{a_{0},a_{1},…,a_{n–1}\}\)), включая специальный пустой символ \(a_{0}\). Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний \(Q=\{q_{0},q_{1},…,q_{n–1}\}\). В начальный момент времени головка находится в начальном состоянии \(q_{0}\). На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии. Программа работы исполнителя МТ задаётся в табличном виде. \(a_{0}\) | \(a_{1}\) | ... \(q_{0}\) | команда | команда | ... \(q_{1}\) | команда | команда | ... ... | ... | ... | ... В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении \(i\)-й строки и \(j\)-го столбца находится команда, которую выполняет МТ, когда головка обозревает \(j\)-й символ, находясь в \(i\)-м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой. Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов \(«L»\), \(«R»\), \(«N»\), \(«S»\). Символы \(«L»\) и \(«R»\) означают сдвиг в левую или правую ячейки соответственно, \(«N»\) – отсутствие сдвига, \(«S»\) – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды. Например, команда \(0, L, q_{3}\) выполняется следующим образом: в текущую ячейку записывается символ \(«0»\), затем головка сдвигается в соседнюю слева ячейку и переходит в состояние \(q_{3}\). Выполните задание На ленте исполнителя МТ в соседних ячейках записана последовательность из 1000 символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами \(«λ»\). В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности. Программа работы исполнителя: \(λ\) | \(2\) | \(1\) | \(0\) \(q_0\) | \(λ, R, q_1\) \(q_1\) | \(λ, S, q_{1}\) | \(0, R, q_{1}\) | \(2, R, q_{1}\) | \(1, R, q_{1}\) После выполнения программы на ленте оказались цифры, сумма которых равна 437. Определите максимально возможное число двоек в исходной последовательности.

Рассмотрим программу исполнителя МТ. Так как символ «2» в итоговой строке будет заменен на символ «0», то эти значения не пойдут в итоговую сумму. Следовательно, на исходной ленте надо расположить максимальное число «2», оставив место под символы, которые дадут сумму 437 после выполнение программы и при этом, их количество будет минимальным. Больший вклад в итоговую сумму дадут символы «1», так как они будут заменены на символы «2», всего их будет 437 // 2 = 218 и еще один символ «0», который будет заменен на символ «1». Всего 218 + 1 = 219 символов «0» и «1». Тогда максимально возможное число двоек в исходной последовательности 1000–219 = 781.