Вход   →
Осталось
4 часа
Демонстрационный вариант

Часть 1

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

Скачать pdf
  1.    Сколько существует целых чисел x, для которых выполняется неравенство 2A16 < x < 618?
       В ответе укажите только количество чисел, сами числа писать не нужно.

    Ответ
  2.    Логическая функция F задаётся выражением \lnot x \lor y \lor (\lnot z \land w).

      На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F ложна.

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

     

    Переменная 1 Переменная  2 Переменная 3 Переменная 4 Функция
    ??? ??? ??? ??? F
    1 0 0 0 1
    1 1 0 0 1
    1 1 1 0 1

     

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

    Ответ
  3.    На рисунке справа схема дорог Н-ского района изображена в виде графа; в таблице слева содержатся сведения о протяжённости каждой из этих дорог (в километрах).
     

    Схема дорог Н-ского района изображена в виде графа

     

       Так как таб­ли­цу и схему ри­со­ва­ли не­за­ви­си­мо друг от друга, то ну­ме­ра­ция населённых пунк­тов в таб­ли­це никак не свя­за­на с бук­вен­ны­ми обо­зна­че­ни­я­ми на графе. Определите, ка­ко­ва длина до­ро­ги из пунк­та А в пункт Г. В от­ве­те за­пи­ши­те целое число — так, как оно ука­за­но в таблице.

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

     

    Таблица 1
    ID Фа­ми­лия_И. О. Пол Год рождения
    15 Петрова Н. А. Ж 1944
    22 Иваненко И. М. М 1940
    23 Иваненко М. И. М 1968
    24 Иваненко М. М. М 1993
    32 Будай А. И. Ж 1960
    33 Будай В. С. Ж 1987
    35 Будай С. С. М 1965
    42 Коладзе А. С. Ж 1941
    43 Коладзе Л. А. М 1955
    44 Родэ О. С. М 1990
    46 Родэ М. О. М 2010
    52 Ауэрман А. М. Ж 1995
    73 Антонова М. А. Ж 1967
    ... ... ... ...

     

    Таблица 2
    ID_Ро­ди­те­ля ID_Ре­бен­ка
    22 23
    42 23
    23 24
    73 24
    22 32
    42 32
    32 33
    35 33
    15 35
    32 44
    35 44
    23 52
    73 52
    ... ...

     

    Ответ
  5.    По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

     

    Буква Кодовое слово   Буква Кодовое слово
    А 00   Л 1101
    Б     Р 1010
    Е 010   С 1110
    И 011   Т 1011
    К 1111   У 100

     

       Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
       Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

    Ответ
  6. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
    1) Строится двоичная запись числа N.
    2) К этой записи дописываются справа ещё два разряда по следующему правилу:
       а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
       б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
       Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
       Укажите минимальное число R, которое превышает число 83 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

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

      A B C D E
    1 1 10 100 1000 10000
    2 2 20 200 2000 20000
    3 3 =C$2 + D$3 300 3000 30000
    4   40 400 4000 40000

     

    Примечание: знак $ обо­зна­ча­ет аб­со­лют­ную адресацию.

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

     

    Бейсик Python
    DIM N, S AS INTEGER
    N = 0
    S = 260
    WHILE S > 0
        S = S - 15
        N = N + 2
    WEND
    PRINT N
    n = 0
    s = 260
    while s > 0:
        s = s - 15
        n = n + 2
    print(n)
    Паскаль Алгоритмический язык
    var n, s: integer;
    begin
        n := 0;
        s := 260;
        while s > 0 do
        begin
            s := s - 15;
            n := n + 2;
        end;
        writeln(n);
    end.
    алг
    нач
        цел n, s
        n := 0
        s := 260
        нц пока s > 0
            s := s - 15
            n := n + 2
        кц
        вывод n
    кон
    Си++
    #include <iostream> 
    using namespace std;
    int main() {
        int n, s;
        n = 0, s = 260;
        while (s > 0) {
            s = s - 15;
            n = n + 2;
        }
        count << n << endl;
        return 0;
    }
    Ответ
  9.    Автоматическая фотокамера производит растровые изображения размером 640×480 пикселей. При этом объём файла с изображением не может превышать 320 Кбайт, упаковка данных не производится. Какое максимальное количество цветов можно использовать в палитре?

    Ответ
  10.    Все 4-буквенные слова, составленные из букв Д, Е, К, О, Р, записаны в алфавитном порядке и пронумерованы, начиная с 1. Ниже приведено начало списка.
    1. ДДДД
    2. ДДДЕ
    3. ДДДК
    4. ДДДО
    5. ДДДР
    6. ДДЕД
          …
    Под каким номером в списке идёт первое слово, которое начинается с буквы K?

    Ответ
  11.    Ниже на пяти языках программирования записан рекурсивный алгоритм F.

     

    Бейсик Python
    DECLARE SUB F(n)
    SUB F(n)
        IF n > 0 THEN
            PRINT n
            F(n - 3)
            F(n \ 3)
        END IF
    END SUB
    def F(n):
        if n > 0:
            print(n)
            F(n - 3)
            F(n // 3)
    Паскаль Алгоритмический язык
    procedure F(n: integer);
    begin
        if n > 0 then begin
            writeln(n);
            F(n - 3);
            F(n div 3)
        end
    end;
    алг F(цел n)
    нач
        если n > 0 то
            вывод n, нс
            F(n - 3)
            F(div(n, 3))
        все
    кон
    Си++
    void F(int n) {
        if (n > 0) {
            std: :cout << n
            F(n - 3);
            F(n / 3);
        }
    }
    Ответ
  12.    В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес, — в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого разряда — нули. 

    Адрес сети получается в результате применения поразрядной конъюнкции к заданным IP-адресу узла и маске.
       Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.
       Для узла с IP-адресом 57.179.208.27 адрес сети равен 57.179.192.0. Каково наибольшее возможное количество единиц в разрядах маски?

    Ответ
  13.   При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов. В качестве символов используют прописные буквы латинского алфавита, т. е. 26 различных символов. В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Определите объём памяти (в байтах), необходимый для хранения данных о 50 пользователях. В ответе запишите только целое число — количество байт.

    Ответ
  14.  Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x,y) в точку с координатами (x + ay + b). Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).
    Цикл
        ПОВТОРИ число РАЗ
        последовательность команд
        КОНЕЦ ПОВТОРИ
    означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).
     
    Чертёжнику был дан для исполнения следующий алгоритм (число повторений и величины смещения в первой из повторяемых команд неизвестны):
    НАЧАЛО
    сместиться на (4, 6)
        ПОВТОРИ …РАЗ
          сместиться на (…, …)
          сместиться на (4, -6)
        КОНЕЦ ПОВТОРИ
    сместиться на (-28, -22)
    КОНЕЦ

     

       В результате выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ … РАЗ»?

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

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

     

     

    Ответ
  16.    Значение арифметического выражения: 4910 + 730 – 49 — записали в системе счисления с основанием 7. Сколько цифр «6» содержится в этой записи?

     

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

     

    Запрос Найдено стра­ниц
    (в сотнях тысяч)
    Бабочка 22
    Гусеница 40
    Трактор 24
    Трактор | Бабочка | Гусеница 66
    Трактор & Гусеница 12
    Трактор & Бабочка 0

     

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

    Ответ
  18.    Для какого наибольшего целого числа А формула ((x ≤ 9) →(x ⋅ x ≤ A)) ⋀ ((y ⋅ y ≤ A) → (y ≤ 9)) тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?

    Ответ
  19.    В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны 3, 0, 4, 6, 5, 1, 8, 2, 9, 7 соответственно, т. е. A[0] = 3, A[1] = 0 и т. д. Определите значение переменной c после выполнения следующего фрагмента этой программы (записанного ниже на разных языках программирования)

     

    Бейсик Python
    c = 0
    FOR i = 1 TO 9
        IF A(i-1) > A(i) THEN
           c = c + 1
           t = A(i)
           A(i) = A(i-1)
           A(i-1) = t
        END IF
    NEXT i
    c = 0
    for i in range(1,10):
        if A[i-1] > A[i]:
           c = c + 1
           t = A[i]
           A[i] = A[i-1]
           A[i-1] = t
    Паскаль Алгоритмический язык
    c := 0;
    for i := 1 to 9 do
        if A[i-1] > A[i] then
        begin
            c := c + 1;
            t := A[i];
            A[i] := A[i-1];
             A[i-1] := t;
        end;
    c := 0
    нц для i от 1 до 9
         если A[i-1] > A[i] то
           c := c + 1
           t := A[i]
           A[i] := A[i-1]
           A[i-1] := t
         все
    кц
    Си++
    c = 0;
    for (int i = 1; i < 10; i++)
         if (A[i-1] > A[i]){
            c++;
            t = A[i];
            A[i] = A[i-1];
            A[i-1] = t;
        }
    Ответ
  20.   Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наименьшее число x, при вводе которого алгоритм печатает сначала 5, а потом 7.

    Бейсик Python

    DIM X, L, M AS INTEGER

    INPUT X

    L = 0

    M = 0

    WHILE X > 0

        M = M + 1

         IF X MOD 2 <> 0 THEN

          L = L + 1

         END IF

    X = X \ 2

    WEND

    PRINT L

    PRINT M

    x = int(input())

    L = 0

    M = 0

    while x > 0:

         M = M + 1

         if x % 2 != 0:

          L = L + 1

         x = x // 2

    print(L)

    print(M)

     

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

    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 + 1;

              x := x div 2;

        end;

        writeln(L)

        writeln(M)

    end.

    алг

    нач

         цел x, L, M

         ввод x

         L := 0

         M := 0

        нц пока x > 0

            M := M + 1

             если mod(x,2) <> 0

                то

                 L := L + 1

            все

            x := div(x,2)

         кц

         вывод L, нс, M

    кон

    С++

    #include <iostream>

    using namespace std;

    int main(){

         int x, L, M;

         cin >> x;

         L = 0;

         M = 0;

         while (x > 0) {

              M = M + 1;

              if(x % 2 != 0) 

                 L = L + 1;

              x = x / 2; }

            cout << L << endl << M << endl;

            return 0;}

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

     

    Бейсик Python
    DIM A, B, T, M, R AS LONG
    A = -20: B = 20
    M = A: R = F(A)
    FOR T = A TO B
        IF F(T) <= R THEN
             M = T
             R = F(T)
        END IF
    NEXT t
    PRINT M+R
     
    FUNCTION F (x)
         F = 2*(x*x-1)*(x*x-1)+27
    END FUNCTION
    def f(x):
         return 2*(x*x-1)*(x*x-1)+27
    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+R)
    Паскаль Алгоритмический язык
    var a, b, t, M, R :longint;
    function F(x: longint) : longint;
        begin
             F:= 2*(x*x-1)*(x*x-1)+27;
        end;
    begin
         a:=-20; b:=20;
         M:=a; R:=F(a);
         for t:= a to b do begin
             if (F(t) <= R) then begin
                 M:=t;
                 R:=F(t)
          end
        end;
         write(M+R)
    end.
    алг
    нач
        цел a, b, t, M, R
        a:=-20; b:=20
        M:=a; R:=F(a)
        нц для t от a до b
             если F(t) <= R то
                то
                     M:=t; R:=F(t)
            все
        кц
        вывод M+R
    кон
    алг цел F(цел x)
    нач
        знач :=2*(x*x-1)*(x*x-1)+27
    кон
    С++

    #include <iostream>
    using namespace std;


    long F(long x) {
         return 2*(x*x-1)*(x*x-1)+27;
    }
    int main() {
         long a = -20, b = 20, M = a, R = F(a);
         for (int t = a; t <= b; ++t) {
             if (F(t)<= R) {
                M = t; R = F(t);
            }
        }
         cout << M + R;
        return 0;}

    Ответ
  22.    Исполнитель М17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
       1. Прибавить 1
       2. Прибавить 2
       3. Умножить на 3

      Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 3. Программа для исполнителя М17 – это последовательность команд. Сколько существует таких программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений программы содержит числа 8 и 10? Траектория должна содержать оба указанных числа.
      Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26.

    Ответ
  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, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

    Ответ

