Отработка задач 15, 18, 19, 20, 21, 24 из ЕГЭ по Информатике и ИКТ часть 13
Список вопросов теста
Вопрос 1
На числовой прямой даны три отрезка: P = [5, 280], Q = [295, 400] и R = [375, 450]. Какова наименьшая длина отрезка A, при котором формула
((x ∈ Q) → (x ∈ P)) ∨ (¬(x ∈ A) → (x ∈ R))
тождественно истинна, то есть принимает значение 1 при любом значении переменной х?
Вопрос 2
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наименьшего натурального числа А формула
(ДЕЛ(x, 3) → ¬ДЕЛ(x, 17)) \/ ¬(A < 190 - x)
тождественно истинна (т.е. принимает значение 1) при любом натуральном значении переменной х?
Вопрос 3
На числовой прямой даны три отрезка: P = [5; 40], Q = [41; 54] и R = [6; 53]. Укажите наименьшую возможную длину такого отрезка А, что формула
тождественно ложна, то есть принимает значение 0 при любых целых неотрицательных значения x?
Вопрос 4
Элементами множеств А, P и Q являются натуральные числа, причём P = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20} и Q = { 5, 10, 15, 20, 25, 30, 35, 40, 45, 50}. Известно, что выражение
((x ∈ A) → (x ∈ P)) ∧ ((x ∈ Q) → ¬(x ∈ A))
истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наибольшее возможное количество элементов множества A.
Вопрос 5
Укажите наименьшее целое значение А, при котором выражение
(680y + 256x < A) ∨ (5x + 3y > 11111)
истинно для любых целых неотрицательных значений x и y.
Вопрос 6
Квадрат разлинован на N х N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз.По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
Определите минимальную и максимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю, при условии, что робот обязательно должен посетить клетки, закрашенные зеленым цветом. В ответе укажите два числа — сначала минимальную сумму, затем максимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Пример входных данных:
Для указанных входных данных ответом является пара чисел: 35 40
Файлы к заданию: 18.xlsx
Вопрос 7
Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из четырёх команд: вправо на одну клетку, вправо на две клетки, вниз на одну клетку или вниз на две клетки.
Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.
В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщенными линиями.
Пример входных данных
Файлы к заданию: 18.xlsx
Вопрос 8
Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх – в соседнюю верхнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает все монеты с собой в том случае, если в клетке нечётное количество монет, иначе - половину. Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой нижней клетки в правую верхнюю. Исходные данные записаны в файле в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля. Внешние и внутренние стены обозначены утолщёнными линиями. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Файлы к заданию: 18.xlsx
Вопрос 9
Квадрат разлинован на NxN клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. Также в лабиринте отмечена одна клетка, через которую робот должен обязательно пройти.
Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером NxN, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщенными линиями.
Пример входных данных:
Для указанных входных данных ответом должна быть пара чисел: 200 180
Файлы к заданию: 18.xls
Вопрос 10
Ответы на каждое задание пишите через пробел.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или пять камней либо увеличить количество камней в куче в два раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы.
Игра завершается в тот момент, когда количество камней в куче становится не менее 31.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 31 или более камня.
В начальный момент в куче было S камней; 1 ≤ S ≤ 30.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Задание 19.
Укажите минимальное значение S, при котором Петя может выиграть своим вторым ходом после неудачного хода Вани.
Задание 20.
Для игры, описанной в задании 19, найдите количество значений S, при которых у Пети есть выигрышная стратегия, при этом он не может выиграть за один ход.
Задание 21.
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть вторым или третьим ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым или вторым ходом.
Вопрос 11
Ответы на каждое задание пишите через пробел.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может уменьшить количество камней в три раза (количество камней, полученное при делении, округляется до меньшего) или убрать из кучи 12 камней. Например, из кучи из 35 камней можно получить кучу из 11 или 23 камней. Игра завершается в тот момент, когда количество камней в куче становится не более 12. Победителем считается игрок, сделавший последний ход. В начальный момент в куче было S камней (S ≥ 13).
Задание 19.
Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. При каком максимальном значении S такое возможно?
Задание 20.
Для игры, описанной в задании 19, найдите минимальное и максимальное значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
• Петя не может выиграть за один ход;
• Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21.
Для игры, описанной в задании 19 определите, сколько существует значений S, при которых одновременно выполняются два условия:
• у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
• у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Вопрос 12
Текстовый файл состоит не более, чем из 1 200 000 прописных символов латинского алфавита. Определите максимальное количество идущих подряд символов, среди которых любые два символа из набора Q, R, S в различных комбинациях (с учётом повторений) не стоят рядом.
Для выполнения этого задания следует написать программу.
Файлы к заданию: 24.txt
Вопрос 13
Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита (ABC…Z) и десятичные цифры. Файл разбит на строки различной длины. Определите количество строк, в которых встречается сочетание букв QWERTY, полученные путем удаления лишних символов без перестановок.
Пример:
Пусть в файле находится 3 строки:
QW1ERTY5EEQW
TTERTTYFF
Q6W6EHRHTHYR
Здесь можно получить сочетания QWERTY путем удаления лишних символов без перестановок в двух строках.
Файлы к заданию: 24.txt
Вопрос 14
Текстовый файл состоит из символов A, C, D, F и O. Определите максимальное количество идущих подряд троек символов вида
согласная + любая буква + гласная
в прилагаемом файле.
Для выполнения этого задания следует написать программу.
Например, для строки ACCADAADD ответом будет число 2 (ACCADAADD).
Файлы к заданию: 24.txt
Вопрос 15
Текстовый файл состоит из символов A, C, D, F и O.
Определите максимальное количество идущих подряд символов, среди которых нет подстроки вида
согласная + гласная + гласная + согласная
в прилагаемом файле.
Для выполнения этого задания следует написать программу.
Файлы к заданию: 24.txt