Студия Компьютерного Мастерства

Тема: Теория игр. Поиск выигрышной стратегии.

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

Немного теории

☆ Все позиции в простых играх делятся на выигрышные и проигрышные

Одна куча

Два игрока, Петя и Вася, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

Например, имея кучу из 20 камней, за одни ход можно получить кучу из 21, 23 или 80 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 78. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 78 или больше камней. В начальный момент в куче было S камней: 1 ≤ S ≤ 77.

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

Известно, что Вася выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

Решение

Ответ

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

Найденные значения запишите в ответе в порядке возрастания.

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

16 18

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

Например, имея кучу из 20 камней, за одни ход можно получить кучу из 21, 22 или 79 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 85. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 85 или больше камней. В начальный момент в куче было S камней: 1 ≤ S ≤ 84.

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

Задание 20 (самостоятельно)

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

Задание 19_20_22(DEMO) пишем программу Phyton

P-01 (демо-2022). Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 28.

Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

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

− Петя не может выиграть за один ход;

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

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

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

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Задание 19_20_22 (Поляков) пишем программу Phyton

Две кучи — варианты решений

Два игрока, Петя и Вася, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

Например, пусть в одной куче 8 камней, а в другой куче 5 камней. Тогда за один ход можем получить четыре позиции: (9, 5); (18, 5); (8, 6); (8, 21).

Для того что бы играть, у игроков есть неограниченное количество камне.

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

В начальный момент в первой куче было 9 камней, во второй S камней: 1 ≤ S ≤ 67.

Можно решить с помощью рассуждений

(№ 4725) (И. Осипов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат три кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) три камня или увеличить количество камней в куче в два раза. Например, пусть в первой куче 10 камней, во второй 7, а в третьей 4 камня; такую позицию в игре будем обозначать (10, 7, 4). Тогда за один ход можно получить любую из шести позиций: (13, 7, 4), (20, 7, 4), (10, 10, 4), (10, 14, 4), (10, 7, 7), (10, 7, 8). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 71. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, что в кучах всего будет 71 или больше камней. В начальный момент в первой куче было семь камней, во второй куче пять камней, в третьей куче – S камней; 1 ≤ S ≤ 58.Ответьте на следующие вопросы:  Вопрос 1.При некотором значении S Ваня одержал победу свои первым ходом после неудачного хода Пети. Укажите минимальное значение S, при котором это возможно.  Вопрос 2. Найдите минимальное и максимальное значения S, при которых Петя выигрывает вторым ходом при любом ходе Вани.  Вопрос 3. Найдите значение S, при котором одновременно выполняются два условия: а) у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; б) у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

14 27

Сборник необходимой теории и практики к заданию №1 ЕГЭ 2023 по информатике «Использование и анализ информационных моделей (таблицы, диаграммы, графики)».

Формулировка задания №1 ЕГЭ 2023 из демоверсии ФИПИ

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта D в пункт B и из пункта F в пункт A. В ответе запишите целое число.

Все типы заданий №1

Граф состоит из вершин (узлов), связанных дугами или рёбрами. Вершины изображают точками, кругами, овалами, прямоугольниками и т.д.

Связи между вершинами называют ветвями и изображают линиями. Если линия направленная, т.е. со стрелкой, она называется дугой. Если линия ненаправленная, т.е. без стрелок, она называется ребром. Дуги могут пересекаться, но точки пересечения не являются вершинами графа.

Количество вершин графа называют его порядком. Количество рёбер называют размером графа.

Взвешенный граф

Рёбрам графа могут быть сопоставлены числовые значения, которые называют весами рёбер. Например, вес ребра в графе, обозначающем дорожную сеть, может представлять собой длину соответствующей дороги между вершинами графа, обозначающими населённые пункты.

Мультиграф

Две вершины называют концевыми вершинами (концами) ребра, которое их соединяет. При этом говорят, что ребро инцидентно каждой из соединяемых им вершин, и наоборот, каждая концевая вершина называется инцидентной соединяющему их ребру. Две концевые вершины одного и того же ребра называют соседними.

