Информатика

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов $$A = \{a0, a1, ..., a_{n-1}\}$$), включая специальный пустой символ a0. Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний $$Q = \{q0, q1, ..., q_{n-1}\}$$. В начальный момент времени головка находится в начальном состоянии q0.

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может изменить символ в текущей ячейке и переместиться в соседнюю ячейку слева или справа от неё. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.

Программа работы исполнителя МТ задаётся в табличном виде.

	a0	a1	...	an-1
q0	команда	команда	...	команда
q1	команда	команда	...	команда
...	...	...	...	...
qn-1	команда	команда	...	команда

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

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

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

Приведём пример выполнения программы, заданной таблично.

На ленте записано неизвестное ненулевое количество расположенных подряд в соседних ячейках символов «Z», все остальные ячейки ленты заполнены пустым символом «λ». В начальный момент времени головка находится на неизвестном расстоянии слева от самого левого символа «Z».

Программа

	λ	Z
q0	λ, R, q1
q1	λ, R, q1	X, R, q2
q2	λ, S, q2	X, R, q2

заменяет на ленте все символы «Z» на «X» и останавливает исполнителя в первой ячейке справа от последовательности символов «X».

Выполните задание.

На ленте в соседних ячейках записано двоичное представление числа 2027 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей слева от последовательности ячейке.

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

	λ	0	1
q0	λ, R, q1
q1	0, R, q2	0, R, q1	1, R, q1
q2	0, R, q3
q3	λ, S, q3

Определите результат работы программы. В ответе запишите получившееся на ленте число в десятичной системе счисления.

На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры и символы из 250-символьного специального алфавита. В базе данных каждый серийный номер занимает одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что 65 536 серийных номеров занимают более 20 Мбайт памяти.

Определите минимально возможную длину серийного номера.

67С помощью текстового редактора определите, сколько раз встречается отдельное слово «Не» или «не» в тексте глав XII и XIII романа И.С. Тургенева «Отцы и дети».

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

Все шестибуквенные слова, составленные из букв Г, Р, А, Н, И, Т, записаны в алфавитном порядке и пронумерованы.

Вот начало списка:

1. АААААА
2. АААААГ
3. АААААИ
4. АААААН
5. АААААР
6. АААААТ

......

Определите, под каким номером в этом списке стоит последнее слово с нечётным номером, которое не начинается с букв Р или Т и при этом содержит в своей записи ровно одну букву Р.

Примечание. Слово – последовательность идущих подряд букв, не обязательно осмысленная.

Прибор автоматической фиксации нарушений правил дорожного движения делает цветные фотографии размером 1280×960 пикселей, используя палитру из 8192 цветов. Для передачи снимки группируются в пакеты по 300 штук.

Определите размер одного пакета фотографий в Мбайт.

В ответе запишите целую часть полученного числа.

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует 6 команд: Поднять хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Назад n (где n – целое число), вызывающая передвижение в противоположном голове направлении; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке, Налево m (где m – целое число), вызывающая изменение направления движения на m градусов против часовой стрелки.

Запись Повтори k [Команда1 Команда2 ... КомандаS] означает, что последовательность из S команд повторится k раз.

Черепахе был дан для исполнения следующий алгоритм:

Повтори 6 [Вперёд 20 Направо 90 Вперёд 24 Направо 90]
Поднять хвост
Вперёд 7 Направо 90 Вперёд 9 Налево 90
Опустить хвост
Повтори 6 [Вперёд 26 Направо 90 Вперёд 10 Направо 90]

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

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Строится троичная запись числа N.

2. Далее эта запись обрабатывается по следующему правилу:

Полученная таким образом запись является троичной записью искомого числа R.

3. Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа \(8_{10} = 22_3\) результатом является число \(22110_3 = 228_{10}\), а для исходного числа \(9_{10} = 100_3\) это число \(10000_3 = 81_{10}\).

Укажите минимальное чётное число R, большее 405, которое может быть получено с помощью описанного алгоритма.

В ответе запишите это число в десятичной системе счисления.

По каналу связи передаются сообщения, содержащие только цифры 2, 3, 4, 5 и четыре знака арифметических действий (+, −, ×, /). Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для цифр известны.

2	00
3	010
4	100
5	101

Какое наименьшее количество двоичных знаков требуется для кодирования четырёх знаков арифметических действий?

В ответе запишите суммарную длину кодовых слов для знаков арифметических действий.

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

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

ID операции    
Дата покупки    
Время покупки    
Код спектакля    
ID тарифа    
Дата спектакля    
Количество купленных билетов для взрослых (без льгот)    
Количество купленных льготных билетов для взрослых    
Количество купленных детских билетов

Таблица «Цены» содержит информацию о ценах на билеты в зависимости от времени и сезона. Заголовок таблицы имеет следующий вид.

ID тарифа    
Название тарифа    
Стоимость билета для взрослого (без льгот), руб.    
Стоимость льготного билета для взрослого, руб.    
Стоимость детского билета, руб.

Таблица «Спектакли» содержит информацию о репертуаре театра. Заголовок таблицы имеет следующий вид.

Код спектакля    
Название    
Автор    
Режиссёр    
Жанр

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

В ответе запишите только число.

Задание 2

Миша заполнял таблицу истинности логической функции F

\(y \lor \neg (\neg z \lor w) \lor \neg x,\)

но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				F
0	1	0		0
		0	0	0
