Вы отправили работу на проверку эксперту. Укажите номер телефона на него придет СМС
Скачать .pdf

Вариант 1

Часть 1.

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

1
1

Сколько единиц в двоичной записи шестнадцатеричного числа 10FA16?

2
2

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












ABCDEF
A2510
B212
C132
D31
E5223
F1013

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

3
3

Каждое из логических выражений F и G содержит 5 переменных. В таблицах истинности выражений F и G есть ровно 5 одинаковых строк, причём ровно в 4 из них в столбце значений стоит 1.


Сколько строк таблицы истинности для выражения F v G содержит 1 в столбце значений?

4
4

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



















Таблица 1
IDФамилия_И.О.Пол
17Гречко Н.АЖ
24Гречко И.М.М
25Гречко М.И.М
26Гречко М.М.М
34Лагидзе А.И.Ж
35Лагидзе В.С.Ж
37Лагидзе С.С.М
44Гольдони А.С.Ж
45Гольдони Л.А.М
46Гланц О.С.М
48Гланц М.О.М
54Гаранян А.М.Ж
75Михейко М.А.Ж
.........



















Таблица 2
ID_родителяID_ребенка
2425
4425
2526
7526
2434
4434
3435
3735
1737
3446
3746
2554
7554
...
5
5

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


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


2. К этой записи дописываются справа ещё два разряда по следующему правилу:


А) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 10000 преобразуется в запись 100001;


Б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2.


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


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

6
6

Дан фрагмент электронной таблицы








ABCDE
1404100707
2303606
3= B$3 * $D22300505
4101400404

Из ячейки АЗ в ячейку С2 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились. Каким стало числовое значение формулы в ячейке С2?


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

7
7

Какой минимальный объём памяти (в Кбайт) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером 512x512 пикселов при условии, что в изображении могут использоваться 256 различных цветов? В ответе запишите только целое число, единицу измерения писать не нужно.


8
8

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


Бейсик


DIM S, N AS INTEGER
    S = 0
    N = 0
WHILE
    S <= 65    
    S = S + 5    
    N = N + 3
WEND
PRINT N

Python


s = 0
n = 0
while s <= 65:
    s = s + 5
    n = n + 3
print(n)

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


алг
нач
    цел n, s
    n : = 0
    s : = 0
    нц пока s <= 65
        s : = s + 5
        n : = n + 3
кц
вывод 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.

Си


#include<stdio.h>    
int main()    
{ int s = 0, n = 0;    
    while (s <= 65)
    {
        s = s + 5;
        n = n + 3;
    }    
    printf("%d\n", n);    
    return 0;    
}
9
9

Для кодирования некоторой последовательности, состоящей из букв А, Б, В и Г, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В используются такие кодовые слова: А — 000, Б — 1, В — 011. Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

10
10

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

11
11

Ниже на 5 языках программирования записана рекурсивная функция (процедура) F.


Бейсик


SUB F (n)
    PRINT n,
    IF n > 2 THEN
        F(n - 3)
        F(n - 2)
        F(n - 1)
    END IF
END SUB

Python


def F(n):
    print (n, end='')
    if n > 2:
        F(n - 3)
        F(n - 2)
        F(n - 1)

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


алг F(цел n)
нач
    вывод n
    если n > 2 то
        F(n - 3)
        F(n - 2)
        F(n - 1)
    все
кон

Паскаль


procedure F(n: integer);
begin
    write(n);
    if n > 2 then
    begin
        F(n - 3);
        F(n - 2);
        F(n - 1)
    end
end;

Си


void F(int n) { 
    printf("%d", n) ;
    if (n > 2) {
        F(n - 3);
        F(n - 2);
        F(n - 1);
    }
}

Что выведет программа при вызове F(4)? В ответе запишите последовательность выведенных цифр слитно (без пробелов).

12
12

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


Например, если IP-адрес узла равен 237.33.255.123, а маска равна 255.255.240.0, то адрес сети равен 237.33.240.0.


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

13
13

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов и содержащий только символы из 26-символьного набора латинского алфавита. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей.


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

14
14

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


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


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


Например, выполнение команды заменить (555, 63)


преобразует строку 12555550 в строку 1263550.


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


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


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


Цикл


ПОКА условие


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


КОНЕЦ ПОКА


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


