Информатика

При регистрации в информационной системе каждому пользователю выдаётся имя длиной ровно N символов. Имя составляется из алфавита мощностью M символов. Для хранения имени отводится одинаковое для всех пользователей целое число байт, при этом используется посимвольное кодирование, а на каждый символ отводится одинаковое целое число бит. Дополнительно на каждого пользователя хранится K байт служебных сведений.

Определить объём памяти, необходимый для хранения сведений о P пользователях.

Округлять вверх придётся дважды и на разных уровнях: сначала — число бит на один символ, затем — число байт на одно имя. Типичная ошибка состоит в том, чтобы округлить итоговый объём вместо объёма одной записи; проверьте себя на примере.

Число бит на символ — наименьшее \(i\), при котором \(2^i \ge M\). Его можно получить без цикла: (M - 1).bit_length().

Ввод. Четыре целых числа, каждое на своей строке: \(N\), \(M\), \(K\) и \(P\), где \(1 \le N \le 1000\), \(1 \le M \le 10^6\), \(0 \le K \le 1000\), \(1 \le P \le 10^6\).

Вывод. Одно целое число — объём памяти в байтах.

Числовая ось разбита на ячейки шагом \(h\), начиная от нуля: ячейка с номером \(k\) занимает промежуток \(\bigl[\,k h,\ (k+1)h\,\bigr)\). Для координаты \(x\) определить номер ячейки, в которую она попадает, — двумя способами: как x // h и как int(x / h).

Координата может быть отрицательной. Найдите такие x, при которых два способа дают разные ответы, и объясните, какой из них верен.

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

Ввод. Два целых числа, каждое на своей строке: \(x\) и \(h\), где \(-10^6 \le x \le 10^6\), \(1 \le h \le 10^6\).

Вывод. Два целых числа через пробел: результат x // h и результат int(x / h).

На струне длиной L миллиметров возбуждена волна длиной λ миллиметров. Определить наибольшее число целых полуволн, укладывающихся на струне.

Полуволна равна \(\lambda/2\), поэтому число полуволн равно

\[\frac{L}{\lambda/2} = \frac{2L}{\lambda}\]

Ввод. Два целых числа, каждое на своей строке: \(L\) и \(\lambda\), где \(1 \le L \le 10^{16}\), \(1 \le \lambda \le 10^9\).

Вывод. Одно целое число — количество целых полуволн.

Аккумулятор ёмкостью Q мА·ч питает прибор, потребляющий постоянный ток I мА.

Ответить на два вопроса:

1. Сколько целых часов проработает прибор от одного полностью заряженного аккумулятора? 2. Сколько аккумуляторов потребуется, чтобы прибор проработал непрерывно T часов?

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

Ввод. Три целых числа, каждое на своей строке: \(Q\), \(I\) и \(T\), где \(1 \le Q \le 10^9\), \(1 \le I \le 10^9\), \(1 \le T \le 10^9\).

Вывод. В первой строке — число целых часов работы одного аккумулятора. Во второй — число аккумуляторов на T часов работы.

Маятник совершает одно полное колебание за T миллисекунд. Наблюдение длилось t миллисекунд, причём в начальный момент маятник только начинал колебание.

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

Ввод. В первой строке — целое \(T\), где \(1 \le T \le 10^6\). Во второй — целое \(t\), где \(0 \le t \le 10^{12}\).

Вывод. Два целых числа через пробел: число полных колебаний и остаток времени в миллисекундах.

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

Ввод. Одно целое число \(N\), где \(0 \le N \le 10^{19}\).

Вывод. Одно целое число — количество байт.

Дано трёхзначное натуральное число. Требуется вывести его разряды по отдельности, а затем сумму разрядов.

Задача отрабатывает связку операций // и %: деление на десять сдвигает число на разряд вправо, остаток от деления на десять снимает младшую цифру.

Ввод. Одно целое число \(n\), где \(100 \le n \le 999\).

Вывод. В первой строке — три числа через пробел: цифра сотен, цифра десятков, цифра единиц. Во второй строке — сумма разрядов.

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке ленты находится ровно один символ из алфавита исполнителя, включая специальный пустой символ «λ», обозначающий пустую ячейку.