Рёбра, имеющие общую концевую вершину, называют смежными. Рёбра, инцидентные одной и той же паре вершин (т.е. соединяющие одну и ту же пару вершин) называют кратными, или параллельными.

Псевдограф

Ребро, концами которого является одна и та же вершина, называется петлёй.

Ещё немного о вершинах

Вершина называется изолированной, если она не является концом ни для одного ребра. Вершина называется висячей (листом), если она является концом ровно одного ребра.

Путь в графе

Циклом называют путь, в котором первая и последняя вершины совпадают. Путь (или цикл) называют простым, если рёбра в нём не повторяются. Простой путь (цикл) называют элементарным, если вершины в нём не повторяются.

Длиной пути (или цикла) называют количество составляющих его рёбер.

Неориентированный и ориентированный граф

В неориентированном графе связи между любыми парами концевых вершин являются двунаправленными, т.е. эти концевые вершины «равноправны» по отношению к этой связи.

В ориентированном графе связи между концевыми вершинами являются направленными. Рёбра ориентированного графа называют дугами. Пути в ориентированном графе называют ориентированными путями (маршрутами). Замкнутый путь (цикл) в ориентированном графе называют контуром.

Полный направленный граф называют турниром.

Способы представления графов

1. Графический способ — изображение графа.

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

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

Для взвешенного графа возможен вариант матрицы смежности, где в ячейках записываются веса рёбер или нули (либо ячейки оставляются пустыми).

4. Матрица инцидентности — таблица, столбцы которой соответствуют вершинам, а строки – рёбрам. При этом в ячейках на их пересечении записываются числа:

Как решать задание №1?

Пример 1. На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите сумму длин дорог между пунктом А и пунктом Б, и между пунктом Е и пунктом К. В ответе запишите целое число.

Пример 2. На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Г в пункт Е. В ответе запишите целое число.

Пример 3. На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите, какова сумма протяженностей дорог из пункта А в пункт D и из пункта G в пункт С. В ответ запишите целое число.

Пример 4. На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам A и G на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Ответы к примерам заданий №1

1. 16; 2. 33; 3. 66; 4. 67.

Ниже представлены замечательные материалы, подготовленные Поляковым Константином Юрьевичем, доктором технических наук. В них вы найдёте всё самое полезное для себя — теория, решения заданий и практика. Все материалы для ЕГЭ по информатике: https://kpolyakov.spb.ru/school/ege.htm.

Смотреть в PDF:

Или прямо сейчас: cкачать в pdf файле.

Логические выражения несколько отличаются от обычных математических. Например, Выражение 1 + 1 = 1 не имеет никакого смысла с точки зрения математики, но абсолютно верно с точки зрения логики. Логика оперирует понятиями Истина и Ложь, или True и False, или 1 и 0. Поэтому логическая сумма двух истинных высказываний также является истинной.

Цель урока: научиться строить таблицы истинности и логические схемы сложных логических выражений и решать задание №2 из ЕГЭ по информатике 2023.

А как преподают компьютерные курсы в Skysmart? Какие есть направления для преподавания? Подробности по ссылке!

Повторяем определение логических операций

В алгебре логики изучаются логические операции, производимые над высказываниями. Такие высказывания могут быть истинными или ложными. Применяя к простым высказываниям логические операции, можно строить составные высказывания.

Повторим основные логические операции (буквами A, B или C будем обозначать элементарные логические высказывания):

Отрицание (инверсия, логическое НЕ) — это логическая операция, которая делает ложное высказывание истинным, а истинное — ложным.

Обозначение: ¬A, или not(A), или НЕ(A),или

Логическое сложение (дизъюнкция, логическое ИЛИ) — это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно, и ложно тогда и только тогда, когда оба простых логических выражения ложны.

Обозначение: A ∨ B, или A or B, или A ИЛИ B, или A + B