В конструкции ЕСЛИ условие ТО команда 1 ИНАЧЕ команда2 КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).


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


НАЧАЛО


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


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


ТО заменить (888, 9)


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


КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ

15
15

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


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


Вариант 1

16
16

Значение арифметического выражения: 92016 + З2015 — 9 — записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?

17
17

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







ЗапросНайдено страниц (в тыс.)
Сосна & Ель270
Сосна & (Ель | Кедр)530
Сосна & Кедр360

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


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

18
18

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел тип. Так, например, 12&6 = 11002&01102 = 01002 = 4.


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


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


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

19
19

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


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


Бейсик


с = 0
FOR i = 0 ТО 8
    IF А(i) <= А(9) THEN
        с = с + 1
        t = А (i)
        А (i) = А ( 9)
        А (9) = t
    ENDIF
NEXT i

Python


c = 0
for i in range(0,9):
    if A[i] <= A[9]:
        c = c + 1
        t = A [ i ]
        A [ i ] = A [ 9 ]
        A [ 9 ] = t

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


с : = 0
нц для i от 0 до 8
    если А[i] <= А[9] то
        с : = с + 1
        t : = А [ I ]
        А[i] := А[9]
        А[9] := t
    все
кц

Паскаль


c : = 0;
for i := 0 to 8 do
    if A[i] <= A[9] then
    begin
        c : = c + 1;
        t : = A [ i ] ;
        A[i] := A[9];
        A[9] := t;
    end;

Си


с = 0 ;
for (i = 0; i < 9;i++)
    if (A[i] <= A[9])
    {
        c+ +;
        t = A [ i ] ;
        A [ i ] = A [ 9 ] ;
        A[9] = t;
    }
20
20

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


Бейсик


DIM X, L, М AS INTEGER
INPUT X
L = X
M = 5
IF L MOD 2=0 THEN
    M = 24
ENDIF
WHILE L <> M
IF L > M THEN
    L = L - M
ELSE
    M = M - L
ENDIF
WEND
PRINT M

Python


х = int(input())
L = х
M = 5
if L % 2 == 0:
    M = 24
while L != M:
    if L > M:
        L = L - M
    else:
        M = M - L
print(M)

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


алг
нач
    цел х, L, М
    ввод X
    L : = х
    М : = 5
    если mod(L,2)=0
        то
            М := 24
    все
    нц пока L о М
        если L > М
            то
                L := L - М
            иначе
                М := М - L
        все
    кц
    вывод М
кон

Паскаль


var x, L, M: integer;
begin
    readln(x);
    L : = x;
    M := 5;
    if L mod 2=0 then
        M := 24;
    while L <> M do
        if L > M then
            L := L - M
        else
            M := M - L;
    writeln(M);
end.

Си


#iclude<stdio.h>
void main()
{
    int x, L, M;
    scanf ("%d", &x);
    L = x;
    M = 5;
    if (L % 2 == 0)
        M = 24;
    while (L !=M) {
        If (L > M)
            L = L - M;
        else
            M = M - L;
    }
    printf("%d", M);
}
21
21

Напишите в ответе наибольшее значение входной переменной k, при котором программа выдаёт тот же ответ, что и при входном значении k = 49. Для Вашего удобства программа приведена на пяти языках программирования.


Бейсик


DIM К, I AS LONG
INPUT К
I = 1
WHILE F(I) < G(К)
    I = I + 1
WEND
PRINT I

FUNCTION F(N)
    F = N * N * N
END FUNCTION

FUNCTION G(N)
    G = 2*N + 1
END FUNCTION

Python


def f (n) :
    return n*n*n

def g (n) :
    return 2*n+1

k = int (input())
i = 1
while f(i) < g(k):
    i+=1
print (i)

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


алг
нач
    цел i, k
    ввод k
    i : = 1
    нц пока f(i) < g (k)
        i : = i + 1
    кц
    вывод i
KOH

алг цел f(цел n)
нач
    знач := n * n * n
кон

алг цел g(цел n)
нач
    знач := 2*n + 1
кон

Паскаль


var    
    k, i : longint;

function f(n: longint):    longint;
begin    
    f : = n * n * n;    
end;    

function g(n: longint):    longint;
begin    
    g : = 2 * n + 1;    
end;    
    
begin    
    readln(k);
    i := 1;    
    while f(i) < g(k) do    
        i : = i +1;    
    writeln(i)
