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

Вариант 4

Часть 1.

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

1
1

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

2
2

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

ABCDEF
A53
B24
C223
D521
E312
F432

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

3
3

Дан фрагмент таблицы истинности выражения F.

x1x2x3x4x5x6x7x8F
111111111
100001011
011110101

Каким выражением может быть F?

1) ¬x1 ∧ x2 ∧ x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ x7 ∧ x8

2) ¬x1 ∧ x2 ∧ x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ x7 ∧ ¬x8

3) ¬x1 v x2 v x3 v x4 v x5 v x6 v ¬x7 v x8

4) ¬x1 v x2 v x3 v x4 v x5 v ¬x6 v x7 v ¬x8

4
4

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

Символ «?» (вопросительный знак) означает ровно один произвольный символ. Символ «*» (звёздочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность.

В каталоге находятся шесть файлов:

cba.doc cat.doc rat.docx bat.docx all.dat whale.dll

Ниже представлено восемь масок. Сколько из них таких, которым соответствуют ровно три файла из данного каталога?

*?a*?.d?**?а*. ???**?a?.d??*.?
*a?.d*c**??a*?.d?*?а*. d?c**at*.*d*

1) 1

2) 2

3) 4

4) 6

5
5

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

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

2. Полученные три числа записываются друг за другом в порядке убывания (без разделителей).

Пример. Исходное число: 7531. Суммы: 7 + 5 = 12; 5 + 3 = 8; 3 + 1 = 4. Результат: 1284.

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

6
6

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

ABCD
11379
2131519
3232527=B$3*2+C$4
421313341

Формулу из ячейки D3 скопировали в ячейку С2 так, что числовое значение ячейки С2 стало отличаться от числового значения ячейки D3. Каково стало числовое значение ячейки С2?

7
7

На студии при двухканальной (стерео) звукозаписи с 16-битным разрешением за 1 минуту был записан звуковой файл. Сжатие данных не производилось. Известно, что размер файла оказался 7500 Кбайт. С какой частотой дискретизации (в кГц) велась запись? В качестве ответа укажите только число, единицы измерения указывать не нужно.

8
8

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

Бейсик

DIM k, s AS INTEGER <br />s = 0 <br />к = 0<br />WHILE к < 200 <br />    s = s + 64 <br />    к = к + 16 <br />WEND <br />PRINT s<br />

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

нач<br />    цел k, s <br />    s : = 0 <br />    k := 0<br />    нц пока k < 200 <br />        s := s + 64 <br />        k := k + 16<br />    кц<br />вывод s<br />кон<br />

Паскаль

var k, s: integer; <br />begin <br />    s : = 0 ; <br />    k := 0;<br />    while k < 200 do <br />    begin<br />        s := s + 64; <br />        k := k + 16; <br />    end;<br />    write (s); <br />end.<br />

Си

{<br />    int к, s; <br />    s = 0 ; <br />    к = 0;<br />    while (k < 200) { <br />        s = s + 64 ; <br />        к = к + 16 ;<br />    }<br />    printf("%d", s) ;<br />}<br />
9
9

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А — 100; Б — 0; В — 110; Г — 111.

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

10
10

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

11
11

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

Бейсик

SUB F(n)<br />    IF n <= 5 THEN <br />        F(n + 2) <br />        PRINT n <br />        F (n + 3)<br />    END IF <br />END SUB<br />

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

алг F(цел n) <br />нач<br />    если n <= 5 то <br />        F(n + 2) <br />        вывод n, нс <br />        F(n + 3)<br />    все<br />кон<br />

Паскаль

procedure F(n: integer); <br />begin<br />    if n <= 5 then <br />    begin<br />        F(n + 2); <br />        writeln (n);<br />        F(n + 3) <br />    end <br />end<br />

Си

void F(int n)<br />{<br />    if (n <= 5)<br />    {<br />        F(n + 2) ;<br />        printf("%d\n", n); <br />        F(n + 3) ;<br />    }<br />}<br />

Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(l)?

12
12

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

Например, если IP-адрес узла равен 131.111.255.131, а маска равна 255.255.192.0, то адрес подсети равен 131.111.192.0.

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

13
13

Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина пароля — ровно 11 символов. В качестве символов используются цифры 2, 4, 6, 8 и 15 различных букв местного алфавита, причём все буквы используются в двух начертаниях: как строчные, так и прописные (регистр буквы имеет значение!).

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

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

14
14

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

Бейсик

INPUT а<br />b = 15<br />а =  - а - 3 * b<br />IF а > b THEN<br />    c = b + 1<br />ELSE<br />    с = b + 2<br />END IF<br />