Программа работы исполнителя задаётся таблицей. В первой строке таблицы перечислены все возможные символы, которые могут находиться в текущей ячейке ленты, в первом столбце — все возможные состояния головки. На пересечении i-й строки и j-го столбца таблицы находится команда, которую должна выполнить машина Тьюринга, если головка находится в состоянии, соответствующем i-й строке, и обозревает символ, соответствующий j-му столбцу. Если для некоторой пары «символ — состояние» команда в таблице отсутствует, это означает, что такая пара при работе исполнителя не встречается.

Каждая команда состоит из трёх элементов, записанных через запятую. Первый элемент — символ алфавита, который следует записать в текущую ячейку (он может совпадать с тем, который уже там записан). Второй элемент — один из символов «L», «R», «N», «S»: символы «L» и «R» означают сдвиг головки на одну ячейку влево или вправо соответственно, символ «N» означает отсутствие сдвига, а символ «S» означает, что после выполнения текущей команды работа исполнителя завершается. Сдвиг головки происходит после записи символа в текущую ячейку. Третий элемент — новое состояние, в которое переходит головка после выполнения команды.

Например, команда 0, L, q3 означает следующее: в текущую ячейку записывается символ «0», затем головка сдвигается на одну ячейку влево и переходит в состояние q3.

Выполните задание. На ленте записана последовательность из нулей и единиц; её длина равна {1}. Ячейки вне последовательности заполнены символом «λ». В начальном состоянии q0 головка обозревает ближайшую пустую ячейку справа от последовательности.

Программа работы исполнителя:

Известно, что после выполнения программы количество нулей на ленте оказалось равно {3}. Определите {4} в исходной последовательности. Ответ запишите целым числом.

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке ленты находится ровно один символ из алфавита исполнителя, включая специальный пустой символ «λ», обозначающий пустую ячейку.

Программа работы исполнителя задаётся таблицей. В первой строке таблицы перечислены все возможные символы, которые могут находиться в текущей ячейке ленты, в первом столбце — все возможные состояния головки. На пересечении i-й строки и j-го столбца таблицы находится команда, которую должна выполнить машина Тьюринга, если головка находится в состоянии, соответствующем i-й строке, и обозревает символ, соответствующий j-му столбцу. Если для некоторой пары «символ — состояние» команда в таблице отсутствует, это означает, что такая пара при работе исполнителя не встречается.

Каждая команда состоит из трёх элементов, записанных через запятую. Первый элемент — символ алфавита, который следует записать в текущую ячейку (он может совпадать с тем, который уже там записан). Второй элемент — один из символов «L», «R», «N», «S»: символы «L» и «R» означают сдвиг головки на одну ячейку влево или вправо соответственно, символ «N» означает отсутствие сдвига, а символ «S» означает, что после выполнения текущей команды работа исполнителя завершается. Сдвиг головки происходит после записи символа в текущую ячейку. Третий элемент — новое состояние, в которое переходит головка после выполнения команды.

Например, команда 0, L, q3 означает следующее: в текущую ячейку записывается символ «0», затем головка сдвигается на одну ячейку влево и переходит в состояние q3.

Выполните задание. На ленте исполнителя МТ в соседних ячейках записано двоичное представление целого положительного числа без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальном состоянии q0 головка обозревает ближайшую пустую ячейку: слева от записи, если первая команда сдвигает головку вправо (R), и справа от записи, если влево (L).

Программа работы исполнителя:

После выполнения программы на ленте оказалась двоичная запись числа {3}. Определите десятичное значение наибольшего числа, меньшего, чем {1}, которое могло быть записано на ленте до начала работы программы. Ответ запишите в десятичной системе счисления.

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке ленты находится ровно один символ из алфавита исполнителя, включая специальный пустой символ «λ», обозначающий пустую ячейку.