end.    

Си


#include <stdio.h>
long f (long n) {
    return n * n * n;
}
long g (long n) {
    return 2*n + 1;
}
int main()
{
    long k, i;
    scant("%ld", &k);
    i = 1;
    while(f(i)<g(k))"
        i + + ;
    printf("%ld", i);
    return 0;
{
22
22

Исполнитель Удвоитель преобразует число на экране.


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


Прибавить 1


Умножить на 2


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


Сколько существует программ, для которых при исходном числе 3 результатом является число 25 и при этом траектория вычислений содержит число 11 и не содержит числа 20?


Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 112 при исходном числе 5 траектория будет состоять из чисел 6, 7, 14.

23
23

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


(x1 ∨ y1) → (x2 ∧ y2) = 0


(x2 ∨ y2) → (x2 ∧ y2) = 0


...


(x5 ∨ y5) → (x6 ∧ y6) = 0


В ответе не нужно перечислять все различные наборы значений переменных x1, х2, ... х6, у1, у2 ... у6, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

 

Часть 2.

Запишите сначала номер задания (24, 27 и т. д.), затем полное решение. Ответы записывайте чётко и разборчиво.

24

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


Бейсик



DIM N, DIGIT, SUM AS LONG
INPUT N
SUM = N MOD 10
WHILE N > 0
    DIGIT = N MOD 10
    IF DIGIT MOD 3=0 THEN
        SUM = DIGIT
    END IF
    N = N \ 10
WEND
IF SUM > 0 THEN
    PRINT SUM
ELSE
    PRINT "NO"
END IF

Python



N = int (input())
sum = N % 10
while N > 0:
    digit = N % 10
    if digit % 3 == 0:
        sum = digit
    N = N // 10
if sum > 0:
    print(sum)
else:
    print("NO")

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



алг
нач
    цел N, digit, sum
    ввод N
    sum := mod(N,10)
    нц пока N > 0
        digit := mod(N,10)
        если mod(digit, 3) = 0 to
            sum : = digit
        все
        N := div(N,10)
    кц
    если sum > 0 to
        вывод sum
    иначе
        вывод "NO"
    все
кон

Паскаль


var N, digit, sum: longint;
begin
    readln(N);
    sum := N mod 10;
    while N > 0 do
    begin
        digit := N mod 10;
        if digit mod 3=0 then
            sum := digit;
        N := N div 10;
    end;
    if sum > 0 then
        writeln(sum)
    else
        writeln('NO')
end.

Си


#include <stdio.h> int main()
{
    int N, digit, sum;
    scanf ("%d", &N);
    sum = N % 10;
    while (N > 0)
    {
        digit = N % 10;
        if (digit % 3 == 0)
            sum = digit;
        N = N / 10;
    }
    if (sum >0)
        printf("%d",sum);
    else
        printf("NO");
    return 0;
}

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


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


2. Приведите пример такого трёхзначного числа, при вводе которого программа выдаёт верный ответ.


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


1) выпишите строку, в которой сделана ошибка;


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


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


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

Показать ответ

Содержание верного ответа


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


1. Программа выведет число 8.


2. Программа выдаёт правильный ответ, например, для числа 357.


Программа работает неправильно из-за неверной начальной инициализации суммы и неверного увеличения суммы. Соответственно, программа будет работать верно, если в числе ровно одна кратная 3 цифра или таких цифр вообще нет и при этом число заканчивается на 0.


В программе есть две ошибки.


Первая ошибка: неверная инициализация суммы (переменная sum).


Строка с ошибкой:


sum := N mod 10;

Верное исправление:


sum := 0;

Вторая ошибка: неверное увеличение суммы.


Строка с ошибкой:


sum := digit;

Верное исправление:


sum := sum + digit;
25

Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от -10 000 до 10 000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести количество пар элементов массива, в которых хотя бы одно число делится на 13. В данной задаче под парой подразумевается два подряд идущих элемента массива. Например, для массива из пяти элементов: 13; 7; 26; -1; 9 — ответ: 3.


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


Бейсик


CONST N AS INTEGER = 30
DIM A (1 TO N) AS INTEGER
DIM I A INTEGER,
    J AS INTEGER,
K AS INTEGER

FOR I = 1 TO N
    INUT A(I)
NEXT I
...
END

ython


# допускается также
# использовать две
# целочисленные переменные j и k
a = []
n = 30
for i in range(0, n):
    a.aend(int(inut()))
...

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


алг
нач
    цел N = 30
    целтаб f[1:N]
    цел i, j, k
    нц для i от 1 до N
            ввод a[i]
        кц
        ...
кон

Паскаль


const
N = 30;
var
    a:array [1..N] of integer;
    i, j, k: integer;
begin
    for i := 1 to N do
        readln(a[i]);
    ...
end.

Си


#include <stdio.h>
#define N 30
int main() {
    int a[N];
    int i, j, k;
    for (i = 0; i < N; i++)
        scanf("%d", &a[i]);
    ...
    return 0;
}

Естественный язык


Объявляем массив А из 30 элементов.
Объявляем целочисленные переменные I, J, K.
В цикле от 1 до 30 вводим элемента массива А с 1-го по 30-й.
...

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

Показать ответ

Содержание верного ответа


На языке Паскаль


 к := 0;
for i := 1 to N - 1 do
    if (a[i] mod 13 = 0) or (a[i+l] mod 13 = 0) then
        inc(k);
writeln (k);

На алгоритмическом языке


 нц для i от 1 до N - 1
    если mod(a[i],13) = 0 или mod(а[i+1],13) = 0
    то
        k := k + 1
    все
кц
вывод к

На языке Бейсик


 k = 0
FOR I = 1 ТО N - 1
    IF (А(I) MOD 13 = 0) OR (А(I + 1) MOD 13 = 0) THEN
        К = К + 1
    END IF
NEXT I PRINT К

На языке Си


 k = 0;
for (i = 0; i < N - 1; i++)
    if (a[i] % 13 == 0 a[i+1] % 13 == 0)
        k++;
printf("%d", k);

На языке Python


 k = 0
for i in range (0, n - 1) :
    if (a [i] % 13 == 0 or a[i + 1] % 13 == 0);
        k += 1
print(k)

На естественном языке


Записываем в переменную К начальное значение, равное 0. В цикле от первого элемента 
до предпоследнего находим остаток от деления текущего и следующего элемента массива на 13.
Если первый или второй из полученных остатков равен 0, увеличиваем переменную К на единицу.
После завершения цикла выводим значение переменной К
26

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


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


Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (21, 30) и (41, 20) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.


Задание 1


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


Задание 2


Для каждой из начальных позиций (10, 34), (5, 37), (6, 36) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.


Задание 3


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

Показать ответ

Содержание верного ответа


Задание 1.


В начальных позициях (10, 35), (6, 37) выигрышная стратегия есть у Вани. При начальной позиции (10, 35) после первого хода Пети может получиться одна из следующих четырёх позиций: (11, 35), (20, 35), (10, 70), (10, 36). Каждая из этих позиций содержит менее 81 камня. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 81 камня, удвоив количество камней во второй куче. Для позиции (6, 37) после первого хода Пети может получиться одна из следующих четырёх позиций: (7, 37), (12, 37), (6, 38), (6, 74). Каждая из этих позиций содержит менее 81 камня. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 81 камня, удвоив количество камней во второй куче.

Таким образом, Ваня при любом ходе Пети выигрывает своим первым ходом.


Задание 2.


В начальных позициях (10, 34), (5, 37) и (6, 36) выигрышная стратегия есть у Пети. При начальной позиции (10, 34) он должен первым ходом получить позицию (10, 35), из начальных позиций (5, 37) и (6, 36) Петя после первого хода должен получить позицию (6, 37). Позиции (10, 35) и (6, 37) рассмотрены при разборе задания 1. В этих позициях выигрышная стратегия есть у игрока, который будет ходить вторым (теперь это Петя). Эта стратегия описана при разборе задания 1. Таким образом, Петя при любой игре Вани выигрывает своим вторым ходом.


Задание 3.


В начальной позиции (5, 36) выигрышная стратегия есть у Вани. После первого хода Пети может возникнуть одна из четырёх позиций: (6, 36), (10, 36), (5, 37) и (5, 72). В позициях (10, 36) и (5, 72) Ваня может выиграть одним ходом, удвоив количество камней во второй куче. Позиции (6, 36) и (5, 37) были рассмотрены при разборе задания 2. В этих позициях у игрока, который должен сделать ход (теперь это Ваня), есть выигрышная стратегия. Эта стратегия описана при разборе задания 2. Таким образом, в зависимости от игры Пети Ваня выигрывает на первом или на втором ходу.


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


Вариант 1


На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы).