Паскаль

readln(a);<br />b := 15;<br />a := - a - 3 * b;<br />if a > b then<br />    c : = b + 1<br />else<br />c : = b + 2;<br />

Си

scanf("%d", &а);<br />b = 15;<br />a = - a - 3 * b;<br />if (a > b)<br />    c = b + 1;<br />else<br />    c = b + 2;<br />

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

ввод a<br />b:= 15<br />a:= - a - 3 * b<br />если a > b<br />    то c := b + 1<br />    иначе c := b + 2<br />все<br />
15
15

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

16
16

Известно, что для натурального числа х справедливо равенство

110x + 4 - 568 = 1010.

Определите значение х. Ответ запишите в десятичной системе счисления.

17
17

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

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

ЗапросНайдено страниц (в тыс)
сафари | лев | крокодил800
сафари290
лев | крокодил600

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

(сафари & крокодил) | (сафари & лев)

Укажите целое число, которое напечатает компьютер.

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

18
18

На числовой прямой даны два отрезка: Р = [3, 20] и Q = [6, 12].

Укажите наибольшую возможную длину промежутка А, для которого формула

((x ∈ P) ~ (x ∈ Q)) → ¬(x ∈ A)

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

19
19

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

Бейсик

s = 0 <br />n = 10<br />FOR i = 0 ТО n - 1<br />    s = s + A(i) + А(i+1) <br />NEXT i<br />

Паскаль

s : = 0 ; <br />n := 10;<br />for i := 0 to n - 1 do begin <br />    s := s + A[i] + A[i +1] <br />end;<br />

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

s : = 0<br />n := 10<br />нц для i от 0 до n - 1 <br />    s := s + A[i] + A[i+1]<br />кц<br />

Си

s = 0; <br />n = 10;<br />for (i = 0; i <= n - 1; i++) <br />    s = s + A [ i ] + A [ i +1 ] ;<br />

В начале выполнения этого фрагмента в массиве находились двухзначные чётные натуральные числа. Какое наименьшее значение может иметь переменная s после выполнения данной программы?

20
20

Ниже на четырёх языках записан алгоритм. Получив на вход число х, этот алгоритм печатает два числа: L и М. Укажите наименьшее из таких чисел х, при вводе которых алгоритм печатает сначала 3, а потом 8.

Бейсик

DIM X, L, М AS INTEGER<br />INPUT X<br />L = 0: M = 0<br />WHILE X > 0<br />    L = L + 1<br />    IF М < (X MOD 10) THEN<br />        М = X MOD 10<br />    END IF<br />    X = X \ 10<br />WEND<br />PRINT L<br />PRINT M<br />

Паскаль

var x, L, M: integer;<br />begin<br />    readln(x);<br />    L := 0; M := 0;<br />    while x > 0 do<br />    begin<br />        L := L + 1;<br />        if M < (x mod 10) then<br />            M := x mod 10;<br />        x := x div 10;<br />    end;<br />    writeln(L); write(M); <br />end.<br />

Си

#include<stdio.h><br />void main()<br />{<br />    int x, L, M;<br />    scanf("%dH, &x) ;<br />    L = 0; M = 0;<br />    while (x > 0) {<br />        L = L + 1;<br />        if M < x % 10 {<br />            M = x % 10<br />        }<br />        x = x /10;<br />    }<br />    printf("%d\n%d", L, M);<br />}<br />

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

алг<br />нач<br />    цел х, L, М<br />    ввод X<br />    L := 0; M := 0<br />    нц пока х > 0<br />        L : = L + 1<br />        если М < mod(x,10) то<br />            М := mod(х,10)<br />        все<br />        х := div(х,10)<br />    кц<br />    вывод L, нс, М<br />кон<br />
21
21

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

Бейсик

DIM А, В, Т, R AS INTEGER<br />А = -20: В = 20<br />R = F (А)<br />FOR Т = А ТО В<br />    IF F(Т) < R THEN <br />        R = F (Т)<br />    END IF<br />NEXT Т<br />PRINT R<br /><br />FUNCTION F (x)<br />    F = 5 * (x + 3) * (x - 3)<br />END FUNCTION<br />

Паскаль

var a, b, t, R: integer;<br />function F(x: integer): integer;<br />begin<br />    F := 5 *(x + 3) * (x - 3);<br />end;<br /><br />begin<br />    a := -20; b := 20;<br />    R := F(a);<br />    for t := a to b do<br />    begin<br />        if (F(t) < R) then begin<br />            R := F(t); <br />        end; <br />    end;<br />write(R); <br />end.<br />