Логическое умножение (конъюнкция, логическое И) — это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложное выражение ложно.

Обозначение: A ∧ B, или A and B, или A И B, или A * B

Логическое следование (импликация) — это сложное логическое выражение, которое истинно во всех случаях, кроме того случая, когда из истины следует ложь. То есть данная логическая операция связывает два простых логических выражения, из которых первое (А) является условием, а второе (В) является следствием.

Логическая эквивалентность (равносильность) — это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.

Обозначение: A ≡ B

Обозначение: A ⊕ B

Вспоминаем порядок выполнения логических операций

Порядок выполнения логических операций в сложном логическом выражении:

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

Законы алгебры логики — это некоторые стандартные преобразования логических выражений, при которых сохраняется равносильность.

1. Законы поглощения констант

A + 0 = A

A * 1 = A

2. Законы поглощения переменных

A + 1 = 1

A * 0 = 0

3. Законы идемпотентности

A * A = A

A + A = A

4. Закон двойного отрицания

5. Закон противоречия

6. Закон исключенного третьего

A * B = B * A

A + B = B + A

(A * B) * C = A * (B * C)

(A + B) + C = A + (B + C)

A * (B + C) = (A * B) + (A * C)

A + (B * C) = (A + B) * (A + C) — обратите особое внимание!

10. Законы де Моргана

Правило для запоминания: «Крыша упала, знак поменяла (+ на *, * на +)».

A + (A * B) = A

A * (A + B) = A

12. Закон преобразования импликации

Учимся упрощать сложные логические выражения

После этого можно тренироваться в упрощении логических выражений.

Логическое выражение будем обозначать буквой F. В качестве упрощения логического выражения удобно заменить логические символы конъюнкции и дизъюнкции на * и +, а затем можно избавиться и от импликации (при использовании программного метода импликацию в логическом выражении заменяют на выражение <=).

Теперь можно переходить к изучению тонкостей и особенностей решения задания №2 по информатике.

Строим таблицы истинности и логические схемы

Таблица истинности выражения определяет его значения при всех возможных комбинациях исходных данных. Если известна только часть таблицы истинности, соответствующее логическое выражение однозначно определить нельзя, поскольку частичной таблице могут соответствовать несколько разных логических выражений (не совпадающих для других вариантов входных данных).

Количество разных логических функций, удовлетворяющих неполной таблице истинности, равно

, где k  — число отсутствующих строк.

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

После получения полной таблицы истинности остается провести анализ на соответствие строк данной в условии части таблицы строкам составленной. При анализе строк особое внимание следует обратить на значение выражения в таблице истинности.

Используем 3 способа решения задания

Способы решения задания:

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

После преобразования логического выражения производится анализ данной в условии таблицы истинности (или ее фрагмента) и для каждого столбца находится его значение (x, y и т. д.)

При использовании электронных таблиц самым сложным является ввод в ячейку таблицы выражения, данного в условии в нотации, соответствующей программе. Чаще всего в качестве программ электронных таблиц используются электронные таблицы пакетов Libre Office, Open Office или Microsoft Office (Excel). Последняя — наиболее распространенная, поэтому здесь будем говорить про нее.

Шаг 1. Сначала количество столбцов в электронной таблице равно количеству переменных логического выражения. Каждый столбец обозначается по именам переменных логического выражения.

Шаг 2. Затем добавляется количество строк электронной таблицы, равное

, где k — количество переменных логического уравнения.

Шаг 3. После этого создается еще один столбец электронной таблицы, в первой строке которого (не заголовка) записывается формула, соответствующая логическому выражению. Растянув эту формулу при помощи маркера автозаполнения на все строки таблицы, получаем полную таблицу истинности выражения.

Таблица функций электронной таблицы Excel и их соответствия логическим операциям:

При использовании программы на языке Python можно описать функцию, например так:

def f(arg):x, y, z, w = argreturn (здесь записывается логическое выражение),