Часть 2

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

  1.     На обработку поступает натуральное число, не превышающее 109. Нужно написать программу, которая выводит на экран максимальную цифру числа, кратную 5. Если в числе нет цифр, кратных 5, требуется на экран вывести «NO». Программист написал программу неправильно. Ниже эта программа для Вашего удобства приведена на пяти языках программирования. Напоминание: 0 делится на любое натуральное число.

     

    Бейсик Python
    DIM N, DIGIT, MAXDIGIT AS LONG
    INPUT N
    MAXDIGIT = N MOD 10
    WHILE N > 0
        DIGIT = N MOD 10
        IF DIGIT MOD 5 = 0 THEN
            IF DIGIT > MAXDIGIT THEN
                MAXDIGIT = DIGIT
            END IF
        END IF
        N = N \ 10
    WEND
    IF MAXDIGIT = 0 THEN
        PRINT "NO"
    ELSE
        PRINT MAXDIGIT
    END IF
    N = int(input())
    maxDigit = N % 10
    while N > 0:
        digit = N % 10
        if digit % 5 == 0:
            if digit > maxDigit:
                maxDigit = digit
        N = N // 10
    if maxDigit == 0:
        print("NO")
    else:
        print(maxDigit))
    Паскаль Алгоритмический язык
    var N,digit,maxDigit: longint;
    begin
        readln(N);
        maxDigit := N mod 10;
        while N > 0 do
        begin
            digit := N mod 10;
            if digit mod 5 = 0 then
                if digit > maxDigit then
                    maxDigit := digit;
                N := N div 10;
        end;
        if maxDigit = 0 then
            writeln('NO')
        else
            writeln(maxDigit)
    end.
    алг
    нач
        цел N, digit, maxDigit
        ввод N
        maxDigit := mod(N,10)
        нц пока N > 0
            digit := mod(N,10)
            если mod(digit, 5) = 0 то
                если digit > maxDigit то
                    maxDigit := digit
                все
            все
            N := div(N,10)
        кц
        если maxDigit = 0 то
            вывод "NO"
        иначе
            вывод maxDigit
        все
    кон
    С++
    #include <iostream>
    using namespace std;
    int main() {
            long N, digit, maxDigit;
            cin >> N;
            maxDigit = N % 10;
            while (N > 0) {
                digit = N % 10;
                if (digit % 5 == 0)
                    if (digit > maxDigit)
                        maxDigit = digit;
                N = N / 10;}
            if (maxDigit == 0)
                cout << "NO" << endl;
            else
                cout << maxDigit << endl;
            return 0;}

     

     

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

    Ответ
  2.     Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит количество элементов массива, больших 100 и при этом кратных 5, а затем заменяет каждый такой элемент на число, равное найденному количеству. Гарантируется, что хотя бы один такой элемент в массиве есть. В качестве результата необходимо вывести измененный массив, каждый элемент массива выводится с новой строчки.
      Например, для массива из шести элементов: 4 115 7 195 25 106 программа должна вывести числа 4 2 7 2 25 106
     
     Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.

    Бейсик

    Python

    CONST N AS INTEGER = 30

    DIM A (1 TO N) AS LONG

    DIM I AS LONG,

        J AS LONG,

        K AS LONG

     

    FOR I = 1 TO N

        INPUT A(I)

    NEXT I

    ...

    END

    # допускается также

    # использовать две

    # целочисленные переменные j и k

    a = [ ]

    n = 30

    for i in range(0, n):

        a.append(int(input()))

    ...

    Паскаль

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

    const

    N = 30;

    var

    a: array [1..N] of longint;

    i, j, k: longint;

    begin

        for i := 1 to N do

            readln(a[i]);

        ...

    end.

    алг

    нач

        цел N = 30

        цел таб a[1:N]

        цел i, j, k

        нц для i от 1 до N

            ввод a[i]

        кц

        ...

     

    кон

    С++

     

    #include <iostream>

    using namespace std;

    const int N = 30;

    int main() {

    long a[N];

    long i, j, k;

        for (i = 0; i<N; i++)

        cin >> a[i];

        ...

        return 0;

    }

     

     

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

    Ответ
  3. Два игрока, Петя и Ваня играют в следующую игру. На столе в кучке лежат фишки. На лицевой стороне каждой фишки написано двузначное натуральное число, обе цифры которого находятся в диапазоне от 1 до 4. Никакие две фишки не повторяются. Игра состоит в том, что игроки поочередно берут из кучки по одной фишке и выкладывают в цепочку на стол лицевой стороной вверх таким образом, что каждая новая фишка ставится правее предыдущей и ближайшие цифры соседних фишек совпадают. Верхняя часть всех выложенных фишек направлена в одну сторону, то есть переворачивать фишки нельзя. Например, из фишки, на которой написано 23, нельзя сделать фишку, на которой написано 32. Первый ход делает Петя, выкладывая на стол любую фишку из кучки. Игра заканчивается, когда в кучке нет ни одной фишки, которую можно добавить в цепочку. Тот, кто добавил в цепочку последнюю фишку, выигрывает, а его противник проигрывает.

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

     

    Пример партии.

    Пусть на столе в кучке лежат фишки: 11, 12, 13, 21, 22, 23.

    Пусть первый ход Пети 12.

    Ваня может поставить 21, 22 или 23. Предположим, он ставит 21. Получим цепочку 12-21.

    Петя может поставить 11 или 13. Предположим, он ставит 11. Получим цепочку 12-21-11.

    Ваня может поставить только фишку со значением 13. Получим цепочку 12-21-11-13.

    Перед Петей в кучке остались только фишки 22 и 23, то есть нет фишек, которые он мог бы добавить в цепочку. Таким образом, партия закончена, Ваня выиграл.

     

    Выполните следующие три задания при исходном наборе фишек в кучке

    {12, 14, 21, 22, 24, 41, 42, 44}.

     

    Задание 1.

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

    б) Пусть Петя первым ходом пошел 42. У кого из игроков есть выигрышная стратегия в этой ситуации? Укажите первый ход, который должен сделать выигрывающий игрок, играющий по этой стратегии. Приведите пример одной из партий, возможных при реализации выигрывающим игроком этой стратегии.

    Задание 2. Пусть Петя первым ходом пошел 44. У кого из игроков есть выигрышная стратегия, позволяющая в этой ситуации выиграть своим четвертым ходом? Постройте в виде рисунка или таблицы дерево всех партий, возможных при реализации выигрывающим игроком этой стратегии. На рёбрах дерева указывайте ход, в узлах — цепочку фишек, получившуюся после этого хода.

    Задание 3. Укажите хотя бы один способ убрать 2 фишки из исходного набора так, чтобы всегда выигрывал не тот игрок, который имеет выигрышную стратегию в задании 2. Приведите пример партии для набора из 6 оставшихся фишек.

    Ответ
  4. В фи­зи­че­ской ла­бо­ра­то­рии про­во­дит­ся дол­го­вре­мен­ный экс­пе­ри­мент по изу­че­нию гра­ви­та­ци­он­но­го поля Земли. По ка­на­лу связи каж­дую ми­ну­ту в ла­бо­ра­то­рию пе­ре­даётся по­ло­жи­тель­ное целое число – те­ку­щее по­ка­за­ние при­бо­ра «Сигма 2015». Ко­ли­че­ство пе­ре­да­ва­е­мых чисел в серии из­вест­но и не пре­вы­ша­ет 10 000. Все числа не пре­вы­ша­ют 1000. Вре­ме­нем, в те­че­ние ко­то­ро­го про­ис­хо­дит пе­ре­да­ча, можно пре­не­бречь.
    Не­об­хо­ди­мо вы­чис­лить «бета-зна­че­ние» серии по­ка­за­ний при­бо­ра – ми­ни­маль­ное чётное про­из­ве­де­ние двух по­ка­за­ний, между мо­мен­та­ми пе­ре­да­чи ко­то­рых про­шло не менее 6 минут. Если по­лу­чить такое про­из­ве­де­ние не удаётся, ответ счи­та­ет­ся рав­ным –1.

     Вам пред­ла­га­ет­ся два за­да­ния, свя­зан­ных с этой за­да­чей: за­да­ние А и за­да­ние Б. Вы мо­же­те ре­шать оба за­да­ния или одно из них по сво­е­му вы­бо­ру. Ито­го­вая оцен­ка вы­став­ля­ет­ся как мак­си­маль­ная из оце­нок за за­да­ния А и Б. Если ре­ше­ние од­но­го из за­да­ний не пред­став­ле­но, то счи­та­ет­ся, что оцен­ка за это за­да­ние – 0 бал­лов. За­да­ние Б яв­ля­ет­ся усложнённым ва­ри­ан­том за­да­ния А, оно со­дер­жит до­пол­ни­тель­ные тре­бо­ва­ния к про­грам­ме.

     А. На­пи­ши­те на любом языке про­грам­ми­ро­ва­ния про­грам­му для ре­ше­ния по­став­лен­ной за­да­чи, в ко­то­рой вход­ные дан­ные будут за­по­ми­нать­ся в мас­си­ве, после чего будут про­ве­ре­ны все воз­мож­ные пары эле­мен­тов. Перед про­грам­мой ука­жи­те вер­сию языка про­грам­ми­ро­ва­ния.
         ОБЯ­ЗА­ТЕЛЬ­НО ука­жи­те, что про­грам­ма яв­ля­ет­ся ре­ше­ни­ем ЗА­ДА­НИЯ А.
    Мак­си­маль­ная оцен­ка за вы­пол­не­ние за­да­ния А – 2 балла.

    Б. На­пи­ши­те про­грам­му для ре­ше­ния по­став­лен­ной за­да­чи, ко­то­рая будет эф­фек­тив­на как по вре­ме­ни, так и по па­мя­ти (или хотя бы по одной из этих ха­рак­те­ри­стик).
    Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если время ра­бо­ты
    про­грам­мы про­пор­ци­о­наль­но ко­ли­че­ству по­лу­чен­ных по­ка­за­ний при­бо­ра N, т.е. при уве­ли­че­нии N в k раз время ра­бо­ты про­грам­мы долж­но уве­ли­чи­вать­ся не более чем в k раз.
    Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по па­мя­ти, если раз­мер па­мя­ти, ис­поль­зо­ван­ной в про­грам­ме для хра­не­ния дан­ных, не за­ви­сит от числа N и не пре­вы­ша­ет 1 ки­ло­бай­та.
    Перед про­грам­мой ука­жи­те вер­сию языка про­грам­ми­ро­ва­ния и крат­ко опи­ши­те ис­поль­зо­ван­ный ал­го­ритм.
         ОБЯ­ЗА­ТЕЛЬ­НО ука­жи­те, что про­грам­ма яв­ля­ет­ся ре­ше­ни­ем ЗА­ДА­НИЯ Б.
    Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни и по па­мя­ти, – 4 балла.
    Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни, но не­эф­фек­тив­ную по па­мя­ти, – 3 балла. НА­ПО­МИ­НА­ЕМ! Не за­будь­те ука­зать, к ка­ко­му за­да­нию от­но­сит­ся каж­дая из пред­став­лен­ных Вами про­грамм.
    Вход­ные дан­ные пред­став­ле­ны сле­ду­ю­щим об­ра­зом. В пер­вой стро­ке задаётся число N – общее ко­ли­че­ство по­ка­за­ний при­бо­ра. Га­ран­ти­ру­ет­ся, что N > 6. В каж­дой из сле­ду­ю­щих N строк задаётся одно по­ло­жи­тель­ное целое число – оче­ред­ное по­ка­за­ние при­бо­ра.

    При­мер вход­ных дан­ных:
    11
    12
    45
    5
    3
    17
    23
    21
    20
    19
    18
    17

    Про­грам­ма долж­на вы­ве­сти одно число - опи­сан­ное в усло­вии про­из­ве­де­ние либо –1, если по­лу­чить такое про­из­ве­де­ние не удаётся.
    При­мер вы­ход­ных дан­ных для при­ведённого выше при­ме­ра вход­ных дан­ных:
    54

    Ответ
Завершить вариант
Демонстрационный вариант
240 минут
на вариант из 27 вопросов
Вернуться назад
Осталось
4 часа 0 минут

Часть 1

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

Часть 2

24
25
26
27

Еще нет аккаунта?

Пользователям Бингоскул доступна бесплатная подготовка к ЕГЭ по всем видам ФИПИ, просмотр решений и отслеживание статистики
Регистрация

Уже зарегистрированы?

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

Вход в систему

Регистрация

Регистрируясь, я подтверждаю своё согласие с условиями пользовательского соглашения

Активация аккаунта

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