гарантируется что искомая сумма не превосходит 107

Тренировочный вариант ЕГЭ №210308 по информатике с ответами 100 баллов

ПОДЕЛИТЬСЯ

Тренировочный вариант ЕГЭ 2021-2022 по информатике КИМ №210308 (№14) для 11 класса с ответами и решением для подготовки к экзамену на 100 баллов от 08.03.2021 (8 марта 2021 года), вариант составлен по новой демоверсии ФИПИ.

Ссылка для скачивания пробного ЕГЭ: задания и ответы

Ответы и решения для заданий опубликованы в конце варианта.

Решу ЕГЭ по информатике тренировочный вариант №210308 с ответами онлайн:

Ответы и задания из варианта:

1)На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта А в пункт В. В ответе запишите целое число – так, как оно указано в таблице.

Правильный ответ: 11

2)Логическая функция F задаётся выражением (¬x /\ y /\ z /\ ¬w) \/ (¬x /\ y /\ ¬z /\ ¬w) \/ (x /\ y /\ z /\ ¬w). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z.

Правильный ответ: zxwy

3)Ниже представлены две таблицы из базы данных. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных общее число дочерей и внучек у Баурн А.С.

Правильный ответ: 4

4)По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А – 0; Б – 111; В – 100. Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Правильный ответ: 110

5)У исполнителя Утроитель две команды, которым присвоены номера: 1. вычти 2 2. умножь на три Первая из них уменьшает число на экране на 2, вторая – утраивает его. Запишите порядок команд в программе получения из 11 числа 13, содержащей не более 5 команд, указывая лишь номера команд. (Например, 21211 – это программа: умножь на три вычти 2 умножь на три вычти 2 вычти 2, которая преобразует число 2 в 8). (Если таких программ более одной, то запишите любую из них.)

Правильный ответ: 11121

6)Запишите подряд (без пробелов) наименьшее и наибольшее значение числа d, которое нужно ввести, чтобы после выполнения программы было напечатано 195?

Правильный ответ: 100107

7)Рисунок размером 256 на 256 пикселей занимает в памяти 40 Кбайт. Найдите максимально возможное количество цветов в палитре изображения.

Правильный ответ: 32

8)Вася составляет четырехбуквенные слова, в которых встречаются только буквы Е, Ж, З, И, причём в каждом слове есть ровно одна гласная буква. Каждая из допустимых согласных букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Правильный ответ: 64

9)Откройте файл электронной таблицы, содержащей вещественные числа — результаты ежечасного измерения температуры воздуха на протяжении трёх месяцев. Найдите количество суток, в которых среднее значение температуры не меньше 18 °С.

Правильный ответ: 79

10)С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «поэт» или «Поэт» в тексте романа в стихах А.С. Пушкина «Евгений Онегин». Другие формы слова «поэт», такие как «поэты», «поэтами» и т.д., учитывать не следует. В ответе укажите только число.

Правильный ответ: 18

11)При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы Ш, К, О, Л, А (таким образом, используется 5 различных символов). Каждый такой пароль в компьютерной системе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Определите объём памяти в битах, отводимый этой системой для записи 30 паролей.

Правильный ответ: 1440

12)Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).

Правильный ответ: 7

13)На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Ж?

Правильный ответ: 22

14)Значение арифметического выражения: 255 + 5 15 − 25 записали в системе счисления с основанием 5. Сколько цифр «4» содержится в этой записи?

Правильный ответ: 8

15)Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула (¬ДЕЛ(x, A) ˄ ДЕЛ(x, 15)) → (¬ДЕЛ(x, 21) ˅ ¬ДЕЛ(x, 15)) истинна при любом натуральном значении x?

Правильный ответ: 105

16)Алгоритм вычисления функции F(n) задан следующими соотношениями: F(n)=2⋅n при n Правильный ответ: 15287

Правильный ответ: 3632319207

18)Квадрат разлинован на N×N клеток (1 Правильный ответ: 684105

19)Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 65. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 65 или больше камней. В начальный момент в куче было S камней, 1≤ S ≤64. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Укажите минимальное значение числа S, при котором Петя может выиграть в один ход.

Правильный ответ: 33

20)Для игры, описанной в предыдущем задании, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: — Петя не может выиграть за один ход; — Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания.

Правильный ответ: 1631

21)Для игры, описанной в задании 19, найдите максимальное значение S, при котором одновременно выполняются два условия: — у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; — у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Правильный ответ: 30

22)Ниже на разных языках записан алгоритм. Получив на вход число x, алгоритм печатает два числа a и b. Укажите наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 45, а потом 5.

Правильный ответ: 59