Вариант 1

27

Датчик передаёт каждую секунду по каналу связи неотрицательное целое число, не превосходящее 1000 — текущий результат измерений. Временем, в течение которого происходит передача, можно пренебречь.


Необходимо найти в заданной серии показаний датчика минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 15 секунд. Если получить такое произведение не удаётся, ответ считается равным — 1. Общее количество показаний датчика в серии не превышает 10 000.


Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору.


Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание — 0 баллов.


Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.


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


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


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


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


ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.


Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.


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


Входные данные представлены следующим образом. В первой строке задаётся число N — общее количество показаний датчика. Гарантируется, что N > 15. В каждой из следующих N строк задаётся одно неотрицательное целое число — очередное показание прибора.


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


<p>17</p>
<p>5</p>
<p>4</p>
<p>3</p>
<p>2</p>
<p>1</p>
<p>6</p>
<p>7</p>
<p>8</p>
<p>9</p>
<p>10</p>
<p>110</p>
<p>120</p>
<p>130</p>
<p>140</p>
<p>150</p>
<p>160</p>
<p>50</p>

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


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

Показать ответ

Содержание верного ответа


Задание А


Ниже приводится пример переборного решения на Паскале, не эффективного ни по памяти, ни по времени, но являющимся правильным ответом на задание А.


