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

Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от ${\displaystyle –}$10 000 до 10 000 включительно. Опишите
на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести количество элементов массива, которые НЕ делятся на 3.

Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается
не использовать некоторые из описанных переменных.

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

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

Пример. Заданный набор слов: {АНТАРКТИДА, АНТРАЦИТ, АБАРА, АБАЖУР, БББ, БАОБАБ, БАР}.

Первым ходом Петя пишет Б (он мог написать Б или А).

Ваня в ответ дописывает А и получает БА (он мог ещё получить ББ).

Вторым ходом Петя получает БАР и выигрывает.

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

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

Задание 1. а) Укажите, у кого есть выигрышная стратегия при исходном наборе слов {АБВГДАБВГДХ, ДГВБАДГВБА}. Опишите эту стратегию. Сколько различных партий возможно при этой стратегии? Для каждой возможной партии укажите, какое слово будет написано в конце партии.

б) Укажите, у кого есть выигрышная стратегия при исходном наборе слов {ТРИТРИ…ТРИ, РИТАРИТА…РИТА} (в первом слове ТРИ повторено
33 раза, т.е. его длина 99 букв; во втором слове РИТА повторено 44 раза,
т.е. его длина 176 букв). Опишите эту стратегию.

Задание 2. В задании 1а поменяйте местами две буквы в более коротком слове так, чтобы теперь выигрышная стратегия была у другого игрока. Напишите полученный набор слов; опишите выигрышную стратегию. Сколько различных партий возможно при этой стратегии? Для каждой возможной партии укажите, какое слово будет написано в конце партии.

Задание 3. Рассмотрим набор слов {СОЛНЦЕ, СОВА, СОВЕТ, ПРОСО, ПРОХОР, ПРОИЗВОДНАЯ}. У кого из игроков есть выигрышная стратегия для этого набора? Приведите в виде рисунка или таблицы дерево всех партий, возможных при этой стратегии.

Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, удовлетворяющие следующим условиям: числа в паре имеют различные остатки от деления на d = 200, и, по крайней мере, одно из чисел пары делится на p = 7. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.

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

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

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

4

70

270

63

73

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

270 63

Пояснение. Из данных четырёх чисел можно составить четыре различные пары, удовлетворяющие условию: (70, 63), (70, 73), (270, 63), (63, 73). Наибольшая сумма получается в паре (270, 63).

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

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

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

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

Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, в том числе память или время работы которой увеличивается не более чем в k раз при увеличении параметра d в k раз $–$ 
3 балла.

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

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

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