В начало страницы

Вариант «ЕГЭ — 2019. Досрочная волна. Вариант 1» (ДОСР-2019)

Список тем

1, Д1, 2, 3, 4, 5, 6, 7, Д7, 8, 11, 12, Д12, 13, 14, 15, 15, 16, Д17, Д19, Д21, 22, 23, Д23, Д24 C1, Д25 C2, Д26 C3, Д26 C3, Д27 C4

Задания

Задание 1 (тема 1, №18072)

Текст задания

На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.

 

П1П2П3П4П5П6
П17154
П2712
П35
П45109
П515121016
П64916

 

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

Задание Д1 (тема Д1, №18070)

Текст задания

Сколько существует натуральных чисел x, для которых верно неравенство 101111002 < x < BF16?

В ответе укажите количество чисел, сами числа писать не нужно.

Задание 2 (тема 2, №18071)

Текст задания

Логическая функция F задаётся выражением (x ∧ ¬y) ∨ (y ≡ z) ∨ ¬w.

Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.

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

 

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

 

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

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

 

Переменная 1Переменная 1Функция
??????F
010

 

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

Задание 3 (тема 3, №18073)

Текст задания

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

 

Таблица 1
IDФамилия И.О.ПолГод рождения
240Черных А. В.М1938
261Черных Д. И.М1997
295Черных Е. П.Ж1939
325Черных И. А.М1972
356Черных Н. Н.Ж1972
367Гунько А. Б.М1979
427Малых Е. А.М2001
517Краско М. А.Ж1967
625Соболь О. К.Ж1988
630Краско В. К.М1993
743Гунько Б. В.М1951
854Колосова А. Е.Ж1955
943Гунько А. Н.Ж1975
962Малых Н. Н.М1946

Таблица 2
ID РодителяID Ребенка
240325
295325
325261
356261
367427
240517
295517
517625
517630
743367
854367
943427
962356
962943

Задание 4 (тема 4, №18074)

Текст задания

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р. решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова 00, 01, 100, 110. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

 

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Задание 5 (тема 5, №18075)

Текст задания

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

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

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

    а) находится остаток от деления на 2 суммы двоичных разрядов N, полученный результат дописывается в конец двоичной последовательности N.

    б) пункт а повторяется для вновь полученной последовательности.

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

Задание 6 (тема 6, №18077)

Текст задания

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

 

 

БейсикPython

DIM K, S AS INTEGER

S = 230

K = 0

WHILE S > 0

    S = S – 15

    K = K + 2

WEND

PRINT K

s = 230

k = 0

while s > 0:

    s = s − 15

    k = k + 2

print(k)

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

var k, s: integer;

begin

    s:=230;

    k:=0;

    while s > 0 do begin

        s := s – 15;

        k := k + 2;

    end;

    write(k);

end.

алг

нач

    цел s, k

    s := 230

    k := 0

    нц пока s > 0

        s := s − 15

        k := k + 2

    кц

    вывод k

кон

Си++

#include <iostream>

using namespace std;

 

int main() {

    int s , k;

    s = 230;

    k = 0;

    while(s > 0){

        s = s − 15;

        k = k + 2;

    }

    cout << k << endl;

}

 

 

Задание 7 (тема 7, №18078)

Текст задания

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

Задание Д7 (тема Д7, №18076)

Текст задания

В ячейки электронной таблицы записаны числа, как показано на рисунке:

 

ABCD
11101001000
22202000
33=A$2+$D33003000
44404004000

 

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

 

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

Задание 8 (тема 8, №18079)

Текст задания

Вася составляет 6-буквенные слова из букв К, О, Т. Причем буква К используется в каждом слове ровно 1 раз. Остальные буквы могут быть использованы любое количество раз, в том числе совсем отсутствовать. Сколько слов может составить Вася? Словом называется любая буквенная комбинация, не обязательно осмысленное слово русского языка.

Задание 11 (тема 11, №18082)

Текст задания

Для регистрации на сайте некоторой страны пользователю необходимо придумать пароль длиной ровно 10 символов. В пароле можно использовать только прописные буквы английского алфавита, т.е. 26 символов. Информация о пользователе хранится с помощью минимально возможного целого количества байт. Каждый символ в пароле кодируется одинаковым и минимально возможным количеством бит. Для хранения дополнительной информации на одного пользователя отводится 15 байт. Определите объем памяти в байтах, необходимый для хранения информации о 50 пользователях.

Задание 12 (тема 12, №18083)

Текст задания

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).

 

Цикл

ПОВТОРИ число РАЗ

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

КОНЕЦ ПОВТОРИ

означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).

 

Чертёжнику был дан для исполнения следующий алгоритм (количество повторений и смещения в первой из повторяемых команд неизвестны):

 

НАЧАЛО

Сместиться на (2, 2)

ПОВТОРИ n РАЗ

Сместиться на (a, b)

Сместиться на (2, -3)

КОНЕЦ ПОВТОРИ

Сместиться на (-20, -14)

