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

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

Вопрос 1

При каком минимальном значении S у Пети есть выигрышная стратегия, в которой он побеждает своим первым ходом?
 

Вопрос 2

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

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

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

Вопрос 3

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

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

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

 

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

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

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

1
2 3
4

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

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

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

Для указанных входных данных при условии, что начальный запас энергии равен 300 единиц, ответом является пара чисел:
73 215

Скачать файл
 

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

Скачать файл

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n <= 2;
F(n) = 4 × F(n − 1) - 2 × F(n − 2) + n, если n > 2 и при этом кратно трем;
F(n) = F(n − 1) - F(n – 2) + n, если n > 2 и при этом не кратно трем.
Чему равно значение функции F(35)?
 

На числовой прямой даны три отрезка: P = [15; 37], Q = [41; 71] и R = [21; 53]. Укажите наименьшую возможную длину такого отрезка А, что формула тождественно ложна, то есть принимает значение 0 при любых целых неотрицательных значения x?
 

Значение арифметического выражения записали в восьмеричной системе счисления. Сколько раз в данной записи непосредственно слева от меньшей цифры стоит большая?
Например, в записи 76573 данное условие выполняется 3 раза.
 

При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 128 символов и содержащий только десятичные цифры и символы из 2040-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме идентификатора, для каждого объекта хранится дополнительная информация.
Известно, что для хранения данных об 1024 объектах потребовалось 376 Кбайт. Сколько Кбайт занимает дополнительная информация обо всех объектах?
В ответе запишите только целое число – количество Кбайт.
 

С помощью текстового редактора определите, сколько отдельных слов «лакей», начинающихся со строчной буквы, встречается в тексте романа Л.Н. Толстого «Анна Каренина». Другие формы слова «лакей», такие как «лакеем», «лакею» и т.д., учитывать не следует.
В ответе укажите только число.

Скачать файл

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

Скачать файл

Все 6-буквенные слова, составленные из букв В, Е, С, Н, А, записаны в алфавитном порядке и пронумерованы.
Вот начало списка:
1. АААААА
2. АААААВ
3. АААААЕ
4. АААААН
5. АААААС
6. ААААВА
… …
Под каким номером стоит последнее слово, в котором есть все буквы из набора, но никакие две одинаковые не стоят рядом?
 

Автомат обрабатывает натуральное число N по следующему алгоритму:
1. Строится восьмеричная запись числа N.
2. К полученной записи дописываются разряды. Если число четное, справа дописывается 57, если число нечетное – слева дописывается 5 и справа 2.
3. Результат переводится в десятичную систему и выводится на экран.

Пример. Дано число N = 13. Алгоритм работает следующим образом:
1. Восьмеричная запись числа N: 15.
2. Число нечетное, следовательно слева дописываем 5, справа 2 – 5+15+2 = 5152. Десятичная запись числа 2666
3. На экран выводится число 2666.

В результате работы автомата на экране появилось число, меньшее 1000. Для какого наибольшего значения N данная ситуация возможна?
 

Для кодирования некоторой последовательности, состоящей из букв А, Н, Т, И, В, Е, С, решили использовать неравномерный двоичный код, гарантирующий однозначное декодирование. Для букв Е и В использовали соответственно кодовые слова 111, 1101. Найдите наименьшую возможную длину кодовой последовательности для слова АТТЕСТАТ.
 

Ученик заполнял таблицу истинности функции \(\neg w \vee(w \equiv \neg y) \wedge (x \rightarrow z)\), но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				\(\neg w \vee(w \equiv \neg y) \wedge (x \rightarrow z)\)
	0		1	0
0	1		0	0
		1	1	0

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

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

Громозека составляет слова из букв слова АРТИШОК по следующим правилам:
- слово должно состоять из 11 букв;
- слово не должно начинаться с буквы К и содержит все гласные буквы ровно по одному разу.
Сколько различных кодов может составить Громозека?

Текстовый файл состоит не более чем из 1 000 000 символов A, B, C, D и E. 
Определите максимальное количество идущих подряд символов, среди которых нет символов B и D, стоящих рядом, а количество гласных букв не менее 50.
Для выполнения этого задания следует написать программу.
 

Текстовый файл состоит не более чем из 1 000 000 символов A, B, C, D и E. 
Определите максимальное количество идущих подряд символов, среди которых нет символов B и C, стоящих рядом, а количество букв E больше количества букв А.
Для выполнения этого задания следует написать программу.

Скачать файл

Текстовый файл состоит не более чем из 1 000 000 символов A, B, C, D и E. 
Определите максимальное количество идущих подряд символов, содержащих не более 5 букв A, но не менее двадцати букв D.
Для выполнения этого задания следует написать программу.
 

Текстовый файл состоит не более чем из 1 000 000 символов A, B, C, D и E. 
Определите максимальное количество идущих подряд символов, содержащих не более 5 букв D.
Для выполнения этого задания следует написать программу.

Скачать файл

Текстовый файл состоит не более чем из 1 000 000 символов A, B, C, D и E. 
Определите максимальное количество идущих подряд символов, среди которых нет символов B и C, стоящих рядом, но есть не менее двух букв А.
Для выполнения этого задания следует написать программу.