Программа 1.


const s = 15; {требуемое расстояние между показаниями} 
var
    N: integer;
    a: array[1..10000] of integer; {все показания датчика}
    mp: integer; {минимальное значение произведения}
    i, j: integer;
begin
    readln(N);
    {Ввод значений датчика}
    for i := 1 to N do
        readln(a [i]);
    mp := 1000 * 1000 + 1;
    for i := 1 to N - s do begin
        for j := i + s to N do begin
            if (a[i] * a[j] mod 2 = 0) and (a[i] * a[j] < mp)
                then mp := a[i] * a[j]
        end;
    end;
    if mp = 1000 * 1000 + 1 then mp := -1;
writeln(mp)
end.

Задание Б


Чтобы произведение было чётным, хотя бы один сомножитель должен быть чётным, поэтому при поиске подходящих произведений чётные показания прибора можно рассматривать в паре с любыми другими, а нечётные — только с чётными.


Для каждого показания с номером k, начиная с k = 16, рассмотрим все допустимые по условиям задачи пары, в которых данное показание получено вторым. Минимальное произведение из всех этих пар будет получено, если первым в паре будет взято минимальное подходящее показание среди всех, полученных от начала приёма и до показания с номером k — 15. Если очередное показание чётное, минимальное среди предыдущих может быть любым, если нечётное — только чётным.


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


Программа 2.


const s = 15; {требуемое расстояние между показаниями}
        аmах = 1001;{больше максимально возможного показания}
var.
    N: integer;
    a: array[l..s] of integer; {хранение s показаний датчика}
    а_: integer; {ввод очередного показания}
    mа: integer; {минимальное число без s последних}
    mе: integer; {минимальное чётное число без s последних}
    mp: integer; {минимальное значение произведения}
    р: integer;
    i, j : integer;
begin
    readln(N);
    {Ввод первых s чисел}
    for i := 1 to s do readln(a[i]);
    {Ввод остальных значений, поиск минимального произведения}
    mа : = аmах; те : = аmах;
    mр := аmах * аmах;
    for i := s + 1 to N do begin
        readln(a );
        if a[l] < mа then mа := a[1];
        if (a [1] mod 2 = 0) and (a[1] < me) then me := a[1];
        if a_ mod 2 = 0 then p := a * mа
        else if me < amax then p := a_ * me
        else p := amax * amax;
        if (p < mp) then mp := p;
        {сдвигаем элементы вспомогательного массива влево}
        for j := 1 to s = 1 do
            a[j] := a[j + 1];
        a[s] := a_
    end;    
        if mp = amax * amax then mp := -1;
    writeln(mp)
end.
0 из 0
Ваш ответ Правильный ответ Первичный балл

Здесь появится результат тестовой части.

Нажмите на кнопку «Завершить работу», чтобы увидеть правильные ответы.