КОНЕЦ

 

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

Задание Д12 (тема Д12, №18081)

Текст задания

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

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

Узлы с IP-адресами 140.37.235.224 и 140.37.235.192 находятся в одной сети. Определите последний байт маски сети. Количество возможных единиц в маске этой сети должно быть наибольшим.

Задание 13 (тема 13, №18084)

Текст задания

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

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

Задание 14 (тема 14, №18085)

Текст задания

Значение выражения 416 + 234 − 8 записали в системе счисления с основанием 2. Сколько цифр 1 содержится в этой записи?

Задание 16 (тема 16, №18080)

Текст задания

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

 

БейсикPython

SUB F(N)

    PRINT N

    IF N >= 3 THEN

        F(n – 1)

        F(n – 2)

        F(n – 2)

    END IF

END SUB

 

def F(n):

    print(n)

    if n >= 3:

        F(n – 1)

        F(n – 2)

        F(n – 2)

 

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

procedure F(n: integer);

begin

    write(n);

    if n >= 3 then begin

        F(n – 1);

        F(n – 2);

        F(n – 2)

    end

end;

 

алг F(цел n)

нач

    вывод n

    если n >= 3 то

        F(n – 1)

        F(n – 2)

        F(n – 2)

    все

кон

 

С++

void F(int n)

{

    std::cout << n;

    if (n >= 3) {

        F(n – 1);

        F(n – 2);

        F(n – 2);

    }

}

 

 

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

Задание Д17 (тема Д17, №18086)

Текст задания

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

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

 

ЗапросНайдено страниц
(в тысячах)
Корабль30
Нос50
Колено45
Корабль | Нос | Колено85
Корабль & Нос13
Корабль & Колено0

 

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

 

Нос & Колено?

 

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

Задание Д19 (тема Д19, №18088)

Текст задания

Представленный ниже на пяти языках программирования фрагмент программы обрабатывает элементы одномерного целочисленного массива A с индексами от 0 до 11. Перед началом выполнения данного фрагмента эти элементы массива имели значения 20, 19, 33, 21, 42, 13, 12, 24, 4, 22, 6, 10 (т.е. A[0] = 20, A[1] = 19, …, A[11] = 10). Определите значение переменной s после выполнения фрагмента.

 

 

БейсикPython

N = 1

S = 1

FOR I = 1 TO 11

    IF A(I) < A(N) THEN

        S = S * I

        T = A(I)

        A(I) = A(N)

        A(N) = T

    END IF

NEXT I

 

n = 1

s = 1

for i in range(1, 12):

    if A[i] < A[n]:

        s = s * i

        t = A[i]

        A[i] = A[n]

        A[n] = t

 

 

 

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

n:= 1;

s:= 1;

for i:=1 to 11 do

    if A[i] < A[n] then begin

        s := s * i;

        t := A[i];

        A[i] := A[n];

        A[n] := t;

    end;

 

s := 1

n := 1

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

    если A[i] < A[n] то

        s := s * i

        t := A[i]

        A[i] := A[n]

        A[n] := t;

    все

кц

С++

n = 1;

s = 1;

for (i = 1; i < 12; i++) {

    if (A[i] < A[n]) {

        s = s * i;

        t = A[i];

        A[i] = A[n];

        A[n] = t;

    }

}

 

Задание Д21 (тема Д21, №18090)

Текст задания

Напишите в ответе число, равное количеству различных значений входной переменной k, при которых приведённая ниже программа выводит тот же ответ, что и при входном значении k = 35. Значение k = 35 также включается в подсчёт различных значений k.

 

 

БейсикPython

DIM K, I AS INTEGER

INPUT K

I = 1

WHILE F(I) < K

    I = I + 1

WEND

IF F(I)−K<=K−F(I−1) THEN

    PRINT I

ELSE

    PRINT I – 1

END IF

 

FUNCTION F(N)

    F = N*N*N

END FUNCTION

def f(n):

    return n*n*n

 

k = int(input())

i = 1

while f(i) < k:

    i = i + 1

if f(i)–k <= k–f(i−1):

    print(i)

else:

    print(i−1)

 

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

var k, i : longint;

function f(n: longint) : longint;

begin

    f := n*n*n;

end;

 

begin

    readln(k);

    i := 1;

    while f(i) < k do

        i:= i+1;

    if f(i)−k <= k−f(i−1) then

        writeln(i)

    else writeln(i−1);

end.

 

алг

нач

    цел k, i

    ввод k

    i := 1

    нц пока f(i) < k

        i := i + 1

    кц

    если f(i)−k <= k−f(i−1)

    то вывод i

    иначе вывод i−1

    все

кон

 

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

нач

        знач := n * n * n

кон

 

С++

#include <iostream>

using namespace std;

 

int F(int n){

    return n*n*n;

}

int main(){

int i, k;

    cin >> k;

    i = 1;

    while(F(i) < k) i=i+1;

    if(F(i)−k<=k−F(i−1))

        cout << i;

    else

        cout << (i − 1);

    return 0;

}

 