а затем, используя полный переборный алгоритм, перебрать значения 0 и 1 для каждой переменной во вложенных циклах и провести проверку истинности выражения:

print (‘x y w z’) # заголовок таблицы (в алфавитном порядке) k = 0, 1 # k — кортеж констант (0 — False, 1 — True) for x in k: for y in k: for w in k: for z in k: if f(x, y, w, z) == 1: print(x, y, w, z) # если F = 1

Или просто вывести таблицу истинности print(x, y, w, z), не используя условный оператор во внутреннем цикле.

Полученную таблицу истинности остается проанализировать вручную и записать единственно верный ответ.

Для того чтобы записать логическое выражение на Python, воспользуйтесь следующей таблицей:

В Python логическое значение True воспринимается как 1, а False — как 0, благодаря этому можно использовать обычное умножение *

В Python логическое значение True воспринимается как 1, а False — как 0, благодаря этому можно использовать обычное сложение +

Желаем вашим ученикам высоких баллов по ЕГЭ!

Мы рекомендуем всем, кто готовит и готовится к сдаче ЕГЭ, ограничиться возможностями PascalABC.NET 3.8.3. Эта версия вышла в начале марта 2022 года. Язык продолжает развиваться и совершенствоваться, но невозможно обеспечить на станциях ЕГЭ наличие самой последней версии программного обеспечения. Использование более ранних версий лишит школьника некоторых имеющихся в языке возможностей и потребует самостоятельно искать для них эквивалентные замены.

Мы призываем тех работников образования, от которых зависит состояние программных средств на станциях ЕГЭ, заблаговременно установить любую доступную сборку версии 3.8.3 или выше.

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

Рекомендуется скачивать текущую версию на сайте.

Об этом документе

Здесь представлены решения некоторых задач демонстрационного варианта ЕГЭ по информатике 2021.

Решения даются с кратким описанием алгоритма и концентрируются в основном на демонстрации возможностей языка.

Решения сбалансированы по простоте записи и восприятия в балансе с новыми возможностями.

В сети можно встретить либо более длинные и непонятные решения на старом языке Паскаль либо переусложнённые и малопонятные для школьника решения с использованием всех возможностей языка. Ни тот ни другой стиль записи программ нами не рекомендуется.

Великолепный разбор задач типа 25 и 26 ЕГЭ по информатике 2021 на чистом PascalABC.NET дан К.Ю.Поляковым в данной презентации. Здесь представлены наиболее эффективные и неочевидные решения.

PascalABC.NET – современный диалект языка программирования Паскаль, позволяющий записывать код компактно и понятно, используя современные языковые возможности. Это делает программу яснее и как следствие сокращает число возможных ошибок на ЕГЭ по информатике, связанных с волнением и другими субъективными причинами.

Данный текст составлен разработчиками языка и рассматривает ряд вопросов, связанных с использованием PascalABC.NET при сдаче ЕГЭ по информатике. Он ориентирован:

Важно! Данный текст не рассматривает вопросы, связанные с методикой решения задач. Он лишь описывает то, как на PascalABC.NET сделать запись алгоритмов лучше, сохранив при этом эффективность.

