Пример задания: Сколько единиц в двоичной записи числа 1025? 1) 1 2) 2 3) 10 4) 11 А1 (базовый уровень, время – 1 мин)

Решение: Первый способ: Переведем число 1025 в двоичную систему счисления Правильный ответ: 2 Второй способ: Представим число 1025 в виде суммы чисел, степеней двойки 1025= В каждом таком числе, в двоичном представлении содержится по одной единице Правильный ответ : 2

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.) Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). 1) 9 2) 10 3) 11 4) 12 ABC D EF A 24 B2 1 7 C D 3 3 E F 2 A2 (базовый уровень, время – 2 мин)

Решение: Правильный ответ: 1) 9 D FA B C E Построим основу графа, обозначив каждый населенный пункт соответствующей вершиной Достроим граф, вес каждого ребра равен расстоянию до населенного пункта Найдем самый короткий путь к вершине Е: A B C E 2+1+4=7 Прибавим расстояние от Е до F: 7+2=9

А12 (повышенный уровень, время – 5 мин) В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Ниже представлен фрагмент программы, в котором значения элементов сначала задаются, а затем меняются. for i:=0 to 9 do A[i]:=9-i; for i:=0 to 4 do begin k:=A[i]; A[i]:=A[9-i]; A[9-i]:=k; end; Чему будут равны элементы этого массива после выполнения фрагмента программы? 1) ) ) )

Решение: Рассмотрим, как будет заполняться массив в первом цикле При i=0, A[0] будет равен 9-0=9 При i=1, A[1] будет равен 9-1=8 При i=2, A[2] будет равен 9-2=7 … При i=9, A[9] будет равен 9-9=0 Таким образом, после выполнения первого цикла массив будет заполнен числами for i:=0 to 9 do A[i]:=9-i;

Решение: Рассмотрим второй цикл который выполнится 5 раз: Стандартный алгоритм обмена k:=A[i]; A[i]:=A[9-i]; A[9-i]:=k; Меняет местами элементы A[i] с A[9-i] При i=0 произойдет обмен A[0] A[9] При i=1 произойдет обмен A[1] A[8] for i:=0 to 4 do begin k:=A[i]; A[i]:=A[9-i]; A[9-i]:=k; end;

Решение: При i=0 произойдет обмен A[0] A[9] При i=1 произойдет обмен A[1] A[8] При i=2 произойдет обмен A[2] A[7] При i=3 произойдет обмен A[3] A[6] При i=4 произойдет обмен A[4] A[5] Каждый элемент массива окажется равен своему индексу Правильный ответ: 2)

B7 (повышенный уровень, время – 2 мин) Запись числа в системе счисления с основанием N оканчивается на 3 и содержит 3 цифры. Укажите наибольшее возможное основание этой системы счисления N. Решение: Так как, остаток от деления числа 381 на N равен 3, получается что число N должно без остатка делить число 381-3=378 Для начала определили, что искать будем делитель числа 378

B7 (повышенный уровень, время – 2 мин) Запись числа в системе счисления с основанием N оканчивается на 3 и содержит 3 цифры. Укажите наибольшее возможное основание этой системы счисления N. Решение: Ограничение в три разряда ограничивает круг поиска Первая часть неравенстваПоказывает что N < 19 Вторая часть неравенстваПоказывает что N 8 Остается найти делитель числа 378 на промежутке от 8 до 18

B7 (повышенный уровень, время – 2 мин) Запись числа в системе счисления с основанием N оканчивается на 3 и содержит 3 цифры. Укажите наибольшее возможное основание этой системы счисления N. Решение: На промежутке от 8 до 18 делителями числа 378 являются 9, 14 и 18 Наибольшим является – 18 Для проверки переведем число 381 восемнадцатеричную систему счисления =133 18

B15 (высокий уровень, время – 10 мин) Сколько различных решений имеет логическое уравнение (x 1 x 2 ) (x 2 x 3 ) (x 3 x 4 )= 1 (у 1 у 2 ) (у 2 у 3 ) (у 3 у 4 ) = 1 ( y 1 x 1 ) ( y 2 x 2 ) ( y 3 x 3 ) ( y 4 x 4 ) = 1 где x 1, x 2, …, x 4 и y 1, y 2, …, y 4 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

B15 (высокий уровень, время – 10 мин) Решение: Для удобства преобразуем третье уравнение (y 1 x 1 ) (y 2 x 2 ) (y 3 x 3 ) (y 4 x 4 ) = 1 Получаем систему (x 1 x 2 ) (x 2 x 3 ) (x 3 x 4 )= 1 (у 1 у 2 ) (у 2 у 3 ) (у 3 у 4 ) = 1 (y 1 x 1 ) (y 2 x 2 ) (y 3 x 3 ) (y 4 x 4 ) = 1 (x 1 x 2 ) (x 2 x 3 ) (x 3 x 4 )= 1 (у 1 у 2 ) (у 2 у 3 ) (у 3 у 4 ) = 1 ( y 1 x 1 ) ( y 2 x 2 ) ( y 3 x 3 ) ( y 4 x 4 ) = 1

B15 (высокий уровень, время – 10 мин) (x 1 x 2 ) (x 2 x 3 ) (x 3 x 4 )= 1 (у 1 у 2 ) (у 2 у 3 ) (у 3 у 4 ) = 1 (y 1 x 1 ) (y 2 x 2 ) (y 3 x 3 ) (y 4 x 4 ) = 1 Решение: Рассмотрим первое уравнение: Всего используется четыре переменных: x1, x2, x3, x4 В каждой скобке не должно встретиться сочетание 1 0 Соответственно, возможные решения для первого уравнения – это 0000, 0001, 0011, 0111, 1111

B15 (высокий уровень, время – 10 мин) (x 1 x 2 ) (x 2 x 3 ) (x 3 x 4 )= 1 (у 1 у 2 ) (у 2 у 3 ) (у 3 у 4 ) = 1 (y 1 x 1 ) (y 2 x 2 ) (y 3 x 3 ) (y 4 x 4 ) = 1 Решение: Рассмотрим второе уравнение: Всего используется четыре переменных: y1, y2, y3, y4 В каждой скобке не должно встретиться сочетание 1 0 Соответственно, возможные решения для первого уравнения – это 0000, 0001, 0011, 0111, 1111

B15 (высокий уровень, время – 10 мин) (x 1 x 2 ) (x 2 x 3 ) (x 3 x 4 )= 1 (у 1 у 2 ) (у 2 у 3 ) (у 3 у 4 ) = 1 (y 1 x 1 ) (y 2 x 2 ) (y 3 x 3 ) (y 4 x 4 ) = 1 Решение: Если бы не было третьего уравнения, то каждому набору переменных x 0000, 0001, 0011, 0111, 1111 соответствовал бы набор переменных y, 0000, 0001, 0011, 0111, 1111 Итого решений было бы 5*5=25

B15 (высокий уровень, время – 10 мин) (x 1 x 2 ) (x 2 x 3 ) (x 3 x 4 )= 1 (у 1 у 2 ) (у 2 у 3 ) (у 3 у 4 ) = 1 (y 1 x 1 ) (y 2 x 2 ) (y 3 x 3 ) (y 4 x 4 ) = 1 Решение: Третье уравнение связывает два предыдущих. Причем и здесь не должно встретиться сочетание Набор у Набор х Ответ: 15

C4 (высокий уровень, время – 55 мин) По известным фамилиям и баллам по 4 предметам найти средний балл и вывести на печать фамилию и средний балл лучшего ученика.