Задание 22 (тема 22, №18089)

Текст задания

Ниже на пяти языках программирования записан алгоритм, который вводит натуральное число x, выполняет преобразования, а затем печатает числа: L и M. Укажите наименьшее из таких чисел x, при вводе которого после выполнения алгоритма будет напечатано сначала 5, а потом 6.

 

 

Бейсик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: longint;

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); write(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;

}

 

 

Задание 23 (тема 23, №18091)

Текст задания

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

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

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

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

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

Программа для исполнителя РазДва — это последовательность команд.

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

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 122 при исходном числе 4 траектория будет состоять из чисел 5, 10, 20.

Задание Д23 (тема Д23, №18092)

Текст задания

Сколько различных решений имеет система логических уравнений

 

 

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

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

...

(x7 ∧ y7) ≡ (¬x8 ∨ ¬y8) = 1

 

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

Задание Д24 C1 (тема Д24 C1, №18093)

Текст задания

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

 

 

БейсикPython

DIM P,I,X,COUNT AS INTEGER

COUNT = 0

P = 0

FOR I = 1 TO 4

    INPUT X

    IF X MOD 10 = 0 THEN

        COUNT = COUNT + 1

        P = X

    END IF

NEXT I

IF P > 0 THEN

    PRINT COUNT

    PRINT P

ELSE

    PRINT ‘NO’

END IF

count = 0

p = 0

for i in range(4):

    x = int(input())

    if x % 10 == 0:

        count = count + 1

        p = x

if p > 0:

    print(count)

    print(p)

else:

    print('NO')

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

var p,i,x,count: integer;

begin

    count := 0;

    p := 0;

    for i := 1 to 4 do begin

        read (x);

        if x mod 10 = 0 then

        begin

            count := count+1;

            p := x;

        end

    end;

if p > 0 then begin

    writeln(count);

    writeln(p);

end

else

    writeln('NO')

end.

алг

нач

    цел p, i, x, count

    count := 0

    p := 0

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

        ввод x

        если mod(x,10) = 0 то

            count := count + 1

            p := x

        все

    кц

    если p > 0 то

        вывод count

        вывод p

    иначе вывод "NO"

кон

С++

#include <iostream>

using namespace std;

int main(){

    int p, i, x, count;

    count = 0; p = 0;

    for(i=0; i < 4; i = i + 1){

        cin >> x;

        if(x % 10 == 0){

            count = count + 1;

            p = x;

        }

    }

    if(p > 0)

        cout << count << endl << p;

    else

        cout << "NO";

    return 0;

}

 

 

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

1. Напишите, что выведет эта программа при вводе 13, 20, 37, 40.

2. Приведите пример входных данных, при вводе которых программа выведет верный ответ. Среди вводимых чисел должно быть хотя бы одно, удовлетворяющее условию отбора. Укажите этот ответ.

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

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

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

Задание Д25 C2 (тема Д25 C2, №18094)

Текст задания

Дан массив, содержащий 70 положительных целых чисел. Необходимо найти сумму чисел не меньших 49 и кратных 7. Далее алгоритм должен заменить такие значения на найденную сумму и вывести измененный массив на экран (по одному элементу в строке).

Напишите на одном из языков программирования программу для решения этой задачи.

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

 

БейсикPython

CONST N=70

DIM A(N) AS INTEGER

DIM I, J, X AS INTEGER

FOR I = 1 TO N

    INPUT A(I)

NEXT I

…

END

# кроме уже указанных

# допускается использование

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

# j, x

a = []

n = 70

for i in range(0, n):

    a.append(int(input()))

…

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

const

    N=70;

var

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

    i, j, x: integer;

begin

    for i:=1 to N do

        readln(a[i]);

    …

end.

алг

нач

    цел N=70

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

    цел i, j, x

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

        ввод a[i]

    кц

    …

кон

С++

#include <iostream>

using namespace std;

const int N=70;

    int main(){

    int a[N];

    int i, j, x;

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

        cin >> a[i];

    …

    return 0;

}

 

 

 

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

Задание Д26 C3.1 (тема Д26 C3, №6435)

Варианты

Текст задания

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

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

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

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

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

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

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

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

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

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

Задание Д26 C3.2 (тема Д26 C3, №18095)

Варианты

Текст задания

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

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

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

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

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

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

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

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

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

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

Задание Д27 C4 (тема Д27 C4, №18096)

Текст задания

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре неважен). Необходимо определить количество пар, для которых произведение элементов кратно 62.

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

В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10000. В качестве результата программа должна вывести одно число: количество пар, в которых произведение элементов кратно 62.

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

5

2

6

13

31

93

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

4

Пояснение. Из 5 чисел можно составить 4 пары, удовлетворяющие условию. Для заданного набора чисел получаем пары (2, 31), (2, 93), (6, 31), (6, 93).

Напишите эффективную по времени и по памяти программу для решения этой задачи.

Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.

Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.

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

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

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

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

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