Программа работы исполнителя задаётся таблицей. В первой строке таблицы перечислены все возможные символы, которые могут находиться в текущей ячейке ленты, в первом столбце — все возможные состояния головки. На пересечении i-й строки и j-го столбца таблицы находится команда, которую должна выполнить машина Тьюринга, если головка находится в состоянии, соответствующем i-й строке, и обозревает символ, соответствующий j-му столбцу. Если для некоторой пары «символ — состояние» команда в таблице отсутствует, это означает, что такая пара при работе исполнителя не встречается.

Каждая команда состоит из трёх элементов, записанных через запятую. Первый элемент — символ алфавита, который следует записать в текущую ячейку (он может совпадать с тем, который уже там записан). Второй элемент — один из символов «L», «R», «N», «S»: символы «L» и «R» означают сдвиг головки на одну ячейку влево или вправо соответственно, символ «N» означает отсутствие сдвига, а символ «S» означает, что после выполнения текущей команды работа исполнителя завершается. Сдвиг головки происходит после записи символа в текущую ячейку. Третий элемент — новое состояние, в которое переходит головка после выполнения команды.

Например, команда 0, L, q3 означает следующее: в текущую ячейку записывается символ «0», затем головка сдвигается на одну ячейку влево и переходит в состояние q3.

Выполните задание. На ленте записана двоичная запись натурального числа {1} без ведущих нулей. В начальном состоянии q0 головка обозревает ближайшую пустую ячейку «λ»: слева от записи, если первая команда сдвигает головку вправо (R), и справа от записи, если влево (L). Ячейки вне записи заполнены символом «λ».

Программа работы исполнителя:

Определите число, десятичная запись которого получится на ленте после выполнения программы (ведущие нули при переводе в десятичную систему не учитываются). Ответ запишите в десятичной системе счисления.

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке ленты находится ровно один символ из алфавита исполнителя, включая специальный пустой символ «λ», обозначающий пустую ячейку.

Программа работы исполнителя задаётся таблицей. В первой строке таблицы перечислены все возможные символы, которые могут находиться в текущей ячейке ленты, в первом столбце — все возможные состояния головки. На пересечении i-й строки и j-го столбца таблицы находится команда, которую должна выполнить машина Тьюринга, если головка находится в состоянии, соответствующем i-й строке, и обозревает символ, соответствующий j-му столбцу. Если для некоторой пары «символ — состояние» команда в таблице отсутствует, это означает, что такая пара при работе исполнителя не встречается.

Каждая команда состоит из трёх элементов, записанных через запятую. Первый элемент — символ алфавита, который следует записать в текущую ячейку (он может совпадать с тем, который уже там записан). Второй элемент — один из символов «L», «R», «N», «S»: символы «L» и «R» означают сдвиг головки на одну ячейку влево или вправо соответственно, символ «N» означает отсутствие сдвига, а символ «S» означает, что после выполнения текущей команды работа исполнителя завершается. Сдвиг головки происходит после записи символа в текущую ячейку. Третий элемент — новое состояние, в которое переходит головка после выполнения команды.

Например, команда 0, L, q3 означает следующее: в текущую ячейку записывается символ «0», затем головка сдвигается на одну ячейку влево и переходит в состояние q3.

Выполните задание. На ленте записана двоичная запись натурального числа {1} без ведущих нулей. В начальном состоянии q0 головка обозревает ближайшую пустую ячейку «λ»: слева от записи, если первая команда сдвигает головку вправо (R), и справа от записи, если влево (L). Ячейки вне записи заполнены символом «λ».

Программа работы исполнителя:

Определите число, десятичная запись которого получится на ленте после выполнения программы (ведущие нули при переводе в десятичную систему не учитываются). Ответ запишите в десятичной системе счисления.

Многие старейшие шифры основаны на замене букв на числа, например, в шифре A1Z26 каждая буква заменяется на её порядковый номер в алфавите. Вдохновившись этой идеей, первоклассник Петя решил придумать свой шифр-замену. Он хочет каждую букву от <<A>> до <<R>> (первые \(18\) букв латинского алфавита) заменять на одно из чисел \(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90\). Числа выбраны так, чтобы при дешифровке легко разделить последовательность цифр на коды букв, причём весь алфавит Петя не смог использовать, ибо сотни он ещё не узнал.