Си

int F(int х)<br />{<br />    return 5 *(х + 3)*(х - 3);<br />}<br /><br />void main()<br />{<br />    int а, b, t, R;<br />    a = -20; b = 20;<br />    R = F (a) ;<br />    for (t = a; t <= b; t++) {<br />        if (F(t) < R) {<br />            R = F(t) ;<br />        }<br />    }<br />printf("%d", R);<br />}<br />

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

нач<br />цел а, b, t, R<br />    a := -20; b := 20<br />    R := F(а)<br />    нц для t от а до b<br />        если F(t)< R то<br />            R := F(t)<br />        все<br />    кц<br />    вывод R<br />кон<br /><br />алг цел F(цел х)<br />нач<br />    знач := 5 *(х + 3) *(х - 3)<br />кон<br />
22
22

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

1. прибавь 1,

2. умножь на 3.

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

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

Сколько есть программ, которые число 1 преобразуют в число 24?.

23
23

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

((x1 ~ x3) v (x2 ~ x4)) ∧ (¬((x1 ~ x3) ∧ ¬(x2 ~ x4))) = 0

((x2 ~ x4) v (x5 ~ x7)) ∧ (¬((x2 ~ x4) ∧ ¬(x5 ~ x7))) = 0

((x5 ~ x7) v (x6 ~ x8)) ∧ (¬((x5 ~ x7) ∧ ¬(x6 ~ x8))) = 0

((x6 ~ x8) v (x9 ~ x10)) ∧ (¬((x6 ~ x8) ∧ ¬(x9 ~ x10))) = 0

((x1 ~ x3) → (x2 ~ x4)) → ((x6 ~ x8) v ¬(x9 ~ x10)) = 1

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

 

Часть 2.

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

24

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

Бейсик

CONST n = 4 <br />count = 0 <br />sum = 0<br />FOR I = 1 ТО n <br />    INPUT x<br />    IF x mod 11 = 0 THEN <br />        count = count + 1 <br />        sum = x <br />    END IF <br />NEXT I<br />IF sum > 0 THEN <br />    PRINT count <br />    PRINT sum <br />ELSE<br />    PRINT "NO"<br />END IF<br />

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

алг<br />нач<br />    цел n = 4 <br />    цел i, х <br />    цел sum, count <br />    count := 0 <br />    sum := 0<br />    нц для i от 1 до n <br />        ввод x<br />        если mod(x, 11) = 0 то <br />            count := count + 1 <br />            sum := х <br />        все <br />    кц<br />    если sum > 0<br />    то<br />        вывод count, нс<br />        вывод sum, нс<br />    иначе<br />        вывод "NO"<br />    все<br />кон<br />

Паскаль

const n = 4;<br />var i, x: integer;<br />var sum, count: integer;<br />begin<br />    count := 0; <br />    sum := 0;<br />    for i := 1 to n do <br />    begin<br />        read(x);<br />        if x mod 11 = 0 then <br />        begin<br />            count := count + 1; <br />            sum := x <br />        end <br />    end;<br />    if sum > 0 then <br />    begin<br />    writeln(count); <br />    writeln(sum) <br />    end <br />    else<br />        writeln('NO')<br />end.<br />

Си

#define n 4 void main(void)<br />{<br />    int i, x; <br />    int sum, count; <br />    count = 0; <br />    sum = 0;<br />    for (i = 1; i <= n; i++) <br />#include <stdio.h><br />    {<br />        scanf("%d", &x) ; <br />        if (x % 11 == 0)<br />        {<br />            count++; <br />            sum = x;<br />        }<br />    }<br />    if (sum > 0)<br />    {<br />        printf("%d\n", count);<br />        printf("%d\n", sum);<br />    }<br />    else<br />        printf("N0\n");<br />}<br />

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

1. Напишите, что выведет эта программа при вводе последовательности: 22 33 65 45

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

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

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

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

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

Примечание: 0 делится на любое целое число.

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

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

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

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

2. Пример последовательности, содержащей числа, кратные 11, и для которой программа работает правильно: 1 3 11 20.

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

1) в последовательности сумма чисел, кратных 11, равна последнему числу, кратному 11;

2) это число больше 0.

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

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

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

    
sum := х 

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

sum := sum + х

Вторая ошибка: неверная проверка наличия чисел, кратных 11, при печати.

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

if sum > 0 then

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

if count > 0 then
25

Дан целочисленный массив из 40 элементов. Элементы массива могут принимать целые значения от -10 000 до 10 000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести количество пар элементов массива, сумма которых кратна 13 и положительна. Под парой подразумеваются два подряд идущих элемента массива.

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

