Вход   →
Осталось
4 часа
Вариант 2

Часть 1

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

Скачать pdf
  1. Вычислите значение выражения FA16 + A1C16.

    В ответе запишите вычисленное значение в десятичной системе счисления.

    Ответ
  2.    Логическая функция F задаётся выражением (B \lor C) (\lnot C \lor A). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных A, B, C.

     

    ? ? ? F
    0 0 0 0
    0 0 1 0
    0 1 0 1
    0 1 1 1
    1 0 0 0
    1 0 1 1
    1 1 0 0
    1 1 1 1

     

       В ответе напишите буквы A, B, C в том порядке, в котором идут соответствующие им столбцы.

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

      П1 П2 П3 П4 П5 П6
    П1   *     *  
    П2 *   * * *  
    П3   *   *   *
    П4   * *   * *
    П5 * *   * * *
    П6     * * *  

    Информатика задание 3

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

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

    Таблица 1

    ID

    Фа­ми­лия_И. О.

    Пол

    Год рождения

    23

    Смирнова А.М.

    ж

    1940

    45

    Соколов С.П.

    м

    1970

    56

    Смирнов К.Н.

    м

    1967

    89

    Соколова Л.Д.

    ж

    1990

    11

    Кузнецов М.Н.

    м

    1940

    34

    Соколова Р.Р.

    ж

    1935

    67

    Смирнова А.Н.

    ж

    1970

    43

    Соколов С.А.

    м

    1960

    28

    Смирнов П.В.

    м

    1965

    85

    Кузнецова К.П.

    ж

    1972

    36

    Кузнецов Т.Р.

    м

    1993

    90

    Смирнов П.Д.

    м

    1987

    37

    Соколов А.В.

    м

    1930

    ...

    ...

    ...

    ...

    Таблица 2

    ID_Ро­ди­те­ля

    ID_Ре­бен­ка

    23

    28

    23

    56

    23

    67

    56

    90

    37

    43

    37

    45

    34

    43

    34

    45

    43

    89

    67

    89

    45

    36

    11

    85

    85

    36

    ...

    ...

     

    Ответ
  5.   По каналу связи передаются сообщения, содержащие только пять букв:  Р, У, Ч, К, А; для передачи используется двоичный код, допускающий однозначное декодирование.  Для букв Р, У, Ч, К используются такие кодовые слова: Р: 101,  У: 11,  Ч: 01, К: 001.  Укажите кратчайшее кодовое слово для буквы А, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением 

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

    число по следующим правилам.

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

    Пример. Исходное число: 478. Суммы: 4 + 7 = 11; 7 + 8 = 15. Результат: 1511.

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

    Ответ
  7.    Дан фрагмент электронной таблицы. Из одной из ячеек диапазона A1:A4 в одну из ячеек диапазона B1:B4 была скопирована формула. При этом адреса в формуле автоматически изменились и числовое значение в ячейке, куда производилось копирование, стало равным 46. В какую ячейку была скопирована формула? В ответе укажите только одно число – номер строки, в которой расположена ячейка.

      А В С D Е
    1 =D$1+$D1         4 4 55
    2 =D$2+$D2   44 3 110
    3 =D$3+$D3   444 2 220
    4 =D$4+$D4   4444 1 440

     

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

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

    Паскаль С++
     var n, s: integer;
     begin 
      s:=2; 
      n:=7; 
     while s< 1002 do
     begin
     s:=s*5; 
     n:=n*3;  
     end;
     write(n)
     end.

    #include <iostream>

    using namespace std;

     

    int main() {

     int n, s;  

       s=2;

      n=7;

     while (s< 1002 ) {

      s=s*5; 

      n=n*3; 

     }  

    cout << n << endl;

    return 0;

    }

     

    Ответ
  9.    Для хранения произвольного растрового изображения размером 256×1024 пикселей отведено 64 Кбайт памяти, при этом для каждого пикселя хранится двоичное число – код цвета этого пикселя. Для каждого пикселя для хранения кода выделено одинаковое количество бит. Сжатие данных не производится. Какое максимальное количество цветов можно использовать в изображении? 

    Ответ
  10.    Все 5-буквенные слова, составленные из букв К, А, Р, Т, записаны в алфавитном порядке и пронумерованы, начиная с 1. Ниже приведено начало списка.
    1. ККККK
    2. KKKKА
    3. KKKKТ
    4. KKKKР
    5. КККАК

    Под каким номером в списке идёт слово РРРТК?   

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

    Паскаль  Си
     procedure F(n: integer);
     begin
       writeln('#');
       if n <= 6 then begin
            F(n*2); 
            F(n*2);
            F(n+2);
      end
       writeln('#'); 
    end;
     
     void F(int n)                
     {
      std::cout <<"#";
      if (n <= 6) {
        F(n*2);
        F(n*2);
        F(n+2);
      }
      std::cout <<"#";
       }
     

     Сколько символов «решётка» будет напечатано на экране при выполнении вызова F(3)?

    Ответ
  12.    Для узла с IP-адресом 220.222.30.100 адрес сети равен 220.222.30.0 . Чему равен третий слева байт маски? Ответ запишите в виде десятичного числа.

    Ответ
  13.   При регистрации на сайте каждому пользователю выдаётся идентификатор, состоящий из 13 символов. В качестве символов используют 10 строчных букв: A, B, C, D, F, G, H, T, U, R  и десятичные цифры. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит. Определите объём памяти (в байтах), необходимый для хранения данных о 23 пользователях. В ответе запишите только целое число — количество байт.

    Ответ
  14. Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 37 идущих подряд цифр 8? В ответе запишите полученную строку.

    НА ЧАЛО

    ПОКА нашлось (333) ИЛИ нашлось (888)

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

    ТО заменить (333, 8) 

    ИНАЧЕ заменить (888, 3)

    КОНЕЦ ЕСЛИ 

    КОНЕЦ ПОКА

    КОНЕЦ

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

    Сколько существует различных путей из города А в город Н?

    Ответ
  16.    Сколько единиц в двоичной записи числа 4448 – 4123 + 2654 – 501?

    Ответ
  17.    В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:

     

    Запрос Количество страниц (тыс.)
    Собака & КОШКА& Хомяк 113
    Собака & КОШКА 225
    Собака & (КОШКА| Хомяк) 645

     

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

    Ответ
  18.   На числовой прямой даны два отрезка: Р = [30, 50] и Q = [21, 41].

      Укажите наибольшую возможную длину промежутка А, для которого формула ((x ∈ P) → (x ∈ Q)) ∧ (x ∈ A) тождественно ложна, то есть принимает значение 0 при любом значении переменной х.

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

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

     

    Паскаль  С++ 
    j := 5;
    while A[j] < A[j-1] do
        begin
            t := A[j];
            A[j] := A[j-1];
            A[j-1] := t;
            j := j - 1;
        end;
    j = 5;
    while (A[j] < A[j-1])
        {
            t = A[j];
            A[j] = A[j-1];
            A[j-1] = t;
            j -= 1;
        }
    Бейсик Pyhon
    j = 5
    WHILE A(j) < A(j-1)
        t = A(j)
        A(j) = A(j-1)
        A(j-1) = t
        j = j - 1
    WEND
    j = 5
    while A[j] < A[j-1]:
        A[j],A[j-1]=A[j-1],A[j]
        j -= 1
    Алгоритмический язык  
    j := 5
    нцпока A[j] < A[j-1]
        t := A[j]
        A[j] := A[j-1]
        A[j-1] := t
        j := j - 1
    кц
     
    Ответ
  20.   Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наименьшее число x, при вводе которого алгоритм печатает сначала 4, а потом 6.

    Бейсик Python

    DIM X, L, M AS INTEGER

    INPUT X

    L = 0

    M = 0

    WHILE X > 0

        M = M + 1

         IF X MOD 3 <> 0 THEN

          L = L + 1

         END IF

    X = X \ 3

    WEND

    PRINT L

    PRINT M

    x = int(input())

    L = 0

    M = 0

    while x > 0:

         M = M + 1

         if x % 3 != 0:

          L = L + 1

         x = x // 3

    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 3 <> 0 then

                L := L + 1;

              x := x div 3;

        end;

        writeln(L)

        writeln(M)

    end.

    алг

    нач

         цел x, L, M

         ввод x

         L := 0

         M := 0

        нц пока x > 0

            M := M + 1

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

                то

                 L := L + 1

            все

            x := div(x,3)

         кц

         вывод 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 % 3 != 0) 

                 L = L + 1;

              x = x / 3;

            }

            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
     
    FUNCTION F (x)
         F = -x*x - 2*x + 3
    END FUNCTION
    def f(x):
         return -x*x - 2*x + 3
    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)
    Паскаль Алгоритмический язык
    var a, b, t, M, R :longint;
    function F(x: longint) : longint;
        begin
             F:= -x*x - 2*x + 3;
        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)
    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
    кон
    алг цел F(цел x)
    нач
        знач :=-x*x - 2*x + 3
    кон
    С++

    #include <iostream>
    using namespace std;


    long F(long x) {
         return -x*x - 2*x + 3;
    }
    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;
        return 0;}

    Ответ
  22. Иван преобразует число, записанное на экране.

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

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

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

    Первая из них увеличивает число на экране на 1, вторая умножает его на 3.

    Программа  – это последовательность команд.

    Сколько существует таких программ, которые исходное число 7 преобразуют в число 23?

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

    (x1→ (x2∧ x3)) ∧ (y1→ y2) = 1
    (x2→ (x3∧ x4)) ∧ (y2→ y3) = 1
    ...
    (x5→ (x6∧ x7)) ∧ (y5→ y6) = 1

     

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

    Ответ