23)Исполнитель К17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 2 3. Умножить на 2 Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 2. Программа для исполнителя К17 – это последовательность команд. Сколько существует таких программ, которые преобразуют исходное число 3 в число 13 и при этом траектория вычислений программы содержит числа 9 и 11? Траектория должна содержать оба указанных числа. Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.

Правильный ответ: 68

24)Текстовый файл состоит не более чем из 106 символов X, Y и Z. Определите максимальное количество подряд идущих одинаковых символов. Для выполнения этого задания следует написать программу.

Правильный ответ: 19

25)Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [600; 30000], числа, имеющие ровно три различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти делители каждый на каждой строке через пробел в порядке возрастания произведения этих делителей. Делители в строке также должны следовать в порядке возрастания.

26)Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Администратор хочет сэкономить место на диске для хранения архивов. Изза этого он выбирает K наибольших по объему архивов и удаляет их. Тем самым сэкономив место на диске. Известно, какой объём занимает файл каждого пользователя. По заданной информации об объёме файлов пользователей, определите сэкономленное администратором место. Входные данные. В первой строке входного файла находятся два числа, расположенные через пробел: N – количество пользователей (натуральное число большее 10, не превышающее 1000000) и K – количество файлов, которые администратор удаляет (K

Источник

Информатика

2020 2021 УЧЕБНЫЙ ГОД ТЕХНОЛОГИЧЕСКИЙ ПРОФИЛЬ

понедельник, 25 октября 2021 г.

Обработка числовой информации в ЭТ

четверг, 21 октября 2021 г.

1) Рассматривается множество целых чисел, принадлежащих отрезку [1325; 15367], которые делятся на 13 и не делятся на 7, 17, 19 и 23. Найдите количество таких чисел и минимальное из них. В ответе запишите два числа через пробел: сначала количество, затем минимальное число.

2) Рассматривается множество целых чисел, принадлежащих отрезку [1390; 12567], которые делятся на 3 или на 5 и не делятся на 7, 11, 13 и 23. Найдите количество таких чисел и максимальное

3) Рассматривается множество целых чисел, принадлежащих числовому отрезку [3394; 8599], которые удовлетворяют следующим условиям:

− остаток от деления на 3 равен 1;

− остаток от деления на 7 равен 5.

Найдите наибольшее из таких чисел и их сумму. Гарантируется, что искомая сумма не превосходит 107.

среда, 20 октября 2021 г.

вторник, 19 октября 2021 г.

2. Квадрат разлинован на N×N клеток (1

Система оценивания

Решение, правильно работающее только для случаев, когда числа K и S не превосходят 100, будет оцениваться в 6 баллов.

Решение

Посчитаем стоимость ручки в копейках после подорожания — она будет равна K * 100 + K * P (один процент стоимости ручки составляет K копеек). Затем переведем S рублей в копейки (умножив на 100) и поделим нацело на стоимость ручки после подорожания.

Пример решения на языке Python

Типичной ошибкой в этой задаче было использование действительных чисел для представления стоимости ручки после подорожания (если стоимость ручки хранить в рублях). Поскольку действительные числа представляются неточно, то после деления значения S на действительное число K + K * P / 100 может получиться не целое число, а число, которое чуть меньше правильного целого результата, и в результате преобразования частного к целому числу путём отбрасывания дробной части ответ получался на 1 меньше правильного. Такие решения набирали, как правило, 7 баллов.

Пример решения с использованием действительных чисел (7 баллов)

Задание 2. «Плот»

Посередине озера плавает плот, имеющий форму прямоугольника. Стороны плота направлены вдоль параллелей и меридианов. Введём систему координат, в которой ось OX направлена на восток, а ось ОY – на север. Пусть юго-западный угол плота имеет координаты (x₁, y₁), северо-восточный угол – координаты (x₂, y₂).

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

Программа получает на вход шесть чисел в следующем порядке: x₁, y₁ (координаты юго-западного угла плота), x₂, y₂ (координаты северо-восточного угла плота), x, y (координаты пловца). Все числа целые и по модулю не превосходят 100. Гарантируется, что

Например, программа должна вывести NE при условиях x > x₂ и y > y₂, вывести N при условиях y > y₂ и x₁ y₂. Аналогично нужно вывести букву S всегда при выполнении условия y x₂. При этом все «угловые» направления NW, NE, SW, SE получатся автоматически — сначала будет выведена одна из букв N или S, а затем одна из букв W или E. Такое решение содержит всего четыре условные инструкции if.

Пример решения на языке Python

Задание 3. «Пакуем чемоданы!»

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

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

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

Определите вес рюкзака и чемодана после того, как Алёна сложит все вещи.

Первая строка входных данных содержит число S – максимально разрешённый вес рюкзака. Во второй строке входных данных записано число N – количество предметов.

В следующих N строках даны массы предметов, сами предметы перечислены в порядке убывания ценности (сначала указана масса самого ценного предмета, затем масса второго по ценности предмета и т. д.). Все числа натуральные, число S не превосходит 2×109, сумма весов всех предметов также не превосходит 2×109. Значение N не превосходит 105

Программа должна вывести два числа – вес рюкзака и вес чемодана (вес пустого рюкзака и чемодана не учитывается).

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

8Максимально возможная масса рюкзака 20 кг. Дано 5 предметов весом 6, 10, 5, 2, 3

Сначала предмет весом 6 кладётся в рюкзак, затем предмет весом 10 тоже кладётся в рюкзак. Предмет весом 5 нельзя положить в рюкзак, так как тогда вес рюкзака станет 21 кг, поэтому предмет весом 5 кладётся в чемодан. Затем предмет весом 2 кладётся в рюкзак, а предмет весом 3 – в чемодан. Вес рюкзака 6 + 10 + 2 = 18, вес чемодана 5 + 3 = 8.

Система оценивания

Решение, правильно работающее только для случаев, когда все входные числа не превосходят 100, будет оцениваться в 4 балла.

Решение

Эта задача оказалась самой простой для большинства участников. Действительно, в этой задаче нет ни «подводных камней», как в первой задаче, ни объёмного разбора случаев, как во второй задаче. Необходимо просто реализовать тот алгоритм, который описан в условии: завести две переменные для хранения массы рюкзака и массы чемодана, считывать очередное число и прибавлять его либо к массе рюкзака, либо к массе чемодана, следя за тем, чтобы масса чемодана не превышала значения S.

Пример решения на языке Python

Типичная ошибка в этой задаче — использование строгого неравенства s1 + a 3 ), то есть время работы такой программы растёт пропорционально N 3 и набирает 40 баллов.

