СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


Вариант № 5445852

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


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


Версия для печати и копирования в MS Word
Времени прошло:0:00:00
Времени осталось:3.9166666666666665:55:00
1
Задание 1 № 14762

Сколько нулей в двоичной записи десятичного числа 507?


Ответ:

2
Задание 2 № 11258

Логическая функция F задаётся выражением

 

¬z ∨ (¬x ∧ y).

 

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

 

Перем. 1Перем. 2Перем. 3Функция
?????????F
0001
0011
0101
0111
1011

 

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

 

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

 

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

 

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


Ответ:

3
Задание 3 № 7916

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.

 

ABCDEF
A24816
B23
C43
D83353
E55
F1635

 

Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам.


Ответ:

4
Задание 4 № 16433

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

 

Таблица 1
IDФамилия И.О.ПолГод рождения
127Петренко А.В. М1935
148Петренко Д.И. М2000
182 Петренко Е.П. Ж1942
212Петренко И.А. М1975
243 Петренко Н.Н. Ж1975
254Штейн А.Б. М1977
314Петренко Е.И.М1999
404 Дулевич М.А.Ж1970
512Тишко О.К. Ж1991
517Дулевич В.К. М1996
630 Штейн Б.В. М1954
741 Петрова А.Е. Ж1958
830 Штейн А.Н. Ж1978
849Косых Н.Н. Ж1952

Таблица 2
ID РодителяID Ребенка
127 212
182212
212148
243148
254314
127404
182404
404512
404517
630254
741254
830314
849243
849830


Ответ:

5
Задание 5 № 3669

Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:

 

abcde
0001100100110

 

Какой набор букв закодирован двоичной строкой 1100000100110?

 


Ответ:

6
Задание 6 № 11235

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

 

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

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

 

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

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


Ответ:

7
Задание 7 № 4555

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

 

ABC
124
2= (B1 – A1)/2= 2 – A1/2= (C1 – A1)*2 – 4

 

Какое целое число долж­но быть за­пи­са­но в ячей­ке C1, чтобы по­стро­ен­ная после вы­пол­не­ния вы­чис­ле­ний диа­грам­ма по зна­че­ни­ям диа­па­зо­на ячеек A2 : С2 со­от­вет­ство­ва­ла ри­сун­ку? Из­вест­но, что все зна­че­ния диа­па­зо­на, по ко­то­рым по­стро­е­на диа­грам­ма, имеют один и тот же знак.


Ответ:

8
Задание 8 № 7780

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

 

Бей­сикPython

DIM S, N AS INTEGER

S = 42

N = 1

WHILE S > 0

S = S – 5

N = N + 3

WEND

PRINT(N)

s = 42

n = 1

while s > 0:

    s = s - 5

    n = n + 3

print(n)

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

var s, n: integer;

begin

    s := 42;

    n := 1;

    while s > 0 do

    begin

        s := s – 5;

        n := n + 3

    end;

    writeln(n)

end.

алг

нач

цел s, n

s := 42

n := 1

нц пока s > 0

    s := s — 5

    n := n + 3

кц

вывод n

кон

Си++

#include <iostream>

using namespace std;

int main()

{

    int s, n;

    s = 42;

    n = 1;

    while (s > 0) {

        s = s – 5;

        n = n + 3;

    }

    cout << n << endl;

}

 


Ответ:

9
Задание 9 № 3808

Текстовый документ, состоящий из 5120 символов, хранился в 8-битной кодировке КОИ-8. Этот документ был преобразован в 16-битную кодировку Unicode. Укажите, какое дополнительное количество Кбайт потребуется для хранения документа. В ответе запишите только число.


Ответ:

10
Задание 10 № 5211

Сколько есть различных символьных последовательностей длины от одного до четырёх в трёхбуквенном алфавите {А, B, C}?


Ответ:

11
Задание 11 № 9797

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

 

БейсикPython

DECLARE FUNCTION F(n)

DECLARE FUNCTION G(n)

FUNCTION F(n)

  IF n > 2 THEN

    F = F(n - 1) + G(n-2)

  ELSE

    F = 1

  END IF

END FUNCTION

FUNCTION G(n)

  IF n > 2 THEN

    G = G(n - 1) + F(n-2)

  ELSE

    G = 1

  END IF

END FUNCTION

def F(n):

  if n > 2:

    return F(n-1)+ G(n-2)

  else: return 1

def G(n):

  if n > 2:

  return G(n-1) + F(n-2)

  else: return 1

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

function F(n: integer): integer;

begin

  if n > 2 then

    F := F(n - 1) + G(n - 2)

  else

    F := 1;

end;

function G(n: integer): integer;

begin

  if n > 2 then

    G := G(n - 1) + F(n - 2)

  else

    G := 1;

end;

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

