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


Вариант № 4595652

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


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


Версия для печати и копирования в MS Word
1
Задание 1 № 10304

Вычислите: 101010112 − 2538 + 616. Ответ запишите в десятичной системе счисления.


Ответ:

2
Задание 2 № 16805

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

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

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

 

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

 

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

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

 

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

 

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


Ответ:

3
Задание 3 № 7442

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

 

ABCDEFG
A51225
B58
C24510
D1282
E45
F55
G251055

 

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


Ответ:

4
Задание 4 № 10307

В фрагменте базы данных представлены сведения о родственных отношениях. Укажите в ответе идентификационный номер (ID) бабушки Сабо С.А.

 

Таблица 1
IDФамилия_И.О.Пол
1243Бесчастных П.А.М
1248Попович А.А.М
1250Ан Н.А.Ж
1251Ан В.А.Ж
1257Фоменко П.И.М
2230Фоменко Е.А.Ж
2300Фоменко И.А.М
3252Фоменко Т.Х.Ж
3293Поркуян А.А.Ж
3319Сабо С.А.Ж
5215Фоменко А.К.М
6214Попович Л.П.Ж
6258Фоменко Т.И.Ж
9252Бесчастных А.П.М
.........

Таблица 2
ID_РодителяID_Ребенка
22301243
22301251
22303319
23006258
23001257
32526258
32521257
52152230
52152300
62142230
62142300
92521243
92521251
92523319
......


Ответ:

5
Задание 5 № 1123

Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-0, Б-11, В-100, Г-011. Через канал связи передаётся сообщение: ГБАВАВГ. Закодируйте сообщение данным кодом. Полученное двоичное число переведите в восьмеричный вид.


Ответ:

6
Задание 6 № 3402

Исполнитель КВАДРАТОР имеет только две команды, которым присвоены номера:

 

1. возведи в квадрат

2. прибавь 1

 

Выполняя команду номер 1, КВАДРАТОР возводит число на экране в квадрат, а выполняя команду номер 2, прибавляет к этому числу 1. Напишите программу, содержащую не более 4 команд, которая из числа 1 получает число 17. Укажите лишь номера команд. Например, программа 12122 — это программа:

 

возведи в квадрат

прибавь 1

возведи в квадрат

прибавь 1

прибавь 1

 

которая преобразует число 1 в число 6.


Ответ:

7
Задание 7 № 7200

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

 

ABC
113
2=A1+2*B1+1=C1–A1=(C1+A1)/2

 

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

Из­вест­но, что все зна­че­ния диа­па­зо­на, по ко­то­рым по­стро­е­на диа­грам­ма, имеют один и тот же знак.


Ответ:

8
Задание 8 № 6265

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

 

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

DIM N, S AS INTEGER

N = 0

S = 0

WHILE S <= 267

S = S + 25

N = N + 10

WEND

PRINT N

var n, s: integer;

begin

    n := 0;

    s := 0;

    while s <= 267 do

    begin

        s := s + 25;

        n := n + 10

    end;

    write(n)

end.

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

#include <iostream>

using namespace std;

int main()

{

    int n, s;

    n = 0;

    s = 0;

    while (s <= 267)

    {

        s = s + 25;

        n = n + 10;

    }

    cout « n « endl;

}

алг

нач

цел n, s

n := 0

s := 0

нц пока s <= 267

    s := s + 25

    n := n + 10

кц

вывод n

кон

Python

n = 0

s = 0

while s <= 267:

    s += 25

    n += 10

print(n)

 


Ответ:

9
Задание 9 № 2433

Документ объемом 5 Мбайт можно передать с одного компьютера на другой двумя способами:

 

А) Сжать архиватором, передать архив по каналу связи, распаковать.

Б) Передать по каналу связи без использования архиватора.

 

Какой способ быстрее и насколько, если

– средняя скорость передачи данных по каналу связи составляет 218 бит в секунду,

– объем сжатого архиватором документа равен 80% от исходного,

– время, требуемое на сжатие документа – 35 секунд, на распаковку – 3 секунды?

 

В ответе напишите букву А, если способ А быстрее или Б, если быстрее способ Б. Сразу после буквы напишите количество секунд, насколько один способ быстрее другого.

Так, например, если способ Б быстрее способа А на 23 секунды, в ответе нужно написать Б23.

Слов «секунд», «сек.», «с.» к ответу добавлять не нужно.


