Информатика

(С.В. Логинова) Логическая функция F задаётся выражением (x → y /\ ¬ z) \/ w. На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.

?	?	?	?	F
		1	0	0
0			1	0
1		1		0

Логическая функция F задаётся выражением \((x \rightarrow \neg z) \land (\neg y \rightarrow \neg x)\). На рисунке приведён фрагмент таблицы истинности функции F. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.

?	?	?	F
1	1	0	0
0	1	0	1

В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы.

(Д. Статный) На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите минимальную возможную длину пути из пункта E в пункт B. Передвигаться можно только по указанным дорогам.

(А. Игнатюк) На рисунке схема дорог изображена в виде графа, в таблице звёздочками обозначено наличие дороги между населенными пунктами. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана обозначениями на графе. Выпишите последовательно без пробелов и знаков препинания указанные на графе буквенные обозначения пунктов от П1 до П8: сначала букву, соответствующую П1, затем букву, соответствующую П2, и т. д.

(Е. Усов) На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице приведены длины дорог между пунктами. Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите ближайший пункт к П3. В ответе запишите буквенное обозначение этого пункта. Если возможно несколько верных ответов, запишите их в алфавитном порядке без пробелов.

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

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

Расстояние между двумя точками на плоскости \(A(x_1, y_1)\ и\ B(x_2, y_2)\) вычисляется по формуле:

\(d(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}.\)

В ответе запишите четыре числа: в первой строке – сначала целую часть произведения \(P_1 \times 10\,000\), затем целую часть произведения \(P_2 \times 10\,000\); во второй строке – сначала \(Q_1\), затем \(Q_2\).

---

В файле A хранятся координаты точек двух кластеров, где H = 6,5 и W = 4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Известно, что количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 6,5, W = 5 для каждого кластера. Известно, что количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична структуре в файле A.

Для файла A определите координаты центра каждого кластера, затем найдите два числа: \(P_1\) – минимальное расстояние от точки с координатами (1,0; 1,0) до центра кластера, и \(P_2\) – максимальное расстояние от этой же точки до центра кластера.

Для файла Б определите координаты центра каждого кластера, затем найдите два числа: \(Q_1\) – в кластере с наибольшим количеством точек число таких точек, которые находятся на расстоянии не более 1,2 от центра кластера, и \(Q_2\) – в кластере с наибольшим количеством точек число таких точек, которые находятся на расстоянии не более 0,75 от центра кластера. Гарантируется, что во всех кластерах количество точек различно.

Напишите программу, которая перебирает целые числа, большие 1 350 050, в порядке возрастания и ищет среди них такие, у которых есть натуральный делитель, оканчивающийся на 11 и не равный ни самому числу, ни числу 11.

В ответе запишите первые пять найденных чисел в порядке возрастания, а также для каждого числа соответствующий минимальный делитель, оканчивающийся на 11, не равный ни самому числу, ни числу 11.

Количество строк в таблице для ответа избыточно.

Каждую пару число_делитель записывать в ответе в отдельной строке через один пробел.

Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:

• A. вычти 3
• B. вычти 6
• C. найди целую часть от деления на 2

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 86 результатом является 12, при этом траектория вычислений содержит число 53 и не содержит 36?

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

Например, для программы CBA при исходном числе 27 траектория состоит из чисел 13, 7, 4.

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

Типовой пример организации данных в файле

ID процесса B	Время выполнения процесса B (мс)	ID процесса(-ов) A
1	3	0
2	4	1
3	2	2; 4
4	5	0
5	8	1; 4
6	3	1

Для приведённой таблицы процесс 3 начинается на 8-й мс, заканчивается на 9-й мс.

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

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

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

Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

• Петя не может выиграть за один ход;
• Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

• добавить в кучу 2 камня;
• добавить в кучу 4 камня;
• увеличить количество камней в куче в 2 раза.

Например, из кучи в 20 камней за один ход можно получить кучу из 22, 24 или 40 камней.

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 125. Победителем считается игрок, сделавший последний ход, то есть первый получивший кучу из 125 или более камней. В начальный момент в куче было S камней, \(1 \leq S \leq 124\).

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

Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.

В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.

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

В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.

Пример входных данных

1	8	8	4
10	1	1	3
1	3	12	2
2	3	5	6

В файле содержится последовательность целых чисел. Её элементы могут принимать целые значения от −100 000 до 100 000 включительно. Определите количество троек элементов последовательности, в которых ни один из трёх элементов не является четырёхзначным числом, а сумма элементов тройки больше максимального элемента последовательности, оканчивающегося на 30.

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

В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности.

Алгоритм вычисления функций F(n) и G(n), где n – целое число, задан следующими соотношениями:

\(F(n) = F(n - 4) + 3580, \text{ если } n \geq 19;\\ F(n) = 6 \times (G(n - 7) - 36), \text{ если } n < 19;\\ G(n) = n / 20 + 28, \text{ если } n \geq 248\,045;\\ G(n) = G(n + 9) - 4, \text{ если } n < 248\,045.\)

Чему равно значение функции F(673)?

Для какого наименьшего целого неотрицательного числа A логическое выражение

\((78\,125 \neq y + 4x) \lor (A > x) \land (A > y)\)

истинно (т.е. принимает значение 1) при любых целых положительных x и y?

Значение арифметического выражения \(3 \cdot 27^9 + 2 \cdot 27^6 + 27^3 - x\), где x – целое положительное число, не превышающее 27 000, записывали в 27-ричной системе счисления.

Определите наименьшее значение x, при котором в 27-ричной записи числа, являющегося значением данного арифметического выражения, содержится ровно 6 нулей.

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

В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске. Широковещательным адресом называется специализированный адрес, в котором на месте нулей в маске стоят единицы. Адрес сети и широковещательный адрес не могут быть использованы для адресации сетевых устройств.

Сеть задана IP-адресом одного из входящих в неё узлов 190.202.83.62 и сетевой маской 255.255.252.0.

Найдите наибольший IP-адрес в данной сети, который может быть назначен компьютеру. В ответе укажите сумму числовых значений октетов найденного IP-адреса.

Например, если бы найденный адрес был равен 100.20.3.4, то в ответе следовало бы записать: 127.

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

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

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

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

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

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

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