№№ заданий Пояснения Ответы Ключ Добавить инструкцию Критерии
Источник Раздел кодификатора Ф ИПИ Справка
PDF-версия PDF-версия (вертикальная) PDF-версия (крупный шрифт) PDF-версия (с большим полем) Версия для копирования в MS Word
Вариант № 4595647

1.

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

2.

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

 

Перем. 1Перем. 2Перем. 3Перем. 4Функция
????????????F
10000
11000
11100

 

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

 

Пример. Если бы функция была задана выражением ¬xy, зависящим от двух переменных: x и y, и был приведён фрагмент её таблицы истинности, содержащий все наборы аргументов, при которых функция F истинна.

 

Перем. 1Перем. 2Функция
??????F
001
101
111

 

Тогда первому столбцу соответствовала бы переменная y, а второму столбцу — переменная x. В ответе следовало бы написать: yx.

3.

Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

ABCDEF
A34720
B35
C44
D754511
E54
F20114

 

Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам).

4.

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

 

Пояснение: дядей считается брат отца или матери.

 

Таблица 1.
IDФамилия_И. О.Пол
14Леоненко Н. А.Ж
23Геладзе И. П.М
24Геладзе П. И.М
25Геладзе П. П.М
34Леоненко А. И.Ж
35Леоненко В. С.Ж
33Леоненко С. С.М
42Вильямс О. С.Ж
44Гнейс А. С.Ж
45Гнейс В. А.М
47Вильямс П. О.М
57Паоло А. П.Ж
64Моор П. А.Ж
.........
Таблица 2
ID_РодителяID_Ребёнка
2324
4424
2425
6425
2334
4434
3435
3335
1433
3442
3342
2457
6457
......

5.

Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Закодируйте таким образом последовательность символов ББГА и запишите полученное двоичное число в шестнадцатеричной системе счисления.

6.

Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.

 

1. Складываются отдельно первая и вторая цифры, вторая и третья цифры, а также третья и четвёртая цифры.

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

 

Пример. Исходное число: 9575. Суммы: 9 + 5 = 14; 5 + 7 = 12; 7 + 5 = 12. Наибольшие суммы: 14, 12. Результат: 1214.

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

7.

В электронной таблице значение формулы =CУMM(D2:D4) равно 16. Чему равно значение ячейки D1, если значение формулы =CP3HAЧ(D1:D4) равно 5? Пустых ячеек в таблице нет.

8.

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

 

 

БейсикPython

DIM S, N AS INTEGER

S = 0

N = 0

WHILE S <= 65

S = S + 5

N = N + 3

WEND

PRINT N

s = 0

n = 0

while s <= 65:

    s = s + 5

    n = n + 3

print(n)

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

var s, n: integer;

begin

    s := 0;

    n := 0;

    while s <= 65 do

    begin

        s := s + 5;

        n := n + 3

    end;

    writeln(n)

end.

алг

нач

цел n, s

s := 0

n := 0

нц пока s <= 65

    s := s + 5

    n := n + 3

кц

вывод n

кон

Си++

#include <iostream>

using namespace std;

int main()

{

    int s = 0, n = 0;

    while (s <= 65)

    {

        s = s + 5;

        n = n + 3;

    }

    cout << n << endl;

    return 0;

}

 

9.

Саша скачивает из сети файл размером 60 Мбайт. Скорость передачи первой половины данных составляет 256 Кбит в секунду, а второй — в два раза меньше. Сколько минут будет скачиваться файл?

10.

Все 4-буквенные слова, составленные из букв М, У, Х, А записаны в алфавитном порядке и пронумерованы.

Вот начало списка:

 

1. АААА

2. АААМ

3. АААУ

4. АААХ

5. ААМА

 

Напишите номер слова ХУХХ

11.

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

F(1) = 1

F(n) = F(n–1) * (n + 2), при n > 1

Чему равно значение функции F(5)? В ответе запишите только натуральное число.

12.

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

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

IP –адрес узла: 224.37.249.32

Маска: 255.255.224.0

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

 

ABCDEFGH
255249240224373280

 

Пример.

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

 

ABCDEFGH
1281682558127017192

 

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

13.

В одной небольшой стране Индивидуальные Номера Налогоплательщиков представляют собой целые числа от 1 до 4000, На некотором предприятии в этой стране работают 300 человек. Главный бухгалтер этого предприятия переписала ИНН всех сотрудников последовательно без разделителей в один файл, при этом использовалось представление целых чисел с одинаковым минимально возможным количеством бит. Оцените объем получившегося файла. (Ответ дайте в байтах.)

14.

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

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

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

заменить (111, 27)