Ответ:

10
Задание 10 № 3238

Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка:

 

1. ААААА

2. ААААК

3. ААААР

4. ААААУ

5. АААКА

……

 

Запишите слово, которое стоит на 450-м месте от начала списка.


Ответ:

11
Задание 11 № 13460

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

 

БейсикPython

 FUNCTION F(n)

  IF n > 2 THEN

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

  ELSE

     F = 2

  END IF

 END FUNCTION

 

 FUNCTION G(n)

  IF n > 2 THEN

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

  ELSE

     G = 2

  END IF

 END FUNCTION

def F(n):

    if n > 2:

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

    else: return 2

def G(n):

    if n > 2:

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

    else: return 2

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

function F(n : integer): integer;

 begin

  if n > 2 then

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

  else

   F := 2;

 end;

function G(n : integer): integer;

 begin

  if n > 2 then

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

  else

   G := 2;

 end;

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

 нач

  если n > 2

  то

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

  иначе

    знач:=2

  все

 кон

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

 нач

  если n > 2

  то

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

  иначе

    знач:=2

  все

 кон

Си

int F(int n) {

    if (n > 2)

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

    else

     return 2;

}

int G(int n) {

    if (n > 2)

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

    else

     return 2;

}

 

 

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


Ответ:

12
Задание 12 № 13542

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

 

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

 

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


Ответ:

13
Задание 13 № 232

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

Каж­дый такой номер в ком­пью­тер­ной про­грам­ме за­пи­сы­ва­ет­ся ми­ни­маль­но воз­мож­ным и оди­на­ко­вым целым ко­ли­че­ством бай­тов (при этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние и все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством битов).

Опре­де­ли­те объём па­мя­ти, от­во­ди­мый этой про­грам­мой для за­пи­си 110 но­ме­ров. (Ответ дайте в бай­тах.)


Ответ:

14
Задание 14 № 5708

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, включает в себя 4 команды-приказа и 4 команды проверки условия.

Команды-приказы:

вверхвнизвлевовправо

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.

Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится, и программа прервётся.

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

сверху свободноснизу свободнослева свободносправа свободно

Цикл

 

ПОКА условие

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

КОНЕЦ ПОКА

 

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

 

ЕСЛИ условие

ТО команда1

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

КОНЕЦ ЕСЛИ

 

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

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

 

НАЧАЛО

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

ЕСЛИ снизу свободно

ТО вниз

ИНАЧЕ влево

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ


Ответ:

15
Задание 15 № 3297

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

 


Ответ:

16
Задание 16 № 2329

Укажите наименьшее основание системы счисления, в которой запись числа 50 трехзначна.


Ответ:

17
Задание 17 № 5316

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

 

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

 

ЗапросНайдено страниц
(в тысячах)
Ильф & Петров & Остап800
Ильф & Петров & Бендер600
Ильф & Петров & Бендер & Остап500

 

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

 

 

(Ильф & Петров & Остап)|(Ильф & Петров & Бендер)?

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


Ответ:

18
Задание 18 № 13602

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Например, 14&5 = 11102&01012 = 01002 = 4.

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

 

x&49 ≠ 0 → (x&41 = 0 → x&А ≠ 0)

 

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


Ответ:

19
Задание 19 № 3360

Значения элементов двух массивов A[1..100] и B[1..100] задаются с помощью следующего фрагмента программы:

 

 

БейсикPython

 

FOR n = 1 TO 100

    A(n) = n - 50

NEXT n

FOR n = 1 TO 100

    B(101-n) = A(n)*A(n);

NEXT n

 

 

for n in range(1, 101):

    A[n] = n - 50

for n in range(1, 101):

    B[101-n] = A[n]*A[n]

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

 

for n : = 1 to 100

    do A[n] : = n - 50;

for n : = 1 to 100 do begin

    B[101-n]:= A[n]*A[n];

end;

 

нц для n от 1 до 100

    A[n] : = n - 50

кц

нц для n от 1 до 100

    B[101-n]:=A[n]*A[n]

кц

 

Си++

 

for (n = 1; n <= 100; n++) {

    A[n] = n - 50;

}

for (n = 1; n <= 100; n++) {

    B[101-n] = A[n]*A[n];

}

 

 

Какой элемент массива B будет наименьшим?

 

1) B[1]

2) B[50]

