Экзамены и диагностики

Для кодирования некоторой последовательности, состоящей из букв О, В, Д, Р, К, решили использовать неравномерный двоичный код, гарантирующий однозначное декодирование. Для букв В и К использовали соответственно кодовые слова 00, 011. Найдите наименьшую возможную длину кодовой последовательности для слова ВОДОРОД.

На рисунке изображена схема дорог некоторого района области в виде графа, в таблице указана длина этих дорог в километрах. Таблицу и схему рисовали независимо друг от друга, нумерация пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите сумму длин сторон между пунктом A и пунктом B, и между пунктом F и пунктом G. В ответе запишите целое число – так, как оно указано в таблице.
 

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

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

 

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

?	?	F
0	1	0

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

 

В период засухи существует опасность лесных пожаров. Чем раньше получится ликвидировать пожар, тем меньший вред он нанесет. Поэтому для предотвращения больших пожаров создана мобильная пожарная бригада. Для мониторинга ситуации проводится аэросъемка местности. Территория разбивается на квадратные участки (клетки), сторона каждой из которых равна 1 км. Клетки нумеруются по принципу: столбцы обозначаются буквами латинского алфавита, а строки — числами. Клетка может содержать лес или пустое пространство. Для ликвидации пожара высылается пожарная бригада, которую доставляют вертолетом максимально близко к точке возгорания. Но приземлиться в любой точке местности вертолет не может. Считается, что точка доступна для посадки, если она находится в центре квадрата из свободных клеток со стороной размера 5, расположенного целиком внутри территории. Необходимо найти количество подходящих под условие задачи точек посадки и расстояние до максимально близкой к точке возгорания клетки, в которую возможно совершить посадку. Если таких клеток найдено несколько, укажите клетку с лексикографически минимальным обозначением столбца и минимальным номером ряда.

Входные данные:
В первой строке входного файла 26.txt находится число N - количество клеток, занятых лесом (натуральное число, не превышающее 10 000).
Каждая из следующих N строк содержит латинскую букву из набора 26 различных букв — обозначение ряда и натуральное число, не превышающих 1000: номер клетки в этом ряду, занятой лесом.
В последней строке вводится латинская буква и натуральное число — координаты клетки, в которой произошло возгорание.

Выходные данные:
Два числа: количество подходящих под условие точек посадки и округленное до целого числа расстояние от ближайшей к точке возгорания точки посадки. Числа разделить пробелом.

Пример входного файла:
4
A 1
C 1
B 2
B 4
B 3
Если считать, что территория ограничена набором из 7 букв от А до G и 7 строк, то под условие посадки подойдут две клетки: Е 4 и Е 5.
Максимально близкая к точке возгорания клетка, доступная для посадки – это Е 4. Расстояние от Е4 до В3 3.16... Округленное до целого значения 3.
Ответ для примера: 2 3

Скачать файл

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 10⁹, найдите все числа, соответствующие маске 270?5?43, делящиеся на число 21 без остатка.

В ответе запишите все найденные числа в порядке возрастания в формате: в одной строке - найденное число и через  пробел соответствующий ему результат деления этого числа на 21.
 

Текстовый файл состоит не более, чем из 10⁶ символов A, B, C и D.
Определите максимальное количество подряд идущих пар символов AB, AC или AD. Искомая подстрока может содержать как только пары АВ, АС или AD, так и одновременно пары в любом количестве из набора AB, AC и AD.

Скачать файл

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

1. Прибавить 2
2. Умножить на 2