Если применить один из таких шифров к строке, он получит натуральное число. Если использовать разные шифры, удовлетворяющие условию, то будут получаться разные числа.

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

Программа получает на вход непустую строку \(s\), состоящую из прописных букв латинского алфавита от <<A>> до <<R>>, длина строки не превышает 1000 символов.

Программа должна вывести одно число — шифр строки \(s\). Обратите внимание, число может быть длинным.

Решения, правильно работающие, когда строка состоит не более чем из \(4\) символов, будут оцениваться в \(20\) баллов.

Решения, правильно работающие, когда строка состоит из букв <<A>> и <<B>>, будут оцениваться в \(20\) баллов.

Решения, правильно работающие, когда строка состоит из букв от <<A>> до <<I>>, будут оцениваться в \(44\) балла.

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

Для того чтобы собрать прямоугольную грядку, нужны 4 доски. В идеале это должны быть две пары досок равной длины, тогда из них можно сложить ровный прямоугольник. Но если доски имеют неравную длину, то в одном из углов полученной грядки можно разместить пластиковый уголок: две планки длины \(r\), скреплённые под прямым углом. Уголок со стороной \(r\) позволит увеличить длины двух досок на величину, не превосходящую \(r\). Если противоположными сторонами грядки будут доски длины \(a\) и \(b\), а также \(c\) и \(d\) соответственно, то для того чтобы сделать прямоугольную грядку из этих досок, понадобится уголок размера \(\max(|a-b|, |c-d|)\) . Например, чтобы сделать грядку из досок длины 5, 7, 3, 2, понадобится уголок размера 2. На рисунке чёрным цветом изображены доски и красным цветом изображён уголок.

В сарае у Аркадия Аркадьевича нашлись \(n\) досок, \(i\)-я из которых имеет длину \(l_i\). Теперь он хочет выбрать из них четыре и сложить из них грядку таким образом, чтобы использовать уголок наименьшего размера. Помогите ему.

Первая строка входных данных содержит число \(n\) (\(4 \leq n \leq 10^5\)) — количество досок в сарае у Аркадия Аркадьевича.

Следующие \(n\) строк содержат числа \(l_1, \dots, l_n\) (\(1 \leq l_i \leq 10^9\)) — длины досок.

Программа должна сначала вывести число \(r\) — минимально возможный размер уголка.

Во второй строке выведите 4 числа \(a\), \(b\), \(c\), \(d\)  — длины досок, которые необходимо выбрать для грядки. При этом противоположными сторонами прямоугольника будут доски \(a\) и \(b\), а также \(c\) и \(d\). Если есть разные варианты выбора досок для грядки с одной и той же величиной уголка, можно вывести любой из них.

Решения, правильно работающие, когда \(n \leq 30\), будут оцениваться в 20 баллов.

Решения, правильно работающие, когда \(n \leq 100\), будут оцениваться в 45 баллов.

Решения, правильно работающие, когда \(n \leq 500\), будут оцениваться в 65 баллов.

Решения, правильно работающие, когда все \(l_i \leq 30\), будут оцениваться в 10 баллов.

Этаж здания представляет собой прямоугольник из \(n\times m\) квадратных комнат. Из каждой комнаты есть проходы в соседние комнаты. В двух комнатах находятся лестницы. Необходимо разработать план эвакуации — указать для каждой комнаты направление движения в одну из соседних комнат так, чтобы, передвигаясь по комнатам только в указанных направлениях, можно было бы достичь одной из двух лестниц, пройдя минимальное расстояние.

На рисунке изображён возможный план эвакуации для примера из условия. Комнаты с лестницами обозначены звёздочками.

Первая строка входных данных содержит число \(n\) — количество строк в плане эвакуации, \(1\le n\le 100\). Вторая строка входных данных содержит число \(m\) — количество столбцов в плане эвакуации, \(2\le m\le 100\). Следующие две строки содержат числа \(r_1\) и \(c_1\) — номера строки и столбца комнаты, в которой находится первая лестница, \(1\le r_1\le n\), \(1\le c_1\le m\). Следующие две строки содержат числа \(r_2\) и \(c_2\) — номера строки и столбца комнаты, в которой находится вторая лестница, \(1\le r_2\le n\), \(1\le c_2\le m\). Гарантируется, что \(r_1\ne r_2\) или \(c_1\ne c_2\). Строки нумеруются сверху вниз числами от 1 до \(n\), столбцы нумеруются слева направо числами от 1 до \(m\).