3) B[51]

4) B[100]


Ответ:

20
Задание 20 № 15957

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

 

 

Бейсик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 8

    ELSE

        B = B * X MOD 8

    END IF

    X = X \ 8

WEND

PRINT A

PRINT B

 

x = int(input())

a=0; b=1

while x > 0:

    if x%2 > 0:

        a += x%8

    else:

        b = b * x%8

    x = x//8

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 8

        else

            b := b * x mod 8;

        x := x div 8;

    end;

    writeln(a); write(b);

end.

 

алг

нач

    цел x, a, b

    ввод x

    a := 0; b := 1

    нц пока x > 0

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

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

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

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

    кц

    вывод 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%8;

        else

            b *= x%8;

        x = x / 8;

    }

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

    return 0;

}

 

 


Ответ:

21
Задание 21 № 8669

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

 

 

Бейсик Python

DIM K, I AS LONG

INPUT K

I = 0

WHILE F(I) < K

    I = I + 1

WEND

PRINT I

FUNCTION F(N)

    F = 3*N*N+1

END FUNCTION

def f(n):

    return 3*n*n+1

k = int(input())

i = 0

while f(i) < k:

    i = i + 1

print(i)

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

алг

нач

    цел i, k

    ввод k

    i := 0

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

        i := i+1

    кц

    вывод i

кон

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

нач

    знач := 3*n*n+1

кон

var k, i : longint;

function f(n: longint):longint;

begin

    f := 3*n*n+1

end;

begin

    readln(k);

    i := 0;

    while (f(i)<k) do

        i := i+1;

    writeln(i)

end.

Си++

#include <iostream>

using namespace std;

long f(long n) {

    return 3*n*n+1;

}

int main()

{

    long k, i;

    cin >> k;

    i = 0;

    while (f(i)<k)

        i++;

    cout << i << endl;

}

 


Ответ:

22
Задания Д18 № 7304

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

 

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

a = 56

b = 7

k = 11

a = a / 8 – b

IF a > b THEN

c = a – k * b

ELSE

c = a + k * b

END IF

a := 56;

b := 7;

k := 11;

a := a/8 – b;

if a > b then

c := a – k*b

else

c := a + k*b;

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

a = 56;

b = 7;

k = 11;

a = a/8 – b;

if (a > b)

c = a – k*b;

else

c = a + k*b;

a := 56

b := 7

k := 11

a := a/8 – b

если a > b

то c := a – k*b

иначе c := a + k*b

все

Python

a = 56

b = 7

k = 11

a = a/8 - b

if a > b:

    c = a - k*b

else:

    c = a + k*b;

 


Ответ:

23
Задание 23 № 15933

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, x6, x7, x8 которые удовлетворяют всем перечисленным ниже условиям?

 

(x1≡x2)→(x2≡x3) = 1

(x2≡x3)→(x3≡x4) = 1

...

(x6≡x7)→(x7≡x8) = 1

 

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, x6, x7, x8 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.


Ответ:

24
Задание 24 № 3597

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

 

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

var х,у: real;

begin

readln(x,y);

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

if у >= −2 then

if у <= x then

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

else

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

end.

INPUT x, у

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

IF у >= −2 THEN

IF у <= x THEN

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

ELSE

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

ENDIF

ENDIF

ENDIF

END

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

{ float x, у;

cin >> x >> y ;

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

if (у >= −2)

if (у <= x)

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

else

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

}

алг

нач

вещ х, у

ввод х, у

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

если у >= −2 то

если у <= x то

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

иначе

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

все

все

все

кон

Python

x = float(input())

y = float(input())

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

    if у >= −2:

        if у <= x:

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

        else:

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

 

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

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

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

 

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

 

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

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

Условие 2

(у >= −2)

Условие 3

(у <= x)

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

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

25
Задание 25 № 4957

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

 

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

const

N=70;

var

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

i, j, x, y: integer;

begin

for i := 1 to N do

readln(a[i]);

end.

алг

нач

цел N=70

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

цел i, j, x, y

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

ввод a[i]

кц

...

кон

БейсикСи++

N=70

DIM A(N) AS INTEGER

DIM I, J, X, Y AS INTEGER

FOR I = 1 TO N

INPUT A(I)

NEXT I

END

#include <iostream>

using namespace std;

#define N 70

int main(void){

long a[N];

long i, j, x, y;

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

cin >> a[i];

}