Первая команда увеличивает число на экране на 2, вторая – увеличивает его вдвое.
Программа для исполнителя – это последовательность команд. Сколько существует таких программ, которые исходное число 1 преобразуют в число 74 и при этом траектория вычислений программы содержит число 22?
 

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) 2 камня или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней, такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (12, 5), (10, 7), (20, 10) и (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 264. В начальный момент в первой куче было 37 камней, во второй куче – S камней, 1 ≤ S ≤ 226.

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

Вопрос 1

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

Вопрос 2

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

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

Если найдено несколько таких значений, в ответе укажите минимальное.
 

Вопрос 3

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

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

Формат ввода ответа

На каждое задание ответы пишите с новой строки. Если вы не знаете ответ на какое-либо задание, напишите в ответе любое число.

Например, если ответ на вопрос  1 - 1, на вопрос 2 - 2 и 3, на вопрос 3 - 4, то ответы надо записать так:

1
2 3
4

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

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

Исходные данные представлены в форме электронной таблицы размером N × N, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.

Найденные числа запишите через пробел.

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

Для указанных входных данных ответом является пара чисел:
85 227

Скачать файл

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

Найденные числа запишите через пробел.

Скачать файл

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

F(n) = 2 при n ≤ 2;
F(n) = 2 · F(n − 1) + F(n − 2) - n, если n > 2 и при этом n нечётно;
F(n) = F(n − 1) – F(n – 2) + 2n, если n > 2 и при этом n чётно.

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

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

F(n) = n + 10, если n < 10;
F(n) = n % 10 + G(F(n/10)), в остальных случаях;
G(n) = n + 10, если n < 10;
G(n) = n % 10 + G(n/10), в остальных случаях;

Определите количество различных значений n, не превосходящих 10⁶,  при котором функция F(n) кратна 7?
Знак / - означает операцию целочисленного деления.
Знак % - означает операцию вычисления остатка при делении двух целых чисел.


 

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

F(n) = n % 10, если n < 100;
F(n) = n / 100 + G(n%100), в остальных случаях;
G(n) = n % 10, если n < 100;
G(n) = n % 100 + F(n/100), в остальных случаях;

Определите сумму всех значений функции G(n), для всех значений n меньших 100000?
Знак / - означает операцию целочисленного деления.
Знак % - означает операцию вычисления остатка при делении двух целых чисел.



 

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

F(n) = n % 10, если n < 100;
F(n) = n / 100 + G(n%100), в остальных случаях;
G(n) = n % 10, если n < 100;
G(n) = n % 100 + F(n/100), в остальных случаях;

Определите сумму всех значений функции F(n), для всех значений n меньших 100000?
Знак / - означает операцию целочисленного деления.
Знак % - означает операцию вычисления остатка при делении двух целых чисел.


 

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

F(n) = n + 10, если n < 10;
F(n) = n % 10 + G(F(n/10)), в остальных случаях;
G(n) = n + 10, если n < 10;
G(n) = n % 10 + G(n/10), в остальных случаях;

Определите сумму всех значений функции F(n) для всех значений n меньших 1000000?
Знак / - означает операцию целочисленного деления.
Знак % - означает операцию вычисления остатка при делении двух целых чисел.


 

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

F(n) = n + 10, если n < 10;
F(n) = n % 10 + G(F(n/10)), в остальных случаях;
G(n) = n + 10, если n < 10;
G(n) = n % 10 + G(n/10), в остальных случаях;

Определите минимальное значение n,  при котором функция F(n)=30?
Знак / - означает операцию целочисленного деления.
Знак % - означает операцию вычисления остатка при делении двух целых чисел.


 

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

F(n) = n + 10, если n < 10;
F(n) = n % 10 + G(F(n/10)), в остальных случаях;
G(n) = n + 10, если n < 10;
G(n) = n % 10 + G(n/10), в остальных случаях;

Определите, для скольких различных значений n меньших 1000000, функция F(n)=25?
Знак / - означает операцию целочисленного деления.
Знак % - означает операцию вычисления остатка при делении двух целых чисел.


 

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

F(n) = n + 10, если n < 10;
F(n) = n % 10 + G(F(n/10)), в остальных случаях;
G(n) = n + 10, если n < 10;
G(n) = n % 10 + G(n/10), в остальных случаях;

Определите, сколько различных значений принимает функция F(n) для всех n меньших 1000000?
Знак / - означает операцию целочисленного деления. 
Знак % - означает операцию вычисления остатка от деления двух целых чисел.




 

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

F(n) = n, если n < 100;
F(n) = n + F(n/3), в остальных случаях;
G(n) = n + 1, если n < 100;
G(n) = G(F(n/2)), в остальных случаях.

Определите, для скольких различных значений n,  принадлежащих отрезку [100, 100000], функция G(n)=99?
Знак / - означает операцию целочисленного деления.


 

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

F(n) = n, если n < 100;
F(n) = n + F(n/3), в остальных случаях;
G(n) = n + 1, если n < 100;
G(n) = G(F(n/2)), в остальных случаях.

Определите, сколько различных значений принимает функция G(n) на отрезке [100, 100000]?
Знак / - означает операцию целочисленного деления.