ВАРИАНТ 7

Часть 1

Ответами к заданиям 1—23 являются число, последовательность букв или цифр, которые следует записать в БЛАНК ОТВЕТОВ № 1 справа от номера соответствующего задания, начиная с первой клеточки, без пробелов, запятых и других дополнительных символов. Каждый символ пишите в отдельной клеточке в соответствии с приведёнными в бланке образцами.

1. Сколько значащих нулей в двоичной записи числа 188?

Ответ: ______________­________________ .

2. Дан фрагмент таблицы истинности выражения F, зависящего от трёх аргументов X, Y, Z:

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

Ответ: ______________­________________ .

3. Между четырьмя местными аэропортами ЛЕСНОЙ, ЗИМА, КРАЙ и ПОЛЯНА, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:

Аэропорт вылета	Аэропорт прилёта	Время вылета	Время прилёта
ПОЛЯНА	КРАЙ	06:20	08:35
КРАЙ	ЛЕСНОЙ	10:25	12:35
ЛЕСНОЙ	КРАЙ	11:45	13:30
ЗИМА	ПОЛЯНА	12:15	14:25
ПОЛЯНА	ЛЕСНОЙ	12:45	16:35
КРАЙ	ПОЛЯНА	13:15	15:40
ЛЕСНОЙ	ПОЛЯНА	13:40	17:25
ЛЕСНОЙ	ЗИМА	15:30	17:15
ПОЛЯНА	ЗИМА	17:35	19:30
ЗИМА	ЛЕСНОЙ	19:40	21:55

Путешественник оказался в аэропорту ЛЕСНОЙ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт ПОЛЯНА.

Ответ: ______________­________________ .

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

Символ “?” (вопросительный знак) означает ровно один произвольный символ.

Символ “*” (звёздочка) означает любую последовательность символов произвольной длины, в том числе “*” может задавать и пустую последовательность.

В каталоге находятся пять файлов:

Ниже представлено восемь масок. Сколько из них таких, которым соответствует ровно три файла из данного каталога?

Ответ: ______________­________________ .

5. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код:

А-110, Б-0, В-111, Г-100. Каким кодовым словом должна кодироваться буква Д? Если таких вариантов несколько, укажите самый короткий.

Ответ: ______________­__________________ .

6. В некоторой информационной системе информация кодируется двоичными шестиразрядными словами. При передаче данных возможны их искажения, поэтому в конец каждого слова добавляется седьмой (контрольный) разряд таким образом, чтобы сумма разрядов нового слова, считая контрольный, была чётной. Например, к слову 101101 справа будет добавлен 0, а к слову 010110 — 1.

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

Приведём фрагмент кодовой таблицы, используемый в данной задаче:

Буква	Кодовое слово	Примечание
x	000000	сбой
А	100001
В	011010
С	110010
D	110011

Исходное сообщение АВС было передано в виде:

1000010 0110101 1100101

И затем было принято в виде:

1100110 0110101 1100100.

Как будет выглядеть принятое сообщение после обработки? В ответе запишите последовательность букв без пробелов и знаков препинания.

Ответ: ______________­__________________ .

7. Дан фрагмент электронной таблицы:

	А	В	С	D
1	3		5
2	=(А1+С1)/4	=С1-1	=А2/2	=В1/2

Какое число должно быть записано в ячейке В1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек A2:D2 соответствовала рисунку?

Ответ: ______________­__________________ .

8. Определите, что будет напечатано в результате выполнения следующего фрагмента программы:

Бейсик	Паскаль
Си	Алгоритмический язык

Ответ: ______________­__________________ .

9. Какова ширина (в пикселях) прямоугольного 64-цветного неупакованного растрового изображения, занимающего на диске 1,5 мегабайта, если его высота вдвое меньше ширины? В ответе запишите только целое число, единицу измерения писать не нужно.

Ответ: ______________­_________________ .

