Все задания — ЕГЭ по информатике — страница 192

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

Игра завершается в тот момент, когда суммарное количество камней
в кучах становится не менее 59.

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока ${\displaystyle –}$ значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (4, 28), (5, 27), (7, 26) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.
В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от дальнейшей игры противника.

Задание 1. Для каждой из начальных позиций (4, 27), (6, 26) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию.

Задание 2. Для каждой из начальных позиций (4, 26), (5, 26), (6, 25) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию.

Задание 3. Для начальной позиции (5, 25) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не является верным ответом на это задание.

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 74.

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.

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

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

4

2

6

37

111

Пример выходных данных для приведённого выше примера входных данных:

4

Пояснение. Из четырёх заданных чисел можно составить 6 попарных произведений: 2·6, 2·37, 2·111, 6·37, 6·111, 37·111 (результаты: 12, 74, 222, 222, 666, 4107). Из них на 74 делятся 4 произведения (2·37=74; 2·111=222; 6·37=222; 6·111=666).

Требуется написать эффективную по времени и по памяти программу для решения описанной задачи.

Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.

Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.

Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, ${\displaystyle –}$ 4 балла.

Максимальная оценка за правильную программу, эффективную только по времени ${\displaystyle –}$ 3 балла.

Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, ${\displaystyle –}$ 2 балла.

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

Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности a_i и a_j, такие что i < j и a_i > a_j (первый элемент пары больше второго, i и j ${\displaystyle –}$ порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m = 107. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел n (2 ≤ n ≤ 12 000). В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000.

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

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

6

60

114

61

100

261

46

Пример выходных данных для приведённого выше примера входных данных:

114 100

Пояснение. Из шести заданных чисел можно составить 3 пары, сумма элементов которых делится на 107: 60+261, 114+100, 61+46. Во второй
и третьей из этих пар первый элемент больше второго, но во второй паре сумма больше.

Требуется написать эффективную по времени и памяти программу для решения описанной задачи.

Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности n и параметра m
в k раз, время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом n.

Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, ${\displaystyle –}$ 4 балла.

Максимальная оценка за правильную программу, возможно, неэффективную по памяти или время выполнения которой существенно зависит от
величины m, ${\displaystyle –}$ 3 балла.

Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, ${\displaystyle –}$ 2 балла.

Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо${\displaystyle �}$ьшая из двух оценок.

Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.