PascalABC.NET имеет множество языковых возможностей и множество стилей программирования, поскольку обобщает современные языковые и библиотечные возможности сразу нескольких современных языков программирования (C#, Python, Kotlin).

При решении задач ЕГЭ по информатике мы рекомендуем использовать лишь ограниченный набор возможностей PascalABC.NET, которые делают текст программы яснее и короче, позволяя концентрироваться на сути алгоритма, а не на технических деталях.

К базовым возможностям языка, рекомендуемым нами при решении задач ЕГЭ, относятся:

Кроме того, в некоторых задачах уместно использование лямбда-выражений как параметров стандартных методов.

Все представленные здесь решения сбалансированно сочетают простоту и понятность записи и использование новых возможностей.

Решение 1. Минимум новых возможностей; длинная запись условия, уводящая от сути

Ответ. 1568 7935

Решение 2. Использование методов Divs и DivsAny

Решение 2а. Заметим, что максимальный элемент является последним удовлетворяющим условию

Решение 3. Использование последовательностей

// Рассмотрим последовательность целых от 1016 до 7937, делящихся на 3 и не делящихся ни на одно из 7, 17, 19, 27

// Выведем количество элементов этой последовательности и ее максимальный элемент

Замечание. Аналогично предыдущему вместо seq.Max можно использовать seq.Last

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

Без использования функции

Более эффективное, в котором список делителей не пополняется если уже содержит более двух делителей. Это решение — на случай достаточно больших значений N, что трудно представить на ЕГЭ

// Это условие даёт более эффективное решение

Данное решение тем не менее будет медленно работать при очень больших N, однако подобное усложнение невозможно на ЕГЭ — оно делает задачу олимпиадной. Однако, решение есть и в этом случае. Оптимизации решения задачи 25 рассмотрены в презентации К.Ю. Полякова.

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

В первой строке входного файла находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 10 000) и N – количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке. Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.

Пример входного файла:

При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера:

Решение скорее всего позаимствовано с сайта К. Полякова с косметическими правками в стиле PascalABC.NET.

Решения аналогичных задач на чистом PascalABC.NET содержатся в презентации К.Ю. Полякова.

Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

Пример организации исходных данных во входном файле:

6
1 3
5 12
6 9
5 4
3 3
1 1

Для указанных входных данных значением искомой суммы должно быть число 32. В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B. Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Далее рассматриваются задачи, которые не требуют решения в виде программы, однако с помощью программы можно проверить ответ.

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.

Для решения используется функция Bin модуля School, содержащего ряд базовых математических алгоритмов:

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б) нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

ПОКА условие
последовательность команд
КОНЕЦ ПОКА

выполняется, пока условие истинно.

ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 70 идущих подряд цифр 8? В ответе запишите полученную строку.

НАЧАЛО
ПОКА нашлось (2222) ИЛИ нашлось (8888)
ЕСЛИ нашлось (2222)
ТО заменить (2222, 88)
ИНАЧЕ заменить (8888, 22)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Решение. Условие — слишком длинное ))

Значение арифметического выражения: 497 + 721 – 7 – записали в системе счисления с основанием 7. Сколько цифр 6 содержится в этой записи?

Пояснение 49bi, 7bi — это константы типа BigInteger

Решение 2. Используем стандартный метод ToBase модуля School и стандартный метод последовательностей CountOf:

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

// Возьмём большой диапазон a: от 1 до 10000

// Если для всех натуральных x (возьмём некоторый большой диапазон)
// выполняется условие задачи, то мы нашли a

Тип BigInteger указан “на всякий случай” — если будут возникать очень большие целые. В задачах ЕГЭ — вряд ли

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

Чему равно значение функции F(26)?

На уроке рассматривается разбор 2 задания ЕГЭ по информатике, дается подробное объяснение того, как решать подобные задачи

2-е задание: «Таблицы истинности»

Требуется использование специализированного программного обеспечения

Примерное время выполнения

— 3 минуты.

Проверяемые элементы содержания: Умение строить таблицы истинности и логические схемы

Типичные ошибки и рекомендации по их предотвращению:

«Игнорирование прямо указанного в условии задания требования, что заполненная таблица истинности не должна содержать одинаковых строк. Это приводит к внешне правдоподобному, но на самом деле неверному решению»

ФГБНУ «Федеральный институт педагогических измерений»

Таблицы истинности и порядок выполнения логических операций

Для логических операций приняты следующие обозначения:

Таблица истинности операции НЕ

Таблица истинности операции И (конъюнкция)

Таблица истинности операции ИЛИ (дизъюнкция)

Сложение по модулю 2 (XOR):

Порядок выполнения операций:

Еще о логических операциях:

О преобразованиях логических операций читайте здесь.