10. Вася и Петя передают друг другу сообщения, используя синий и красный фонарики. Эти они делают, включая фонарики последовательно на одинаково короткое время в некоторой комбинации. Количество вспышек в одном сообщении — от 1 до 5. Сколько различных сообщений могут передавать мальчики?

Ответ: ______________­_________________ .

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

F(n) = F(n - 1) + F(n/2), при n > 1 и n кратно 2

F(n) = F(n - 1) + 1, при n > 1 и n не кратно 2

F(1) = 1

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

(В ответе запишите только натуральное число.)

Ответ: ______________­__________________ .

12. В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.

По заданным IP-адресу узла и маске определите адрес сети.

IP-адрес узла: 209.135.205.15

Маска: 255.255.248.0

При записи ответа выберите из приведённых в таблице чисел четыре элемента IP-адреса и запишите в нужном порядке соответствующие им буквы. Точки писать не нужно.

А	В	С	D	Е	F	G	Н
0	15	135	200	205	209	248	255

Пример

Пусть искомый IP-адрес 192.168.128.0, и дана таблица

А	В	С	D	Е	F	G	Н
128	168	255	8	127	0	17	192

В этом случае правильный ответ будет записан в виде: HBAF

Ответ: ______________­__________________ .

13. Для регистрации на сайте онлайн-магазина пользователю предлагается придумать пароль, состоящий из 6 символов. Правилами безопасности сайта разрешается использовать только символы латинского алфавита (строчные и прописные). При этом используется посимвольное кодирование и в памяти сервера для кодирования каждого символа используется минимально возможное и одинаково целое количество бит. А для хранения всего пароля используется минимально возможное целое количество байт. Какое количество информации (в байтах) требуется для хранения паролей 80 пользователей?

Ответ: ______________­__________________ .

14. Система команд исполнителя РОБОТ, “живущего” в прямоугольном лабиринте на клетчатой плоскости включает 4 команды-приказа и 4 команды проверки условия. Команды-приказы:

вверх

вниз

влево

вправо

При выполнении этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.

Если РОБОТ начнет движение в сторону находящейся рядом с ним стены, то он разрушится и программа прервётся.

Другие четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:

сверху свободно

снизу свободно

слева свободно

справа свободно

Цикл

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

В конструкции

выполняется команда, если условие истинно. Если условие ложно, происходит переход к следующей команде.

Сколько клеток лабиринта соответствует требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)?

Ответ: ______________­__________________ .

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

Ответ: ______________­__________________ .

16. Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 23, запись которых в двоичной системе счисления оканчивается на 101.

Ответ: ______________­__________________ .

17. В языке запросов к поисковому серверу для обозначения логической операции “ИЛИ” используется символ |, а для логической операции “И” — &. В таблице приведено количество страниц, которое находит поисковая система по каждому запросу.

Запрос	Количество найденных страниц
(Клавиатура | Мышь) & Джойстик	11700
Клавиатура & Джойстик	7300
Мышь & Джойстик	5900

Какое количество страниц будет найдено по запросу: Клавиатура & Мышь & Джойстик? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Ответ: ______________­__________________ .

18. Какое наибольшее целое число удовлетворяет логическому условию:

Ответ: ______________­_________________ .

19. В программе используется целочисленный массив А с индексами от 0 до 9. Значения элементов массива равны 4; 5; 4; 7; 10; 8; 9; 11; 7; 8 соответственно, т.е. А[0] = 4; А[1] = 5 и т.д.

Определите значение переменной k после выполнения следующего фрагмента программы, записанной ниже на разных языках программирования.

Бейсик	Паскаль
Си	Алгоритмический язык

Ответ: ______________­_________________ .

20. Ниже на четырёх языках записан алгоритм. Получив на вход число х, этот алгоритм печатает два числа: L и М. Укажите наименьшее из таких чисел х, при вводе которых алгоритм печатает сначала 3, а потом 13.

