11 класс

 1.  Каждый сотрудник предприятия получает электронный пропуск, на котором записаны личный код сотрудника, номер подразделения и некоторая дополнительная информация. Личный код состоит из 15 символов, каждый из которых может быть заглавной русской буквой (используется 25 различных букв) или одной из цифр от 0 до 5. Для записи кода на пропуске отведено минимально возможное целое число байт. При этом используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством бит. Номер подразделения  — целое число от 1 до 1200, он записан на пропуске как двоичное число и занимает минимально возможное целое число байт. Всего на пропуске хранится 40 байт данных. Сколько байт выделено для хранения дополнительных сведений об одном сотруднике? В ответе запишите только целое число  — количество байт.

2.  Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А)  заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б)  нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

 

Цикл

ПОКА условие

последовательность команд

КОНЕЦ ПОКА

выполняется, пока условие истинно.

В конструкции

ЕСЛИ условие

ТО команда1

ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

 

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 108 идущих подряд цифр 7? В ответе запишите полученную строку.

НАЧАЛО

ПОКА нашлось (33333) ИЛИ нашлось (777)

ЕСЛИ нашлось (33333)

ТО заменить (33333, 7)

ИНАЧЕ заменить (777, 3)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

3.  В терминологии сетей TCP/⁠IP маской сети называют двоичное число, которое показывает, какая часть IP-⁠адреса узла сети относится к адресу сети, а какая  — к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети.

Сеть задана IP-⁠адресом 122.159.136.144 и маской сети 255.255.255.248.

Сколько в этой сети IP-⁠адресов, для которых количество единиц в двоичной записи IP-⁠адреса не кратно 4?

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

4.  Значение выражения 36⁷ + 6¹⁹ − 18 записали в системе счисления с основанием 6.

Сколько цифр 5 содержится в этой записи?

5.  Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Так, например, 14&5  =  1110₂ & 0101₂  =  0100₂  =  4. Для какого наименьшего неотрицательного целого числа А формула

x & 73 = 0 → (x & 28 ≠ 0 → x & А ≠ 0)

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

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

F(n)  =  2 при n  =  1;

F(n)  =  F(n – 1) · n при n ≥ 2.

 

Чему равно значение функции F(5)? В ответе запишите только натуральное число.

7.  Файл содержит последовательность неотрицательных целых чисел, не превышающих 10 000. Назовём парой два идущих подряд элемента последовательности. Определите количество пар, в которых один из двух элементов делится на 5, а другой меньше среднего арифметического всех нечётных элементов последовательности. В ответе запишите два числа: сначала количество найденных пар, а затем  — максимальную сумму элементов таких пар.

Задание 17

Например, в последовательности (8 10 2 7 5 1) есть две подходящие пары: (10 2) и (5 1), в ответе для этой последовательности надо записать числа 2 и 12.

 

Ответ:

8.  Робот стоит в левом нижнем углу прямоугольного поля, в каждой клетке которого записано целое число. В некоторых клетках записано число −1, в эти клетки роботу заходить нельзя. Для вашего удобства такие клетки выделены тёмным фоном. В остальных клетках записаны положительные числа.

За один ход робот может переместиться на одну клетку вправо или на одну клетку вверх. Клетка, из которой робот не может сделать допустимого хода (справа и сверху находятся границы поля или запрещённые клетки), называется финальной. На поле может быть несколько финальных клеток.

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

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

Задание 18

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

Задание 2. Определите количество финальных клеток, до которых робот может дойти с начальным запасом энергии 2000 единиц.

Исходные данные записаны в электронной таблице. В ответе запишите два числа: сначала ответ на задание 1, затем ответ на задание 2.

 

Ответ:

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

добавить в кучу один камень или

увеличить количество камней в куче в четыре раза.

Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или из 40 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче превышает 64. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 65 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 64.

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

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

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

добавить в кучу один камень или

увеличить количество камней в куче в четыре раза.

Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или из 40 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче превышает 64. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 65 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 64.

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

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

—  Петя не может выиграть за один ход;

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

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