Вариант 2020_1 (ФИПИ)

№1. Сколько единиц в двоичной записи шестнадцатеричного числа E1F0₁₆?

Решение

При переводе числа из 16СС в 2СС каждая цифра из 16СС заменяется четырьмя разрядами в 2СС, т.к. 16 = 2⁴

Переведем каждую цифру из 16СС (E, 1, F, 0) в 2 СС

1₁₆= 0001₂

Е₁₆ = 14₁₆ = 1110₂

F₁₆ = 15₁₆ = 1111₂

0₁₆ = 0000₂

E1F0₁₆ = 1110000111110000₂

Примечание: если в числе при переводе в 2СС впереди числа получаются нули, то они зачеркиваются как незначащие, например, 001101010111

Ответ: 8

№ 2

Миша заполнял таблицу истинности функции (x /\ y) \/ (x ≡ z) \/ w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Решение

Т.к. в формуле есть V w и значение функции =0, то значит w = 1 (w = 0)

Единственный вариант поставить w во 2-ой столбик

*w **

Для оставшегося выражения функции (x /\ y) \/ (x ≡ z) построим таблицу истинности

X	Y	Z	F
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

Выберем столбцы, в которых F = 0 и сопоставим с исходной таблицей

X	Y	Z	F				F
0	0	1	0	0	1	0	0
0	1	1	0	0			0
1	1	0	0		0	1	0

В данной таблице только один столбик содержит два нуля. В построенной таблице это соответствует столбику X. Значит первый столбик – X.

X	Y	Z	F	X	Z	Y	F
0	0	1	0	0	1	0	0
0	1	1	0	0			0
1	1	0	0		0	1	0

В построенной таблице только одна строка содержит два нуля, ищем в данной таблице такую же ситуацию (первая строчка). Из нее видим, что 1 соответствует Z. Значит второй столбик Z, третий Y.

Т.о. получаем XWZY.

№3

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

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

A	4	- уникальная точка		1 C F	2 А	3 C F	4	5	6	7
B	3		1 - C F			*			*
C	2		2 - А				*	*	*	*
D	3		3 - C F	*						*
E	3		4		*			*		*
F	2		5		*		*		*
G	3		6	*	*			*
			7		*	*	*

А содержит 4 дороги – пункт 2

C и F содержат две дороги, это пара 1 и 3

Точки D и F содержит 3 дороги и проходят через пункты C и F. Это должно быть пересечение со столбиками 1,3

	1 C F	2 А	3 C F	4	5	6	7
1 - C F			*			*
2 - А				*	*	*	*
3 - C F	*						*
4		*			*		*
5		*		*		*
6 - D и В	*	*			*
7 - D и В		*	*	*

Получаем 6,7 – это D и В

Оставшиеся пункты 4 и 5 – это точки Е и G

Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам E и G на схеме.

Ответ: 45

№ 4

1955

55-33=22

1933

1980

1980-1955=25

1978

1978-1955=23

1955

1984

1984-1955=29

1985

1985-1955=30

1955

1955-1932=23

1964-1932=32

1955

1964

1932

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

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

Ответ: 4

№ 5

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв Б, В, Г используются такие кодовые слова: Б – 101; В – 110; Г – 0.

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

101

110

Ответ: 111

№6

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

1) Строится двоичная запись числа N.

2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописываются два нуля, в противном случае справа дописываются две единицы. Например, двоичная запись 1001 числа 9 будет преобразована в 100111.

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

Укажите минимальное число N, для которого результат работы алгоритма

будет больше 134. В ответе это число запишите в десятичной системе

счисления.

Решение

Алгоритм: N₁₀ N₂ N + 2разряда R₂ R₁₀

R > 134

135₁₀ 2сс

135₁₀ = 10000111₂ (перевести самим!)

100001 11

Применяем алгоритм к числу

100001

если N чётное, в конец числа (справа) дописываются два нуля, в противном случае справа дописываются две единицы. 100001 – нечетное, значит дописываем 11

100001 11

Наше полученное число совпадает со значением 135₁₀ = 10000111₂

Но нас просят найти число N

Значит переводим число 100001 в 10СС

100001₂ = 33₁₀

Ответ: 33

№ 7