Программа должна вывести \(n\) строк, каждая строка должна содержать \(m\) символов. Каждый символ соответствует одной комнате. В двух комнатах с лестницами должен находиться символ <<S>> (прописная английская буква). В остальных комнатах находятся символы, указывающие направление движения:

<<<>> (символ <<меньше>>) — налево.

<<>>> (символ <<больше>>) — направо.

<<^>> (символ находится на клавише <<6>>) — вверх.

<<v>> (строчная английская буква) — вниз.

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

Решения, правильно работающие, когда \(n=1\), будут оцениваться в 20 баллов.

Решения, правильно работающие, когда \(c_1=c_2\), будут оцениваться в 20 баллов.

Решения, правильно работающие, когда лестницы находятся в двух противоположных углах здания, будут оцениваться в 20 баллов.

Даны два прямоугольника размера \(a\times b\) и \(c\times d\). Можно соединить их вместе, приложив сторону одного прямоугольника к стороне другого и склеив место соединения. Прямоугольники можно поворачивать перед склеиванием. После этого из полученной фигуры нужно вырезать квадрат со сторонами, параллельными сторонам прямоугольника. Определите максимальное возможное значение стороны квадрата.

На рисунке изображены два прямоугольника со сторонами \(8\times 3\) и \(6\times 2\), из которых можно вырезать квадрат со стороной 5 (заштрихован).

Программа получает на вход натуральные числа \(a\), \(b\), \(c\), \(d\), каждое в отдельной строке — стороны первого и второго прямоугольников. Все числа не превосходят \(10^9\).

Программа должна вывести одно целое число — максимальную возможную сторону квадрата.

В первой строке — число N, дальше N строк по шесть чисел через пробел.

Выведите, сколько строк удовлетворяют обоим условиям:

• в строке одно число повторяется трижды, а остальные три различны;
• квадрат суммы повторяющихся чисел больше квадрата суммы неповторяющихся.

Это условие взято из демоверсии ЕГЭ 2025 года. Для решения задачи напишите программу, считав входные данные с калвиатуры (а не с файла как в основном задании). Цель задания - проверить правильность написания программы.

Для хранения покадровой анимации, состоящей из \(N\) кадров одинакового размера \(640 \times 480\) пикселей, отведено 4800 Кбайт памяти без учёта заголовка файла. Изображение использует 16 цветов, для каждого пикселя также выделяется 4 бита для хранения степени прозрачности. Коды пикселей записываются один за другим без промежутков.

Определите максимально возможное значение \(N\).

В памяти объёмом 2400 Кбайт хранятся два растровых изображения без учёта заголовков файлов: первое имеет размер \(1024 \times 768\) пикселей, второе — \(512 \times 384\) пикселей. Оба изображения используют одинаковую глубину цвета, для каждого пикселя также выделяется 4 бита для хранения степени прозрачности. Коды пикселей записываются один за другим без промежутков.

Какое максимальное количество цветов (без учёта прозрачности) можно использовать в изображениях?

Для хранения покадровой анимации, состоящей из 15 кадров одинакового размера \(256 \times 192\) пикселей, отведено 720 Кбайт памяти без учёта заголовка файла. Для кодирования цвета каждого пикселя используется одинаковое количество бит, также для каждого пикселя используется 2 бита для хранения степени прозрачности. Коды пикселей записываются один за другим без промежутков.

Какое максимальное количество цветов (без учёта прозрачности) можно использовать в изображении?

Для хранения растрового изображения размером \(1280 \times H\) пикселей отведено 3750 Кбайт памяти без учёта размера заголовка файла. Изображение использует 65536 цветов, для каждого пикселя также выделяется 8 бит для хранения степени прозрачности. Коды пикселей записываются один за другим без промежутков.

Определите максимально возможное значение \(H\).