преобразует строку 05111150 в строку 0527150.

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

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

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

 

Цикл

ПОКА условие

    последовательность команд

КОНЕЦ ПОКА

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

 

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 85 единиц?

 

НАЧАЛО

    ПОКА нашлось (11111)

        заменить (111, 2)

        заменить (222, 1)

    КОНЕЦ ПОКА

КОНЕЦ

15.

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

 

16.

Значение выражения 1254 + 258 − 30 записали в системе счисления с основанием 5.

Сколько цифр 4 содержится в этой записи?

17.

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

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

 

ЗапросНайдено страниц
(в тысячах)
Сириус & Вега260
Вега & (Сириус | Арктур) 467
Сириус & Вега & Арктур131

 

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

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

18.

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Так, например, 12&6 = 11002&01102 = 01002 = 4.

Для какого наибольшего целого числа А формула

 

х&А → (x&10 = 0 → х&3)

 

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

19.

Дан фрагмент программы, обрабатывающей двухмерный массив A[1..5,1..4]:

 

 

БейсикPython

k = 4

FOR m = 1 TO 4

    k = k + 1

    FOR n = 1 TO 5

        k = m - k

        A(n,m) = n*n+m*m-2*k

    NEXT n

NEXT m

 

k = 4

for m in range(1, 5):

   k += 1

   for n in range(1, 6):

      k=m-k

      A[n][m]=n*n+m*m-2*k

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

k:=4;

for m:=1 to 4 do begin

   k:=k+1;

   for n:=1 to 5 do begin

       k:=m-k;

       A[n,m]:=n*n+m*m-2*k;

    end;

end;

k:=4

нц для m от 1 до 4

    k:=k+1

    нц для n от 1 до 5

        k:=m-k

        A[n,m]:=n*n+m*m-2*k

    кц

кц

 

Си++

k = 4;

for (m = 1; m <= 4; m++) {

    k = k + 1;

    for (n = 1; n <= 5; n++) {

        k=m-k;

        A[n][m]=n*n+m*m-2*k;

    }

}

 

 

Чему будет равно значение A[3,1]?

20.

Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает число M. Известно, что x > 100. Укажите наименьшее такое (т. е. большее 100) число x, при вводе которого алгоритм печатает 15.

 

БейсикPython

DIM X, L, M AS INTEGER

INPUT X

L = X - 30

M = X + 30

WHILE L <> M

   IF L > M THEN

    L = L – M

  ELSE

    M = M – L

END IF

WEND

PRINT M

x = int(input())

L = x-30

M = x+30

while L != M:

  if L > M:

    L = L - M

  else:

    M = M - L

print(M)

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

var x, L, M: integer;

begin

  readln(x);

  L := x-30;

  M := x+30;

  while L <> M do

    if L > M then

      L := L - M

    else

      M := M – L;

  writeln(M);

end.

алг

нач

  цел x, L, M

  ввод x

  L := x-30

  M := x+30

  нц пока L <> M

    если L > M

      то

      L := L – M

      иначе

      M := M – L

    все

  кц

  вывод M

кон

Си++

#include <iostream>

using namespace std;

int main()

{

  int x, L, M;

  cin >> x;

  L = x-30;

  M = x+30;

  while (L != M){

    if(L > M)

      L = L - M;

    else

      M = M - L;

  }

  cout « M « endl;

  return 0;

}

 

21.

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

 

Бэйсик Паскаль

DIM A, B, T, M, R AS INTEGER

A = -20: B = 20

T = A: M = A: R = F(A)

FOR T = A TO B

    IF F(T) < R THEN

        M = T

        R = F(T)

    ENDIF

NEXT T

PRINT M

FUNCTION F(x)

    F = 2*(x-9)*(x-9);

END FUNCTION

var a,b,t,M,R :integer;

    Function F(x: integer):integer;

        begin

            F := 2*(x-9)*(x-9);

        end;

BEGIN

    a := -20; b := 20;

    M := a; R := F(a);

    for t := a to b do

        if (F(t)< R) then begin

            M := t;

            R := F(t);

        end;

    write(M);

END.

Си++ Алгоритмический

#include <iostream>

using namespace std;

int F(int x)

{

    return 2*(x-9)*(x-9);

}

int main()

{

    int a, b, t, M, R;

    a = -20; b = 20;

    M = a; R = F(a);

    for (t=a; t<=b; t++){

        if (F(t) < R ) {

            M = t; R = F(t);

        }

    }

    cout « M « endl;

}

алг

нач

цел a, b, t, R, M

a := -20; b := 20

M := a; R := F(a)

нц для t от a до b

если F(t)< R

