Информатика

Дан лабиринт в виде прямоугольной таблицы N×M. Символ '.' — проход, символ '#' — стена. Найдите количество различных путей из левого верхнего угла (0,0)  в правый нижний угол (N-1, M-1).
Двигаться можно только вправо или вниз. Проходить через одну клетку дважды нельзя.

Формат входных данных
Первая строка: два числа N и M — размеры лабиринта (2 ≤ N, M ≤ 5)
Следующие N строк: лабиринт (символы '.' и '#')

Формат выходных данных
Одно число — количество различных путей.
Если путей нет, вывести 0.
 

Примечание

В тестовом примере существуют два пути
Путь 1: (0,0)→(1,0)→(2,0)→(2,1)→(2,2)
Путь 2: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)

ПОДСКАЗКА:
1. Отмечай посещённые клетки, чтобы не ходить по кругу
2. При откате снимай отметку о посещении
3. Проверяй границы лабиринта и стены
 

Реализуйте алгоритм k-means для одномерных данных (только координата x).

Для одномерных данных расстояние между точками вычисляется как модуль разности: |x₁ - x₂|

При равном расстоянии до нескольких центров точка присваивается кластеру с меньшим номером.

 

Формат входных данных

- Первая строка: два целых числа n и k (1 ≤ k ≤ n ≤ 1000) — количество точек и кластеров

- Вторая строка: n целых чисел через пробел — значения точек (−10⁶ ≤ xᵢ ≤ 10⁶)

- Третья строка: k вещественных чисел через пробел — начальные центры кластеров

 

Формат выходных данных

- Первая строка: k вещественных чисел — финальные центры кластеров (округлённые до 1 знака после запятой)

- Вторая строка: n целых чисел — номер кластера (0-индексация) для каждой точки в порядке их появления во входных данных

На числовой прямой даны два отрезка: P = [225; 464] и Q = [140; 315]. Укажите наименьшую возможную длину такого отрезка A, что логическое выражение

\((x \in P) \to (((x \in Q) \land \neg (x \in A)) \to \neg (x \in P))\)

истинно (т.е. принимает значение 1) при любом значении переменной x.

Значение арифметического выражения

\(2 \cdot 2187^{226} + 2 \cdot 729^{227} - 243^{228} + 2 \cdot 81^{229} - 27^{230} - 6561\)

записали в системе счисления с основанием 27. Определите в 27-ричной записи числа количество цифр с числовым значением, превышающим 9.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

......

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

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

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

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

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

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

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

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

• а) если число N делится на 3, то к этой записи справа дописываются две последние троичные цифры;
• б) если число N на 3 не делится, то вычисляется сумма цифр полученной троичной записи, эта сумма умножается на 3, переводится в троичную систему счисления и дописывается в конец числа.

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

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

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

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

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

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

2	00
3	01
4	100
5	101

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

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

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

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

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

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

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

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

				F
1			1	1
0	1		0	1
1	1	0		1

Определите, какому столбцу таблицы соответствует каждая из переменных 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.

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

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

• A. прибавь 3
• B. прибавь 5
• C. умножь на 3

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

Сколько существует программ, для которых при исходном числе 13 результатом является 70, при этом траектория вычислений содержит числа 26 и 34 и не содержит 21, 29 и 52?

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

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

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

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

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

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

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

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

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

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

Операнды арифметического выражения записаны в системе счисления с основанием 27.

\(472x215_{27} + 92x538_{27}\)

В записи чисел переменной x обозначена неизвестная цифра из алфавита 27-ричной системы счисления. Определите наибольшее значение x, при котором значение данного арифметического выражения кратно 26. Для найденного x вычислите частное от деления значения арифметического выражения на 26 и укажите его в ответе в десятичной системе счисления. Основание системы счисления указывать не нужно.

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

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

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

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