нач

  если n > 2

    то

      знач := F(n - 1) + G(n - 2)

    иначе

      знач := 1

  все

кон

алг цел G(цел n)

нач

  если n > 2

    то

      знач := G(n - 1) + F(n - 2)

    иначе

      знач := 1

  все

кон

Си

int F(int n)

{

  if (n > 2)

    return F(n-1) + G(n-2);

  else return 1;

}

int G(int n)

{

  if (n > 2)

    return G(n-1) + F(n-2);

  else return 1;

}

 

Чему будет равно значение, вычисленное при выполнении вызова F(8)?


Ответ:

12
Задание 12 № 10475

В терминологии сетей 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 № 5610

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


Ответ:

14
Задание 14 № 6773

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, включает в себя 4 команды-приказа и 4 команды проверки условия. Команды-приказы: вверх, вниз, влево, вправо. При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится, и программа прервётся.

Другие 4 команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: сверху свободно, снизу свободно, слева свободно, справа свободно.

Цикл

 

ПОКА условие

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

КОНЕЦ ПОКА

 

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

 

ЕСЛИ условие

ТО команда1

ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

 

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)?

 

НАЧАЛО

ПОКА снизу свободно ИЛИ справа свободно

ПОКА снизу свободно

вниз

КОНЕЦ ПОКА

вправо

КОНЕЦ ПОКА

КОНЕЦ


Ответ:

15
Задание 15 № 6269

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


Ответ:

16
Задание 16 № 15926

Значение выражения 367 + 619 − 18? записали в системе счисления с основанием 6.

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


Ответ:

17
Задание 17 № 8665

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

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

 

ЗапросНайдено страниц (в сотнях тысяч)
Зима650
Мороз500
Жаворонок380
Зима | Мороз | Жаворонок1000
Мороз & Жаворонок0
Зима & Мороз250

 

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

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


Ответ:

18
Задание 18 № 16821

Для какого наименьшего целого неотрицательного числа A выражение

 

(3x + 4y ≠ 70) ∨ (A > x) ∨ (A > y)

 

тождественно истинно при любых целых неотрицательных x и y?


Ответ:

19
Задание 19 № 7301

Ниже представлен записанный на разных языках программирования фрагмент одной и той же программы. В программе описан одномерный целочисленный массив A, в представленном фрагменте программы обрабатываются элементы массива с индексами от 1 до 25.

 

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

n = 25

A(1) = 2

FOR i = 2 TO n

    A(i) = 2*A(i–1) MOD 10

NEXT i

n:=25;

A[1]:=2;

for i:= 2 to n do begin

    A[i] := 2*A[i–1] mod 10;

end;

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

n=25;

A[1] = 2;

for (i = 2; i <= n; i++) {

    A[i] = 2*A[i–1] % 10;

}

n:=25

A[1] := 2

нц для i от 2 до n

    A[i] = mod (2*A[i–1], 10)

кц

Python

n = 25

A[1] = 2

for i in range(2, n+1):

    A[i] = 2*A[i–1] % 10

 

 

Чему будет равно значение элемента A[25] (то есть элемента массива с индексом 25) после выполнения фрагмента программы?


Ответ:

20
Задание 20 № 16395

Ниже на пяти языках записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа a и b. Укажите наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 2, а потом 10.

 

 

БейсикPython

DIM X, A, B AS INTEGER

INPUT X

A = 0: B = 1

WHILE X > 0

    IF X MOD 2 > 0 THEN

        A = A + X MOD 12

    ELSE

        B = B * (X MOD 12)

    END IF

    X = X \ 12

WEND

PRINT A

PRINT B

 

x = int(input())

a=0; b=1

while x > 0:

    if x%2 > 0:

        a += x%12

    else:

        b *= x%12

    x = x // 12

print(a, b)

 

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

var x, a, b: longint;

begin

    readln(x);

    a := 0; b := 1;

    while x > 0 do begin

        if x mod 2 > 0 then

            a := a + x mod 12

        else

            b := b * (x mod 12);

        x := x div 12;

    end;

    writeln(a); write(b);

end.

 

алг

нач

    цел x, a, b

    ввод x

    a := 0; b := 1

    нц пока x > 0

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

            то a := a + mod(x,12)

            иначе b:=b*mod(x,12)

        все x := div(x,12)

    кц

    вывод a, нс, b

кон

 

С++

#include <iostream>

using namespace std;

int main()

{

    int x, a, b;

    cin >> x;

    a = 0; b = 1;

    while (x > 0) {

        if (x%2 > 0)

            a += x%12;

        else

            b *= x%12;

        x = x / 12;

    }

    cout << a << endl << b << endl;

    return 0;

}

 

 


Ответ:

21
Задание 21 № 10484

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

 

 

БейсикPython

DIM K, I AS LONG

INPUT K

I = 1