то

M := t; R := F(t)

все

кц

вывод M

кон

алг цел F(цел x)

нач

знач := 2*(x-9)*(x-9)

кон

Python

def f(x):

    return 2*(x-9)*(x-9)

a = -20

b = 20

M = a

R = f(a)

for t in range(a, b+1):

    if (f(t) < R):

        M = t

        R = f(t);

print(M)

 

22.

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

 

БэйсикПаскаль

x = 2.5E+02

x = x + 0.5E+02

y = -x

c = -2*y - x

x:= 2.5E+02;

x:= x + 0.5E+02;

y:= -x;

c:= -2*y - x;

Си++Алгоритмический язык

x= 2.5E+02;

x= x + 0.5E+02;

y= -x;

c= -2*y - x;

x:= 2.5E+02

x:= x + 0.5E+02

y:= -x

c:= -2*y - x

Python

x= 2.5E+02

x= x + 0.5E+02

y= -x

c= -2*y - x

 

23.

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

(¬x1 ∨ y1) → (¬x2 ∧ y2) = 1

(¬x2 ∨ y2) → (¬x3 ∧y3) = 1

                        …

(¬x6 ∨ y6) → (¬x7 ∧ y7) = 1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, ...x7, y1, y2, ...y7, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

24.

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

 

БейсикПаскаль

DIM N AS LONG

INPUT N

sum = 1

WHILE N > 1

N = N \ 10

sum = sum + 1

WEND

PRINT sum

END

var N: longint;

sum: integer;

begin

readln(N);

sum := 1;

while N > 1 do

begin

N := N div 10;

sum := sum + 1;

end;

writeln(sum);

end.

Си++Алгоритмический

#include <iostream>

using namespace std;

int main()

{

long int N;

int sum;

cin >> N;

sum = 1;

while (N > 1)

{

N = N /10;

sum = sum + 1;

}

cout « sum « endl;

}

алг

нач

цел N, sum

ввод N

sum := 1

нц пока N > 1

N := div(N, 10)

sum := sum + 1

кц

вывод sum

кон

Python

n = int(input())

sum = 1

while n > 1:

    n //= 10

    sum += 1

print(sum)

 

 

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

 

1. Напишите, что выведет эта программа при вводе числа 938.

2. Укажите одно число для которого эта программа будет работать верно.

3. Найдите все ошибки в этой программе (их может быть одна или несколько). Укажите все строки (одну или более), содержащие ошибки, и для каждой такой строки приведите правильный вариант. Обратите внимание, что требуется найти ошибки в имеющейся программе, а не написать свою, возможно, использующую другой алгоритм решения. Исправление ошибки должно затрагивать только строку, в которой находится ошибка.

25.

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

26.

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

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

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

 

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

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

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

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

Для указанных значений S опишите выигрышную стратегию Пети.

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

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

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

27.

Соревнования по игре «Тетрис-онлайн» проводятся по следующим правилам:

 

1. Каждый участник регистрируется на сайте игры под определённым игровым именем. Имена участников не повторяются.

2. Чемпионат проводится в течение определённого времени. В любой момент этого времени любой зарегистрированный участник может зайти на сайт чемпионата и начать зачётную игру. По окончании игры её результат (количество набранных очков) фиксируется и заносится в протокол.

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

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

5. Более высокое место в соревнованиях занимает участник, показавший лучший результат.

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

 

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

 

Спонсор чемпионата предоставил призы различной ценности для награждения К лучших игроков (К<=20). Если участников окажется меньше К, призами награждаются все. Вам необходимо написать эффективную, в том числе по памяти, программу, которая по данным протокола определяет К лучших игроков и занятые ими места. 

 

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

 

Описание входных данных

Первая строка содержит числа К — количество имеющихся призов и N — общее количество строк протокола.

Каждая из следующих N строк содержит записанные через пробел результат участника (целое положительное число, не превышающее 100 миллионов) и игровое имя (имя не может содержать пробелов). Строки исходных данных соответствуют строкам протокола и расположены в том же порядке, что и в протоколе.

 

Описание выходных данных

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

 

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

6 15

69485 Jack

95715 qwerty

95715 Alex

83647 M

197128 qwerty

95715 Jack

93289 Alex

95715 Alex

95715 M

32768 BilboBaggins

99824 TetrisMaster

45482 BilboBaggins

62123 BilboBaggins

77623 M

56791 Champion

 

Пример выходных данных для приведённого выше примера входных данных:

1. qwerty (197128)

2. TetrisMaster (99824)

3. Alex (95715)

4. Jack (95715)

5. M (95715)

6. BilboBaggins (62123)