Python

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

# использовать три

# целочисленные переменные j, x, y

a = []

n = 70

for i in range(0, n):

a.append(int(input()))

...

 

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


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

26
Задание 26 № 4878

Два игрока, Петя и Ваня, играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди, первый ход делает Петя. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 3 камня в какую-то кучу. Игра завершается в тот момент, когда количество камней в одной из куч становится не менее 14. Если в момент завершения игры количество камней в одной из куч не менее 21, то выиграл Ваня, в противном случае — Петя. Кто выигрывает при безошибочной игре обоих игроков? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.


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

27
Задание 27 № 6792

Дед Мороз и Сне­гу­роч­ка при­хо­дят на дет­ские утрен­ни­ки с меш­ком кон­фет. Дед Мороз делит кон­фе­ты по­ров­ну между всеми при­сут­ству­ю­щи­ми детьми (детей на утрен­ни­ке ни­ко­гда не бы­ва­ет боль­ше 100), а остав­ши­е­ся кон­фе­ты от­да­ет Сне­гу­роч­ке. Сне­гу­роч­ка каж­дый раз за­пи­сы­ва­ет в блок­нот ко­ли­че­ство по­лу­чен­ных кон­фет. Если кон­фе­ты раз­де­ли­лись между всеми детьми без остат­ка, Сне­гу­роч­ка ни­че­го не по­лу­ча­ет и ни­че­го не за­пи­сы­ва­ет. Когда утрен­ни­ки за­кон­чи­лись, Деду Мо­ро­зу стало ин­те­рес­но, какое число чаще всего за­пи­сы­ва­ла Сне­гу­роч­ка. Дед Мороз и Сне­гу­роч­ка — вол­шеб­ные, по­это­му число утрен­ни­ков N, на ко­то­рых они по­бы­ва­ли, может быть очень боль­шим. На­пи­ши­те про­грам­му, ко­то­рая будет ре­шать эту за­да­чу. Перед тек­стом про­грам­мы крат­ко опи­ши­те ал­го­ритм ре­ше­ния за­да­чи и ука­жи­те ис­поль­зу­е­мый язык про­грам­ми­ро­ва­ния и его вер­сию.

 

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

 

За­да­ние А. Име­ет­ся набор чисел, со­сто­я­щий из 10 пар по­ло­жи­тель­ных целых чисел. В этом ва­ри­ан­те за­да­ния оце­ни­ва­ет­ся толь­ко пра­виль­ность про­грам­мы, время ра­бо­ты и раз­мер ис­поль­зо­ван­ной па­мя­ти не имеют зна­че­ния.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му – 2 балла.

 

За­да­ние Б. Име­ет­ся набор дан­ных, со­сто­я­щий из пар по­ло­жи­тель­ных целых чисел. По­ста­рай­тесь сде­лать про­грам­му эф­фек­тив­ной по вре­ме­ни и ис­поль­зу­е­мой па­мя­ти (или хотя бы по одной из этих ха­рак­те­ри­стик).

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

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

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

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

 

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

В пер­вой стро­ке вво­дит­ся одно целое по­ло­жи­тель­ное число — ко­ли­че­ство утрен­ни­ков N. Каж­дая из сле­ду­ю­щих N строк со­дер­жит два целых числа: сна­ча­ла D — ко­ли­че­ство при­шед­ших на оче­ред­ной утрен­ник детей, а затем K – ко­ли­че­ство кон­фет в мешке Деда Мо­ро­за на этом утрен­ни­ке. Га­ран­ти­ру­ет­ся вы­пол­не­ние сле­ду­ю­щих со­от­но­ше­ний:

1 ≤ N ≤ 10000

1 ≤ D ≤ 100 (для каж­до­го D)

D ≤ K ≤ 1000 (для каж­дой пары D, K)

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

Про­грам­ма долж­на вы­ве­сти одно число — то, ко­то­рое Сне­гу­роч­ка за­пи­сы­ва­ла чаще всего. Если не­сколь­ко чисел за­пи­сы­ва­лись оди­на­ко­во часто, надо вы­ве­сти боль­шее из них. Если Сне­гу­роч­ка ни разу ни­че­го не за­пи­сы­ва­ла, надо вы­ве­сти ноль.

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

7

10 58

15 315

20 408

100 1000

32 63

32 63

11 121

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

31


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