Дан фрагмент электронной таблицы. Из ячейки A3 в ячейку C4 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились. Какова сумма числовых значений формул в ячейках A3 и C4?

A3 = $C1 + A$1

$C – не меняется, $1 – не меняется.

A3 C4

Маршрут копирования

C4 = $C2 + С$1

A3 = $C1 + A$1= 3 + 1 = 4

C4 = $C2 + С$1= 8 + 3 = 11

Какова сумма числовых значений формул в ячейках A3 и C4: 4+11= 15

Ответ: 15

№ 8

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

var s, n: integer;

begin

s:= 175;

n:= 0;

while s + n < 325 do

begin

s:= s - 10;

n:= n + 30

end;

writeln(s)

end.

Решение

s = 175 – 10х

n = 0 + 30 х

Программа остановится, когда будет нарушено условие s + n < 325

Значит, берем s + n >= 325

175 – 10х + 0 + 30 х 325

20х >= 150

Х >= 7,5

Х = 8

writeln(s) вывести нужно s

s = 175 – 10х = 175 – 10*8 = 175 – 80 = 95

Ответ 95

№ 9

Обратите внимание!!! Задача на ЗВУКОВУЮ информацию.

Музыкальный фрагмент был записан в формате квадро (четырёхканальная запись), оцифрован и сохранён в виде файла без использования сжатия данных. Размер полученного файла без учёта размера заголовка файла – 12 Мбайт. Затем тот же музыкальный фрагмент был записан повторно в формате моно и оцифрован с разрешением в 2 раза выше и частотой дискретизации в 1,5 раза меньше, чем в первый раз. Сжатие данных не производилось. Укажите размер в Мбайт файла, полученного при повторной записи. В ответе запишите только целое число, единицу измерения писать не нужно. Искомый объём не учитывает размера заголовка файла.

Решение

Формулы:

V = M*t*i*k

V - Объем

M – частота дискретизации

t – время в сек.

i - разрешение

k – количество каналов (моно 1, стерео 2, квадро 4)

1-й файл	2-й файл
V₁ = 12 Мб	V₂ =?
M	М*2
i	i/1,5
K = 4	K = 1
t	t
Время записи не изменилось

t₁ = V₁/(M*i*k₁)

V₂ M*2*i/1,5*k₂

V₁ M*i*k₁

t₂ = V₂/(M*2*i/1,5*k₂)

Приравниваем и выражаем V₂

V₁/(M*i*k₁) = V₂/ (M*2*i/1,5*k₂)

Ответ: 4

№ 10

Вася составляет 5-буквенные слова, в которых есть только буквы В, О, Л, К, причём буква В используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Решение

***** - 5-буквенные слова

ВОЛК – 4 буквы

В - ровно 1 раз

Буква В может стоять в пяти местах – 1,2,3,4,5

В****

*В***

**В**

***В*

****В

На оставшихся местах остаются 3 буквы О, Л, К

В*3*3*3*3 = 81

Аналогично еще 4 раза

3* В*3*3*3 = 81

3* 3* В*3*3 = 81

3* 3*3* В*3 = 81

3* 3*3*3 *В= 81

81*5=405

Ответ: 405

№ 11

procedure F(n: integer);

begin

if n > 0 then

begin

write(n);

F(n - 3);

F(n div 2)

end

end;

Запишите подряд без пробелов и разделителей все числа, которые будут выведены на экран при выполнении вызова F(7). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

Решение: div 2 – целое деление на 2

F(n) =

F(7) = 7, F(4); F(3)

F(4) = 4, F(1); F(2)

F(3) = 3, F(0); F(1)

F(2) = 2, F(-1); F(1)

F(1) = 1, F(-2); F(0)

Ничего не делается, можно зачеркнуть

F(0)

F(-1)

F(-2)

Заполняем снизу вверх

F(7) = 7, F(4); F(3) = 7412131

F(4) = 4, F(1); F(2) = 4121

F(3) = 3, F(0); F(1)= 31

F(2) = 2, F(-1); F(1) = 21

F(1) = 1, F(-2); F(0) = 1

Ответ: 7412131

№ 12

Для узла с IP-адресом 117.191.176.37 адрес сети равен 117.191.160.0. Чему

равен третий слева байт маски? Ответ запишите в виде десятичного числа.

Решение

176 = 10110000