Пример решения на языке Python (40 баллов)

Сложность этого решения можно уменьшить до O(N 2 ), если максимум на отрезке считать быстрее. Для этого можно заметить, что при увеличении правой границы j на 1 к рассматриваемому отрезку добавляется один элемент, поэтому можно хранить текущее значение максимума на отрезке и при увеличении j новый добавляемый к отрезку элемент сравнивать с максимумом, обновляя максимум при необходимости. Но такое решение тоже не получает максимальный балл.

Для того, чтобы придумать правильное и эффективное решение заметим, что ответ (высоты наилучшего маршрута) всегда имеет вид, как в примере (15, 20, 20, 10) — все значения кроме двух крайних равны, а два крайних меньше их. Иначе можно сократить маршрут, оставив только два крайних значения, меньших наибольшего значения на маршруте. Поэтому можно изучать только последовательности равных идущих подряд элементов массива, среди всех таких последовательностей нужно выбрать последовательность наименьшей длины, причём перед и после этой последовательности должны быть меньшие значения. При этом алгоритм должен иметь сложность O(N), иначе программа также не сможет уложиться в ограничение по времени в 1 секунду.

Решение можно реализовать и без использования массива для хранения всех даннях чисел. Будем считывать числа по одному, при этом будем использовать следущие переменные:

Пусть значение нового считанного элемента равно h. Если h = last_height, то новый элемент продолжает последовательность элементов равных last_height, потому увеличим значение last_len на 1. Если же новый элемент неравен last_height, то этот элемент начинает новуй последовательность равных элементов, поэтому запишем его значение в переменную last_height, переменной last_len присвоим значение 1, а старое значение last_height переместится в переменную prev_height. Но сначала проверим, является ли последовательность элементов равных last_height, удовлетворяющей условию задачи, что означает выполнение неравенств prev_height h. Если эти неравенства верны, а также если длина последовательности last_len наименьшая (для этого будем также хранить наименьшую известную длину последовательности, удовлетворяющую условию задачи в переменной best_len), то запомним ответ и обновим значение переменной best_len.

Пример решения на языке Python (100 баллов)

Задание 5. Делимость

Сегодня в школе на уроке математики проходят делимость. Чтобы продемонстрировать свойства делимости, учитель выписал на доске все целые числа от 1 до N в несколько групп, при этом если одно число делится на другое, то они обязательно оказались в разных группах. Например, если взять N = 10, то получится 4 группы.

Вы уже догадались, что, поскольку любое число делится на 1, одна группа всегда будет состоять только из числа 1, но в остальном подобное разбиение можно выполнить различными способами. От вас требуется определить минимальное число групп, на которое можно разбить все числа от 1 до N в соответствии с приведённым выше условием.

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

Система оценивания

Решение

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

Пример решения на языке Python (20 баллов)

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

Пример решения на языке Python (100 баллов)

Источник