Часть 2

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

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

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

    DIM N AS LONG

    INPUT N

    min_digit = 9

    WHILE N >= 10

        digit = N MOD 10

        IF digit > min_digit THEN

             min_digit = digit

        END IF

        N = N \ 10

    WEND

    PRINT digit

    END

    var N: longint;

        digit, min_digit: integer;

    begin

        readln(N);

         min_digit := 9;

        while N >= 10 do

        begin

            digit := N mod 10;

            if digit > min_digit then

                 min_digit := digit;

            N := N div 10;

        end;

        writeln( digit);

    end.

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

    #include <iostream>

    using namespace std;

    void main()

    {

        long int N;

        int digit, min_digit;

    cin >>N;

         min_digit = 9;

        while (N >= 10)

        {

            digit = N % 10;

            if (digit > min_digit)

                 min_digit = digit;

            N = N /10;

        }

        cout << digit;

    }

    алг

    нач

        цел N, digit, min_digit

        ввод N

         min_digit := 9

        нц пока N >= 10

            digit := mod(N, 10)

            если digit > min_digit то

                 min_digit := digit

            все

            N := div(N, 10)

        кц

        вывод digit

    кон

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

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

    2. Най­ди­те все ошиб­ки в этой про­грам­ме (их может быть одна или не­сколь­ко). Для каж­дой ошиб­ки:

    1) вы­пи­ши­те стро­ку, в ко­то­рой сде­ла­на ошиб­ка;
    2) ука­жи­те, как ис­пра­вить ошиб­ку, — при­ве­ди­те пра­виль­ный ва­ри­ант стро­ки.

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

    Ответ
  2.     Дан мас­сив состоящий из 100 целых чисел. Напишите на одном из язы­ков про­грам­ми­ро­ва­ния ал­го­ритм, поз­во­ля­ю­щий найти и вы­ве­сти про­из­ве­де­ние эле­мен­тов мас­си­ва, ко­то­рые имеют нечётное зна­че­ние и де­лят­ся на 3. Га­ран­ти­ру­ет­ся, что в ис­ход­ном мас­си­ве есть хотя бы один эле­мент, зна­че­ние ко­то­ро­го нечётно и крат­но 3.

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

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

    N=100

    DIM A(N) AS LONG

    DIM I, J, P AS LONG

    FOR I = 1 TO N

    INPUT A(I)

    NEXT I

    END

    const

    N=100;

    var

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

    i, j, p: longint;

    begin

    for i := 1 to N do

    readln(a[i]);

    end.

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

    #include <iostream>

    using namespace std;

    const int N =  100;

    void main(void){

    long a[N];

    long i, j, p;

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

    cin >>a[i];

    }

    алг

    нач

    цел N=100

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

    цел i, j, p

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

    ввод a[i]

    кц

    ...

    кон

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

    Ответ
  3.   Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить в одну из куч (по сво­е­му вы­бо­ру) один ка­мень или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, пусть в одной куче 10 кам­ней, а в дру­гой 7 кам­ней; такую по­зи­цию в игре будем обо­зна­чать (10, 7). Тогда за один ход можно по­лу­чить любую из четырёх по­зи­ций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

      Будем го­во­рить, что игрок имеет вы­иг­рыш­ную стра­те­гию, если он может вы­иг­рать при любых ходах про­тив­ни­ка. Опи­сать стра­те­гию иг­ро­ка – зна­чит опи­сать, какой ход он дол­жен сде­лать в любой си­ту­а­ции, ко­то­рая ему может встре­тить­ся при раз­лич­ной игре про­тив­ни­ка. На­при­мер, при на­чаль­ных по­зи­ци­ях (6, 34), (7, 33), (9, 32) вы­иг­рыш­ная стра­те­гия есть у Пети. Чтобы вы­иг­рать, ему до­ста­точ­но удво­ить ко­ли­че­ство кам­ней во вто­рой куче.

      За­да­ние 1. Для каж­дой из на­чаль­ных по­зи­ций (6, 33), (8, 32) ука­жи­те, кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию. В каж­дом слу­чае опи­ши­те вы­иг­рыш­ную стра­те­гию; объ­яс­ни­те, по­че­му эта стра­те­гия ведёт к вы­иг­ры­шу, и ука­жи­те, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стра­те­гии.

      За­да­ние 2. Для каж­дой из на­чаль­ных по­зи­ций (6, 32), (7, 32), (8, 31) ука­жи­те, кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию. В каж­дом слу­чае опи­ши­те вы­иг­рыш­ную стра­те­гию; объ­яс­ни­те, по­че­му эта стра­те­гия ведёт к вы­иг­ры­шу, и ука­жи­те, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стра­те­гии.

      За­да­ние 3. Для на­чаль­ной по­зи­ции (7, 31) ука­жи­те, кто из иг­ро­ков имеет вы­иг­рыш­ную стра­те­гию. Опи­ши­те вы­иг­рыш­ную стра­те­гию; объ­яс­ни­те, по­че­му эта стра­те­гия ведёт к вы­иг­ры­шу, и ука­жи­те, какое наи­боль­шее ко­ли­че­ство ходов может по­тре­бо­вать­ся по­бе­ди­те­лю для вы­иг­ры­ша при этой стра­те­гии. По­строй­те де­ре­во всех пар­тий, воз­мож­ных при ука­зан­ной Вами вы­иг­рыш­ной стра­те­гии. Пред­ставь­те де­ре­во в виде ри­сун­ка или таб­ли­цы.

    Ответ
  4. Вам пред­ла­га­ет­ся два за­да­ния с по­хо­жи­ми усло­ви­я­ми: за­да­ние А и за­да­ние Б. Вы мо­же­те ре­шать оба за­да­ния или одно из них по сво­е­му вы­бо­ру. За­да­ние Б более слож­ное, его ре­ше­ние оце­ни­ва­ет­ся выше. Ито­го­вая оцен­ка вы­став­ля­ет­ся как мак­си­маль­ная из оце­нок за за­да­ния А и Б.  

    За­да­ние А. Име­ет­ся набор дан­ных, со­сто­я­щий из 6 пар по­ло­жи­тель­ных целых чисел. Не­об­хо­ди­мо вы­брать из каж­дой пары ровно одно число так, чтобы сумма всех вы­бран­ных чисел не де­ли­лась на 3 и при этом была мак­си­маль­но воз­мож­ной. Если по­лу­чить тре­бу­е­мую сумму не­воз­мож­но, в ка­че­стве от­ве­та нужно вы­дать 0.
    На­пи­ши­те про­грам­му для ре­ше­ния этой за­да­чи. В этом ва­ри­ан­те за­да­ния оце­ни­ва­ет­ся толь­ко пра­виль­ность про­грам­мы, время ра­бо­ты и раз­мер ис­поль­зо­ван­ной па­мя­ти не имеют зна­че­ния.
    Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му – 2 балла.  

    За­да­ние Б. Име­ет­ся набор дан­ных, со­сто­я­щий из пар по­ло­жи­тель­ных целых чисел. Не­об­хо­ди­мо вы­брать из каж­дой пары ровно одно число так, чтобы сумма всех вы­бран­ных чисел не де­ли­лась на 3 и при этом была мак­си­маль­но воз­мож­ной. Если по­лу­чить тре­бу­е­мую сумму не­воз­мож­но, в ка­че­стве от­ве­та нужно вы­дать 0.
    На­пи­ши­те про­грам­му для ре­ше­ния этой за­да­чи.
    По­ста­рай­тесь сде­лать про­грам­му эф­фек­тив­ной по вре­ме­ни и ис­поль­зу­е­мой па­мя­ти (или хотя бы по одной из этих ха­рак­те­ри­стик).
    Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если время ра­бо­ты про­грам­мы про­пор­ци­о­наль­но ко­ли­че­ству пар чисел N, т. е. при уве­ли­че­нии N в k раз время ра­бо­ты про­грам­мы долж­но уве­ли­чи­вать­ся не более чем в k раз.
    Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по па­мя­ти, если раз­мер па­мя­ти, ис­поль­зо­ван­ной в про­грам­ме для хра­не­ния дан­ных, не за­ви­сит от числа N и не пре­вы­ша­ет 1 ки­ло­бай­та.
    Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни и па­мя­ти, — 4 балла.
    Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни, но не­эф­фек­тив­ную по па­мя­ти, — 3 балла. 

    Как в ва­ри­ан­те А, так и в ва­ри­ан­те Б про­грам­ма долж­на на­пе­ча­тать одно число — мак­си­маль­но воз­мож­ную сумму, со­от­вет­ству­ю­щую усло­ви­ям за­да­чи (или 0, если такую сумму по­лу­чить нель­зя). 

    НА­ПО­МИ­НА­ЕМ! Не за­будь­те ука­зать, к ка­ко­му за­да­нию от­но­сит­ся каж­дая из пред­став­лен­ных Вами про­грамм. 

    Перед тек­стом про­грам­мы крат­ко опи­ши­те Ваш ал­го­ритм ре­ше­ния, ука­жи­те ис­поль­зо­ван­ный язык про­грам­ми­ро­ва­ния и его вер­сию (на­при­мер, Free Pascal 2.6.4). 

    Вход­ные дан­ные
    Для ва­ри­ан­та А на вход про­грам­ме подаётся шесть строк, каж­дая из ко­то­рых со­дер­жит два на­ту­раль­ных числа, не пре­вы­ша­ю­щих 10 000.
    При­мер вход­ных дан­ных для ва­ри­ан­та А:
    1 3
    5 12
    6 9
    5 4
    3 3
    1 1  

    Для ва­ри­ан­та Б на вход про­грам­ме в пер­вой стро­ке подаётся ко­ли­че­ство пар N (1 ≤ N ≤ 100 000). Каж­дая из сле­ду­ю­щих N строк со­дер­жит два на­ту­раль­ных числа, не пре­вы­ша­ю­щих 10 000.
    При­мер вход­ных дан­ных для ва­ри­ан­та Б:
    6
    1 3
    5 12
    6 9
    5 4
    3 3
    1 1
    При­мер вы­ход­ных дан­ных для при­ведённых выше при­ме­ров вход­ных дан­ных: 32 

    Ответ
Завершить вариант
Вариант 2
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

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

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

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

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

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

Регистрация

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

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

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