160 = 10100000

Узел

Маска

Сеть

10110000 10110000

******** 11100000

10100000 10100000

11100000 = 224. Ответ: 224

№ 13

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 25 символов и содержащий только символы из 7-символьного набора: С, Д, А, М, Е, Г, Э. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей.

Для хранения сведений о 50 пользователях потребовалось 1200 байт.

Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.

Решение

1) к= 25

N = 7 ® i = 3 бита

V = 25*3=75бит = 75/8 = 10 байт – на один пароль

2) 1200/50 = 24 байта всего на 1 пользователя

3) 24 – 10 = 14 байт – дополнительные сведения

Ответ: 14

№ 14

НАЧАЛО

ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>3)

ЕСЛИ нашлось (>1)

ТО заменить (>1, 22>)

КОНЕЦ ЕСЛИ

ЕСЛИ нашлось (>2)

ТО заменить (>2, 2>)

КОНЕЦ ЕСЛИ

ЕСЛИ нашлось (>3)

ТО заменить (>3, 1>)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Дано: На вход приведённой ниже программе поступает строка, начинающаяся с символа «>», а затем содержащая 10 цифр 1, 20 цифр 2 и 30 цифр 3, расположенных в произвольном порядке.

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

Решение

Алгоритм

ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>3) – это условие того, что задача продолжает решаться

Дано

>11111111112….3…….

10 20 30

Ответ: 110 (если не понятно, могу сделать видео с объяснением, пишите)

№ 15

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

Какова длина самого длинного пути из города А в город М? Длиной пути считать количество дорог, составляющих этот путь.

!!!!Обратите внимание на необычную формулировку вопроса, будет видеоразбор этого задания.

Считаем количество дорог на рисунке и выбираем путь, где количество дорог больше, добавляя по 1 за каждую новую дорогу (стрелку)

Ответ: 9

№ 16

Значение арифметического выражения: 9¹¹*3²⁰ – 3⁹ – 27 – записали в системе

счисления с основанием 3. Сколько цифр 2 содержится в этой записи?

Решение

9¹¹*3²⁰ – 3⁹ – 27 = 3²²*3²⁰ – 3⁹ – 3³ = 3⁴² – 3⁹ – 3³

3⁴² – 3⁹

42 – 9 = 33 двойки, но одну занимаем, т.к. дальше идет вычитание, остается 32

3⁹ – 3³

9 – 3 = 6

32 + 6 = 38

Ответ 38

№ 17

Какое количество страниц (в сотнях тысяч) будет найдено по запросу Физика & Квант?

Н| Ф |К = Н + Ф + К – Н&Ф –Н&К – Ф&К + Н&Ф&К

90 = 34+ 46+34 – 12 – 0 – x + 0

Н&К = 0, значит Н&Ф&К = 0

90 = 102 – x

X = 12

Ответ 12

№ 18 (будет видеоразбор)

Для какого наименьшего целого неотрицательного числа А выражение

(x + 2y < A) \/ (y > x) \/ (x > 20)

тождественно истинно, т.е. принимает значение 1 при любых целых неотрицательных x и y

Для такого типа задач есть простой вариант решения (используется, если А встречается только в одном неравенстве)

(x + 2y < A) \/ (y > x) \/ (x > 20)

Найдем, когда 2-я и 3-я скобки ложные

x <= 20, значит, берем для x крайнее значение 20

y <= x

y <= 20, значит, берем тоже 20

Если 2-я и 3-я скобки ложные, то должна быть истинной первая скобка, т.к. принимает значение 1 при любых целых неотрицательных x и y

и подставляем в 1-е неравенство x + 2y < A

20 + 2*20 < A

А > 60. Значит А = 61

Ответ 61

№ 19

В программе используется одномерный целочисленный массив A с индексами от 0 до 11. Значения элементов массива A[i] приведены в таблице.

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

s:= 0;

n:= 1;

for i:= 0 to 11 do

if A[i] > A[n] then

s:= s + A[i] + i

else

A[n]:= A[i];

А(i)		13 8 4
s	14		31			48	84	112	142	167	182	202

n:= 1 и не меняется