WHILE F(I) < G(K)

    I = I + 1

WEND

PRINT I

 

FUNCTION F(N)

  F = N * N * N

END FUNCTION

 

FUNCTION G(N)

  G = 2*N + 1

END FUNCTION

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)

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

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.

алг

нач

  цел i, k

  ввод k

  i := 1

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

    i := i + 1

  кц

  вывод i

кон

 

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

нач

  знач := n * n * n

кон

 

алг цел g(цел n)

нач

  знач := 2*n + 1

кон

Си++

#include <iostream>

using namespace std;

long f(long n) {

  return n * n * n;

}

 

long g(long n) {

  return 2*n + 1;

}

 

int main()

{

  long k, i;

  cin >> k;

  i = 1;

  while (f(i) < g(k))

    i++;

  cout << i << endl;

  return 0;

}

 


Ответ:

22
Задание 22 № 18091

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

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

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

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

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

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

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

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


Ответ:

23
Задание 23 № 15863

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

 

(x1x2) ∧ (¬x1 ∨ ¬x2) ∧ (¬x1y1) = 1

(x2x3) ∧ (¬x2 ∨ ¬x3) ∧ (¬x2y2) = 1

...

(x6x7) ∧ (¬x6 ∨ ¬x7) ∧ (¬x6y6) = 1

x7y7) = 1

 

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


Ответ:

24
Задание 24 № 2801

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

 

ПаскальБейсик
var x,y: real;

begin

readln(x,y);

if x*x+y*y>=4 then

if x>= –2 then

if y<= –x then

write('принадлежит')

else

write('не принадлежит')

end.

INPUT x, y

IF x*x+y*y>=4 THEN

IF x>= –2 THEN

IF y<= –x THEN

PRINT "принадлежит"

ELSE

PRINT "не принадлежит"

ENDIF

ENDIF

ENDIF

END

Си++Алгоритмический
int main()

{

float x,y;

cin >> x >> y;

if (x*x+y*y>=4)

if (x>= –2)

if (y<= –x)

cout << "принадлежит";

else

cout << "не принадлежит";

}

алг

нач

вещ x,y

ввод x,y

если x*x+y*y>=4 то

    если x>= –2 то

        если y<= –x то

            вывод 'принадлежит'

        иначе

            вывод 'не принадлежит'

        все

    все

все

кон

Python

x = float(input())

y = float(input())

if x*x+y*y >= 4:

    if x >= −2:

        if у <= -x:

            print("принадлежит")

        else:

            print("не принадлежит")

 

 

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

1. Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (A, B, C, D, E, F, G и H).

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

 

2. Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы.)

 

ОбластьУсловие 1

(x*x+y*y>=4)

Условие 2

(x>= –2)

Условие 3

(y<= –x)

Программа выведетОбласть обрабатывается верно
A
В
С
D
Е
F
G
Н

Решения заданий с развернутым ответом не проверяются автоматически.
На следующей странице вам будет предложено проверить их самостоятельно.

25
Задание 25 № 15865

Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит сумму элементов массива, меньших 200 и при этом кратных 5, а затем заменяет каждый такой элемент на число, равное найденной сумме. Гарантируется, что хотя бы один такой элемент в массиве есть. В качестве результата необходимо вывести изменённый массив, каждый элемент выводится с новой строчки. Например, для исходного массива из шести элементов:

204

115

27

20

305

4

программа должна вывести следующий массив:

204

135

27

135

305

4

 

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

 

БейсикPython

CONST N AS INTEGER = 30

DIM A (1 TO N) AS LONG

DIM I, J, 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

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

    цел i, j, k

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

        ввод a[i]

    кц

    ...

кон

Си++

#include <iostream>

using namespace std;

const int n = 30;

int main() {

    int a[n];

    int i, j, k;

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

        std::cin >> a[i];

    ...

     return 0;

}

 

 

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


Решения заданий с развернутым ответом не проверяются автоматически.
На следующей странице вам будет предложено проверить их самостоятельно.

26
Задание 26 № 14787

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

 

увеличить количество камней в куче в два раза или увеличить количество камней в куче в три раза.

 

Например, имея кучу из 10 камней, за один ход можно получить кучу из 20 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 49.

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

 

Выполните следующие задания.

 

Задание 1. Назовите все значения S, при которых Петя может выиграть первым ходом, причём у Пети есть ровно один выигрывающий ход.

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

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


Решения заданий с развернутым ответом не проверяются автоматически.
На следующей странице вам будет предложено проверить их самостоятельно.

27
Задание 27 № 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 балла.

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

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


Решения заданий с развернутым ответом не проверяются автоматически.
На следующей странице вам будет предложено проверить их самостоятельно.
Времени прошло:0:00:00
Времени осталось:3.9166666666666665:55:00
Завершить тестирование, свериться с ответами, увидеть решения.