Страница 3 из 5
В начальный момент в куче было – S камней; 1 ≤ S ≤ 43.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Ответ: ___________________________.
20. Для игры, описанной в предыдущем задании, найдите два таких наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Например, если Петя может выиграть своим вторым ходом при s = 8, s = 13, s = 15, то в ответ необходимо записать только числа 8 и 13.
Ответ: ___________________________.
21. Для игры, описанной в задании 19, определите, сколько существует таких значений s, при которых Ваня выигрывает своим первым ходом независимо от того, как будет ходить Петя
Ответ: ___________________________.
22. Ниже на четырёх языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм печатает сначала 21, а потом 12.
Ответ: ___________________________.
23. Исполнитель преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 3
2. Умножить на 3
Первая команда увеличивает число на экране на 1, вторая увеличивает число на 3, третья – умножает его на 3.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 3 результатом является число 21, и при этом траектория вычислений содержит число 7 и не содержит число 14
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 6 траектория будет состоять из чисел 7, 10, 11.
Ответ: ___________________________.
Задание выполняется с использованием прилагаемых файлов
24. В текстовом файле представлен рассказ А.П. Чехова – «Альбом».
Определите, сколько в тексте этого рассказа вставлено лишних пробелов.
Например, если после слова или знака препинания стоят шесть пробелов, то лишними считаются пять из них.
Для выполнения этого задания следует написать программу.
Ответ: ___________________________.
25. Напишите программу, которая ищет среди десятичных целых чисел, принадлежащих отрезку [23220; 30764], числа, оканчивающиеся на 18 в десятичной системе счисления и имеющие не менее двух цифр «5» в восьмеричной записи. Для каждого найденного числа запишите, сколько в нем цифр «5» в восьмеричной записи. В первом столбце каждой строки таблицы следует записывать десятичное число, удовлетворяющее условиям выше, а во втором столбце – количество цифр «5» в восьмеричной записи этого числа.
Числа в таблицу записывать по возрастанию.
Например, в диапазоне [1000; 10000] ровно два целых десятичных числа удовлетворяют условиям задачи. 291810 = 55468 и 701810 = 155528, поэтому для этого диапазона таблица на экране должна содержать следующие значения:
Ответ: ___________________________.
Задание выполняется с использованием прилагаемых файлов
26. Системный администратор раз в неделю создаёт архив пользовательских файлов среднего размера. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов.
Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы среднего размера можно сохранить в архиве и их суммарный объем, если администратор сохраняет файлы наиболее близкие к среднему размеру всех файлов пользователей.
Входные данные.
В первой строке входного файла находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 16 000) и N – количество пользователей (натуральное число, не превышающее 500). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 10000), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы среднего размера могут быть сохранены в архив, затем суммарный объем всех сохраненных файлов.
Пример входного файла:
36 4
18
13
22
2
При таких исходных данных можно сохранить файлы максимум двух пользователей, это файлы имеющие размеры 13 и 18. Средний размер всех четырех файлов составляет 13,75. Числа 13 и 18 наиболее близки к среднему размеру всех файлов и их суммарный размер не превышает 36. Из оставшихся чисел, 22 ближе к среднему арифметическому, чем 2, но уже не помещается в архив, поэтому ответ для приведённого примера:
2 31
Ответ: ___________________________.
Задание выполняется с использованием прилагаемых файлов
27. Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, находящихся на расстоянии не меньше 9 (разница в индексах элементов должна быть 9 или более). Необходимо определить количество пар, произведение чисел в которых кратно 38. Гарантируется, что хотя бы одна такая пара есть.
Входные данные.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.
Пример организации исходных данных во входном файле:
12
18
19
7
76
12
11
13
18
21
76
19
14
Для указанных входных данных искомое количество пар равно 3.
В ответе укажите два числа: сначала количество искомых пар для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Ответ: __________________________
Вариант 2