i:= 0 A[0] > A[1] 14> 13 (да) s:= s + A[i] + i S = 0 + A[0] +0 =14	i:= 1 A[1] > A[1] (нет) A[n]:= A[i];	i:= 2 A[2] > A[1] 15> 13 да S = 14 + A[2] +2 =14+15+2= 31	i:= 3 A[3] > A[1] 8> 13 нет A[1]:= A[3] = 8	i:= 4 A[4] > A[1] 4> 8 нет A[1]:= A[4] = 4
i:= 5 A[5] > A[1] 12> 4 да s:= s + A[5] + 5 S =31 + 12 + 5 = 48	i:= 6 A[6] > A[1] 30> 4 да s:= s + A[6] + 6 S = 48+30+6=84	i:= 7 A[7] > A[1] 2> 4 да S =84+21+7=112	i:= 8 да S =112+22+8=142	i:= 9 да S =142+16+9=167
i:= 10 да S =167+5+10=182	i:= 11 да S =182+9+11=202

Ответ 202

№ 20

Ниже на пяти языках программирования записан алгоритм. Получив на вход натуральное десятичное число x, этот алгоритм печатает два числа: L и M.

Укажите наибольшее число x, при вводе которого алгоритм выводит сначала 2, а потом 3.

var x, L, M: integer;

begin

readln(x);

L:= 0;

M:= 0;

while x > 0 do

begin

M:= M + 1;

if x mod 2 <> 0 then

L:= L + x mod 8;

x:= x div 8

end;

writeln(L);

writeln(M)

end.

Решение

x:= x div 8 – 8СС: 0……7

x mod 2 <> 0 условие нечетности

M:= M + 1 количество всех цифр M = 3

L:= L + x mod 8; сумма нечетных цифр 8-ричного числа L = 2, это будет 1 и 1

Больше нечетных цифр не м.б. Значит еще берем цифру 6

Наибольшее - 611

611₈ = 6*8² + 1*8 + 1 = 393

Ответ 393

№ 21

Определите наибольшее значение входной переменной k, при котором программа выдаёт тот же ответ, что и при входном значении k = 27.

var

k, i: longint;

function F(n: longint): longint;

begin

F:= n * n * n;

end;

function G(n: longint): longint;

begin

G:= 2 * n + 2;

end;

begin

readln(k);

i:= 1;

while F(i) < G(k) do

i:= i + 1;

writeln(i)

end.

Решение

Программа находит количество целых чисел, для которых выполнено условие F(i) < G(k)

k = 27, значит F(i) < G(27)

G(27) =2 * 27 + 2 = 56

while F(i) < 56 do

i:= i + 1;

Меняем условие на противоположное F(i) >= 56

F(i) = i³

i³ >= 56

i>= 3,…

i= 4

Т.е. при i= 4 цикл заканчивается, а при i= 3 цикл еще продолжается

F(3) < G(27) F(3) < G(к) 3³ < G(к)

F(4) >= G(27) F(4) >= G(к) 4³ >= G(к)

G(к):= 2 * к + 2

27 < 2k+2 <=64

12,5 < k <=31

[13;31] это все значения k

наибольшее значение входной переменной k, значит 31

Ответ 31

№ 22

Исполнитель Вычислитель преобразует число на экране.

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

1. Прибавить 1 -1

2. Умножить на 2 :2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для Вычислителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 21 и при этом траектория вычислений содержит

число 10 и не содержит числа 18?

Решение

1 ® 10 ® 21 18

1	1	10	14
2	2	11	14
3	2	12	14
4	4	13	14
5	4	14	14
6	6	15	14
7	6	16	14
8	10	17	14
9	10	18	0
10	14	19	0
		20	14
		21	14

Ответ 14

№ 23

Сколько существует различных наборов значений логических переменных x1, x2, … x7, y1, y2, … y7, которые удовлетворяют всем перечисленным ниже условиям?

x1 → y1 = 1

(x2 → (x1 /\ y2)) /\ (y2 → y1) = 1

(x3 → (x2 /\ y3)) /\ (y3 → y2) = 1

…

(x7 → (x6 /\ y7)) /\ (y7 → y6) = 1

Решение

Разбираем систему

(x2 → (x1 /\ y2)) /\ (y2 → y1) = 1

(x3 → (x2 /\ y3)) /\ (y3 → y2) = 1

…

(x7 → (x6 /\ y7)) /\ (y7 → y6) = 1