Бейсик	Паскаль
Си	Алгоритмический язык

Ответ: ______________­_________________ .

21. Определите, при каком наибольшем значении b в результате выполнения следующего алгоритма будет напечатано число 50 (для Вашего удобства алгоритм представлен на четырёх языках):

Бейсик	Паскаль
Си	Алгоритмический язык

Ответ: ______________­_________________ .

22. У исполнителя Удвоитель две команды, которым присвоены номера:

1. прибавь 3,

2. умножь на 2.

Первая из них увеличивает число на экране на 3, вторая удваивает его. Программа для Удвоителя — это последовательность команд.

Сколько есть программ, которые число 2 преобразуют в число 26?

Ответ: ______________­__________________ .

23. Сколько существует различных наборов значений логических переменных х₁, х₂, ... х₉, x₁₀, которые удовлетворяют всем перечисленным ниже условиям?

В ответе не нужно перечислять все различные наборы значений х₁, х₂, ... х₉, x₁₀, при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

Ответ: ______________­_________________ .

Не забудьте перенести все ответы в бланк ответов № 1 в соответствии с инструкцией по выполнению работы.

Часть 2

Для записи ответов на задания этой части (24—27) используйте БЛАНК ОТВЕТОВ № 2. Запишите сначала номер задания (24, 25 и т. д.), а затем полное решение. Ответы записывайте чётко и разборчиво.

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

Паскаль	Бейсик
Си	Алгоритмический язык

Последовательно выполните следующее:

1. Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (А, В, С, D и Е). Границы (точки -2, 1, 4 и 7) принадлежат заштрихованным областям (В и D соответственно).

Область	Условие 1 (х >=-2)	Условие 2 (х<= 7)	Условие 3 (x<4)	Программа выведет	Область обрабатывается верно
А
В
С
D
Е

В столбцах условий укажите “да”, если условие выполнится, “нет”, если условие не выполнится, “—” (прочерк), если условие не будет проверяться, “не изв.”, если программа ведёт себя по-разному для разных значений, принадлежащих данной области. В столбце “Программа выведет” укажите, что программа выведет на экран. Если программа ничего не выводит, напишите “—” (прочерк). Если для разных значений, принадлежащих области, будут выведены разные тексты, напишите “не изв.”. В последнем столбце укажите “Да” или “Нет”.

2. Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы. (Это можно сделать несколькими способами, поэтому можно указать любой способ доработки исходной программы.)

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

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

Паскаль	Бейсик
Си	Алгоритмический язык
Русский (естественный) язык
Объявляем массив А из 40 элементов. Объявляем целочисленные переменные I, L, Lmax, S, Smax. В цикле от 1 до 40 вводим элементы массива А с 1-го по 40-й. ...

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

26. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

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

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

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

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

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

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

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

3. Укажите такое значение S, при котором:

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

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

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

Районный методист решила, что оценку “отлично” должны получить 20% участников (целое число, с отбрасыванием дробной части).

Для этого она должна определить, какой балл должен был набрать ученик, чтобы получить “отлично”.

Если невозможно определить такой балл, чтобы “отлично” получили ровно 20% участников, “отлично” должно получить меньше участников, чем 20%.

Если таких участников не окажется (наибольший балл набрали больше 20% участников) — эти и только эти ученики должны получить “отлично”.

Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая должна вывести на экран наименьший балл, который набрали участники, получившие “отлично”. Известно, что информатику сдавало больше 5-ти учеников. Также известно, что есть такое количество баллов, которое не получил ни один участник.

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

<Фамилия> <Имя> <Номер школы> <Количество баллов>,

где <Фамилия> — строка, состоящая не более, чем из 30 символов без пробелов, <Имя> — строка, состоящая не более, чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число диапазоне от 1 до 100. Эти данные записаны через пробел, причём ровно один между каждой парой (то есть, всего по три пробела в каждой строке).

Пример входной строки:

Иванов Иван 50 87

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

78