Бейсик

<br />N = 40<br />DIM A(N) AS INTEGER<br />DIM I, J, К AS INTEGER<br />FOR I = 1 TO N<br />    INPUT A(I)<br />NEXT I<br />. . .<br />END<br />

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

алг<br />нач<br />    цел N = 40<br />    цел таб а[1:N]<br />    цел i, j, k<br />    нц для i от 1 до N<br />        ввод а[i]<br />    кц<br />...<br />кон<br />

Паскаль

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

Си

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

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

Объявляем массив А из 40 элементов.<br />Объявляем целочисленные переменные I, J,<br />В цикле от 1 до 40 вводим элементы массива А с 1-го по 40-й.<br />
Показать ответ

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

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

 for i := 1 to N - 1 do<br />    if ((a[i] + a[i+l]) mod 13 = 0) and (a[i] + a[i+l] > 0) then <br />        inc(k);<br />writeln(k);

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

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

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

K = 0;<br />FOR I = 1 ТО N - 1<br />    IF (А(I) + А(1+1)) MOD 13 = 0 AND А(1) + А(1+1) > 0 THEN <br />        К = К + 1 <br />    END IF <br />NEXT I <br />PRINT К

На языке Си

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

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

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

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

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

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

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

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

Задание 1

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

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

Задание 2

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

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Вася.

Для каждого указанного значения S опишите выигрышную стратегию Пети.

Задание 3

Укажите значение хотя бы одно значение S, при котором одновременно выполняются два условия:

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

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

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

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

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

Задание 1.

а) Петя может выиграть, удвоив количество камней в куче, если S = 50, ... 99. При меньших значениях S за один ход нельзя получить кучу, в которой не менее 100 камней.

б) Вася может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 49 камней. Тогда после первого хода Пети в куче будет 50, 52 или 98 камней. Во всех случаях Вася удваивает количество камней и выигрывает в один ход.

Задание 2.

Возможные значения S: 46, 48. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 49 камней. Эта позиция разобрана в п. 16). В ней игрок, который будет ходить (теперь это Вася), выиграть не может, а его противник (то есть Петя) следующим ходом выиграет.

Задание 3.

Возможные значения S: 45, 47.

Например, для S = 45 после первого хода Пети в куче будет 46, 48 или 90 камней. Если в куче станет 90 камней, Вася удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 46 или 48 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Вася), выигрывает своим вторым ходом.

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

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

27

Каждую секунду датчик передаёт по каналу связи неотрицательное вещественное число — результат некоторых измерений. Временем, в течение которого происходит передача, можно пренебречь. Необходимо найти в заданной серии показаний датчика максимальную сумму двух показаний, между моментами передачи которых прошло не менее 10 секунд. Значение каждого показания датчика не превышает 1000. Общее количество показаний датчика не превышает 10 000.

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

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

Максимальная оценка за правильную программу, неэффективную ни по времени, ни по памяти, — 2 балла. Перед программой укажите версию языка и кратко опишите использованный алгоритм. В первой строке задаётся число N — общее количество показаний прибора. Гарантируется, что N > 10. В каждой из следующих N строк задаётся одно неотрицательное вещественное число — очередное показание датчика.

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

11

12

45

5

4

25

23

21

20

10

12

26

Программа должна вывести одно число — описанное в условии произведение.

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

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

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

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

program task32;<br />const s = 10; {требуемое расстояние между показаниями} <br />var<br />    N: integer;<br />    a: array[0..s - 1] of real; {хранение показаний прибора}<br />    {k-e введенное число записываем в ячейку a[k mod 3]} <br />    а_: real; {ввод очередного показания} <br />    mx: real; {максимальное введённое число}<br />    {не считая 10 последних} <br />    m: real; {максимальное значение суммы} <br />    i: integer; <br />begin<br />    readln(N);<br />    {Ввод первых 10 чисел} <br />    for i := 1 to s do <br />    begin<br />        readln(a_); <br />        a[i mod s] := a_<br />    end;<br />    {Ввод остальных значений, поиск максимальной суммы } <br />    mх := -1; т := -1; <br />    for i := s + 1 to N do <br />    begin<br />        readln(a_);<br />        if a[i mod s] > mx then mx := a[i mod s]; <br />        if a_ + mx > m then m := a_ + mx; <br />        a[i mod s] : = a_ <br />    end;<br />    writeln(m) <br />end.
0 из 0
Ваш ответ Правильный ответ Первичный балл

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

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