0				0

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Функция F задана выражением $$\neg x \lor y$$, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.

		F
0	1	0

В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать: yx.

На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта G в пункт E и из пункта F в пункт H.

В ответе запишите целое число.

Дана блок-схема алгоритма F(A, B)

Найдите такую пару целых положительных чисел A и B (известно, что B > 1), чтобы вызов F(A, B) вернул число 1594323. Если таких пар существует несколько, найдите ту, у которой максимальное значение A. В ответе укажите через пробел сначала значение A и затем значение B.

 

Дана блок-схема алгоритма F(A, B)

Найдите такую пару целых положительных чисел A и B (известно, что B > 1), чтобы вызов F(A, B) вернул число 2097152. Если таких пар существует несколько, найдите ту, у которой максимальное значение A. В ответе укажите через пробел сначала значение A и затем значение B.

 

---

Часть 1: Функция «Здание»

Напиши функцию building(width, height, floors, color), которая рисует здание с окнами.

Параметры функции:

• width — ширина здания
• height — высота здания
• floors — количество этажей (рядов окон)
• color — цвет здания

Как выглядит здание

    ┌────────────┐
    │  ■■    ■■  │  ← этаж 3
    │  ■■    ■■  │  ← этаж 2
    │  ■■    ■■  │  ← этаж 1
    └────────────┘
    ↑
    черепашка начинает тут (левый нижний угол)

Шаг 1: Запоминаем начальную позицию

Перед рисованием сохрани координаты черепашки:

base_x = xcor()
base_y = ycor()

Шаг 2: Рисуем здание

Закрашенный прямоугольник размером width × height цвета color.

Шаг 3: Вычисляем размер окон

window_width = width / 5
window_height = height / (floors * 2)

Шаг 4: Рисуем окна

На каждом этаже по 2 окна.  Используйте данный фрагмент для рисования окон, добавив нужные строки

# floor — номер этажа (0, 1, 2...), window — номер окна на этаже (0 или 1).
# Рисуем окна по этажам
for floor in range(floors):   # проходим по этажам
    for window in range(2):   # проходим по окошкам на этаже
        # Определяем позицию окна
        x = base_x + width / 6 + window * (width / 2)
        y = base_y + window_height / 2 + floor * (height / floors)
        

        # Переходим к окну (в точку (x, y))
        # Этот код напишите сами! 
        # не забудьте поднять перо перед переходом в точку и после перехода опустить

        # Рисуем жёлтое окно
        fillcolor("yellow")
        begin_fill()
        # напишите код рисования квадрата со стороной window_width
        
        end_fill()

В конце функции поднимите перо черепашки! Протестируйте функцию на одном здании! Затем приступайте к части 2.

---

### Схема расположения окон
    ┌─────────────────────────┐
    │                         │
    │   ■■            ■■      │  floor = 1
    │                         │
    │   ■■            ■■      │  floor = 0
    │   │             │       │
    └───│─────────────│───────┘
    ↑   │             │
 base_x │             └── base_x + width/6 + width/2
        │
        └── base_x + width/6

 

---

Часть 2: Рисуем улицу

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

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

i	widths[i]	heights[i]	floors_list[i]	colors[i]
0	60	120	4	"gray"
1	100	80	2	"beige"
2	50	150	5	"lightblue"
3	80	100	3	"pink"

Первое здание начните рисовать с точки (-300, -200) 
После рисования одного здания изменяйте положение Черепашки по оси x:

x = x + widths[i] + 10

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

Входные данные: В первой строке число N (1 ≤ N ≤ 10). Во второй строке N целых чисел от 0 до 100 — время отдыха на каждой ступеньке.

Выходные данные: Минимальное суммарное время отдыха.

Дана блок-схема алгоритма, реализованного в виде рекурсивно вызываемой функции:

Определите сумму первых 10¹⁰ чисел, которые выведутся при запуске алгоритма с 𝑁 = −3159

Нарисуйте цветной рисунок из трёх дуг (каждая дуга это полуокружность - угол 180 градусов)

1. Начало в (0, 0).
2. Фиолетовая дуга радиусом 150 (рисуется вверх вправо).
3. Желтая дуга радиусом 100.
4. Зеленая дуга радиусом 50.
5. Жёлтая и зеленая дуги находятся внутри фиолетовой так как показано на рисунке

У каждой дуги цвет контура и цвет заливки одинаковый

Какой тип данных имеет значение {1}?

1. строка
2. целое число
3. логическая переменная
4. вещественное число

Совет директоров хочет выйти на новый рынок в Китае. Для этого они запросили информацию по 3 крупнейшим компаниям на этом рынке с целью их покупки. Ваша задача — проанализировать эти компании и определить, какая из них принесет наибольшую прибыль (в млн $) через 5 лет, предполагая, что темпы роста капитала не изменятся.

Название	Капитал, млн $	Ежегодный прирост капитала за последние 5 лет, %	Доля прибыли от капитала, %
Engine Motors	15	5	4
Speed Cross	18	3	6
Fast Fuel	10	6	7

Выберите верное название компании:

1. Engine Motors
2. Speed Cross
3. Fast Fuel

Секретный уровень открывается, когда пройдены не менее 10 основных уровней (levels_passed), но не 15. Выбери правильное условие.

1. levels_passed > 10 and levels_passed != 15
2. levels_passed >= 10 and levels_passed <= 15
3. levels_passed >= 10 and levels_passed != 15
4. levels_passed > 10 or levels_passed < 15