№№ заданий Пояснения Ответы Ключ Добавить инструкцию Критерии
Источник Раздел кодификатора ФИПИ Справка
PDF-версия PDF-версия (вертикальная) PDF-версия (крупный шрифт) PDF-версия (с большим полем) Версия для копирования в MS Word
Вариант № 4871420

1.

Дано А = A716, B = 2518. Найдите сумму A + B. Ответ укажите в двоичной системе.

2.

Ло­ги­че­ская функ­ция F задаётся вы­ра­же­ни­ем z ∧ ¬y ∧ (w → x). На ри­сун­ке при­ведён фраг­мент таб­ли­цы ис­тин­но­сти функ­ции F, со­дер­жа­щий все на­бо­ры ар­гу­мен­тов, при ко­то­рых функ­ция F ис­тин­на.

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

 

Пе­ре­мен­ная 1Пе­ре­мен­ная 2Пе­ре­мен­ная 3Пе­ре­мен­ная 4Функ­ция
????????????F
10001
10101
10111

 

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

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

 

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

 

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

3.

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

 

П1П2П3П4П5П6П7П8
П1152018
П21525
П3252422
П42012
П5131617
П6241315
П71216
П818221715

 

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

4.

Ниже приведены фрагменты таблиц базы данных канцелярского магазина:

 

 Изделие  Артикул 
 Авторучка 
 1948 
 Фломастер 
 2537 
 Карандаш 
 3647 
 Фломастер 
 4758 
 Авторучка 
 5748 
 Карандаш 
 8457 

 Артикул  Размер  Цвет  Цена 
 8457 
 маленький  красный 
 5 
 2537 
 большой  синий 
 9 
 5748 
 большой  синий 
 8 
 3647 
 большой  синий 
 8 
 4758 
 маленький  зелёный 
 5 
 3647 
 большой  зелёный 
 9 
 1948 
 маленький  синий 
 6 
 3647 
 большой  красный 
 8 
 1948 
 маленький  красный 
 6 

 

Сколько разных карандашей продаётся в магазине?

5.

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко шесть букв: А, B, C, D, E, F. Для пе­ре­да­чи ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Для букв A, B, C ис­поль­зу­ют­ся такие ко­до­вые слова: А – 11, B – 101, C – 0. Ка­ко­ва наи­мень­шая воз­мож­ная сум­мар­ная длина всех ко­до­вых слов?

 

При­ме­ча­ние. Усло­вие Фано озна­ча­ет, что ни одно ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова. Коды, удо­вле­тво­ря­ю­щие усло­вию Фано, до­пус­ка­ют од­но­знач­ное де­ко­ди­ро­ва­ние.

6.

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

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

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

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

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

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

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

7.

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

 

ТЦЯн­варьФев­ральМартАп­рель
Про­да­но,
штук
Цена,
руб.
Про­да­но,
штук
Цена,
руб.
Про­да­но,
штук
Цена,
руб.
Про­да­но,
штук
Цена,
руб.
Эдель­вейс514117515415
По­ку­поч­ка613216611414
Ко­ше­лек217514415118
Сол­неч­ный812713711713
 Про­да­но всего 21152216
 Сред­няя цена 14151315

 

Из­вест­но, что весь по­сту­пив­ший от по­став­щи­ка в те­ку­щем ме­ся­це товар ре­а­ли­зу­ет­ся в этом же ме­ся­це.

В каком ме­ся­це вы­руч­ка по­став­щи­ка дан­но­го то­ва­ра была мак­си­маль­на?

8.

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

 

 

Бей­сикPython

DIM N, S AS INTEGER

N = 1

S = 0

WHILE N <= 101

    S = S + 7

    N = N + 1

WEND

PRINT S

n = 1

s = 0

while n <= 101:

    s += 7

    n += 1

print(s)

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

var n, s: integer;

begin

    n := 1;

    s := 0;

    while n <= 101 do

    begin

        s := s + 7;

        n := n + 1;

    end;

    writeln(s);

end.

алг

нач

    цел n, s

    n := 1

    s := 0

    нц пока n <= 101

        s := s + 7

        n := n + 1

    кц

    вывод s

кон

Си++

#include <iostream>

using namespace std;

int main() {

    int n, s;

    n = 1, s = 0;

    while (n <= 101) {

        s = s + 7;

        n = n + 1;

    }

    cout << s << endl;

    return 0;

}

 

9.

Стереоаудиофайл передается со скоростью 32 000 бит/с. Файл был записан при среднем качестве звука: глубина кодирования – 16 бит, частота дискретизации – 48 000 измерений в секунду, время записи ─ 90 сек.Сколько времени будет передаваться файл? Время укажите в секундах.

10.

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

 

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

 

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

11.

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

 

Бей­сикPython

SUB F(n)

  IF n > 0 THEN

    PRINT "*"

    F(n - 1)

    F(n \ 3)

  END IF

END SUB

def F(n):

    if n > 0:

        print("*")

        F(n - 1)

        F(n // 3)

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

алг F(цел n)

нач

  если n > 0 то

    вывод "*"

    F(n - 1)

    F(div(n, 3))

  все

кон

procedure F(n: integer);

begin

  if n > 0 then

  begin

    writeln('*');

    F(n - 1);

    F(n div 3)

  end

end

Си

void F(int n)

{

  if (n > 0)

  {

    printf("*");

    F(n - 1);

    F(n / 3);

  }

}

 

 

Сколь­ко сим­во­лов «звёздоч­ка» будет на­пе­ча­та­но на экра­не при вы­пол­не­нии вы­зо­ва F(6)?

12.

В тер­ми­но­ло­гии сетей TCP/IP мас­кой под­се­ти на­зы­ва­ет­ся 32-раз­ряд­ное дво­ич­ное число, опре­де­ля­ю­щее, какие имен­но раз­ря­ды IP-ад­ре­са ком­пью­те­ра яв­ля­ют­ся об­щи­ми для всей под­се­ти - в этих раз­ря­дах маски стоит 1. Обыч­но маски за­пи­сы­ва­ют­ся в виде чет­вер­ки де­ся­тич­ных чисел - по тем же пра­ви­лам, что и IP-ад­ре­са. Для не­ко­то­рой под­се­ти ис­поль­зу­ет­ся маска 255.255.255.192. Сколь­ко раз­лич­ных ад­ре­сов ком­пью­те­ров тео­ре­ти­че­ски до­пус­ка­ет эта маска, если два ад­ре­са (адрес сети и ши­ро­ко­ве­ща­тель­ный) не ис­поль­зу­ют?

13.

При ре­ги­стра­ции в ком­пью­тер­ной си­сте­ме каж­до­му поль­зо­ва­те­лю выдаётся па­роль, со­сто­я­щий из 11 сим­во­лов и со­дер­жа­щий толь­ко сим­во­лы А, Б, В, Г, Д, Е. Каж­дый такой па­роль в ком­пью­тер­ной про­грам­ме за­пи­сы­ва­ет­ся ми­ни­маль­но воз­мож­ным и оди­на­ко­вым целым ко­ли­че­ством байт, при этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние и все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством бит. Опре­де­ли­те, сколь­ко байт не­об­хо­ди­мо для хра­не­ния 20 па­ро­лей.

14.

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

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

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

заменить (111, 27)

преобразует строку 05111150 в строку 0527150.

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

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

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

 

Цикл

ПОКА условие

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

КОНЕЦ ПОКА

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

 

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 77 единиц?

 

НАЧАЛО

    ПОКА нашлось (11111)

        заменить (222, 1)

        заменить (111, 2)

    КОНЕЦ ПОКА

КОНЕЦ

15.

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

16.

В какой системе счисления выполняется равенство 12 · 13 = 222?

В ответе укажите число – основание системы счисления.

17.

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

 

ЗапросНайдено страниц, тыс.
Новосибирск & (Красноярск & Хабаровск | Норильск)570
Новосибирск & Норильск214
Новосибирск & Красноярск & Хабаровск & Норильск68

 

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

 

Новосибирск & Красноярск & Хабаровск?

 

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

18.

Эле­мен­та­ми мно­жеств А, P, Q яв­ля­ют­ся на­ту­раль­ные числа, причём P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}, Q = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}. Из­вест­но, что вы­ра­же­ние

 

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

 

ис­тин­но (то есть при­ни­ма­ет зна­че­ние 1) при любом зна­че­нии пе­ре­мен­ной х. Опре­де­ли­те наи­боль­шее воз­мож­ное ко­ли­че­ство эле­мен­тов в мно­же­стве A.

19.

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

 

Бей­сикPython

FOR n = 1 TO 6

    FOR m = 1 TO 6

        A(n,m) = A(m,n)+2*n-m

    NEXT m

NEXT n

for n in range(1, 7):

    for m in range(1, 7):

        A[n,m] = A[m,n]+2*n-m

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

for n:= 1 to 6 do

    for m:=1 to 6 do begin

        A[n,m]:= A[m,n]+2*n-m;

    end;

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

    нц для m от 1 до 6

        A[n,m]:= A[m,n]+2*n-m

    кц

кц

Си++

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

    for (m = 1; m <= 6; m++) {

        A[n][m]= A[m][n]+2*n-m;

    }

}

 

 

До вы­пол­не­ния дан­но­го фраг­мен­та про­грам­мы зна­че­ние A[4,3] было равно 10, а зна­че­ние A[3,4] было равно 15. Чему будет равно зна­че­ние A[4,3] после вы­пол­не­ния этого фраг­мен­та про­грам­мы?

20.

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

 

БейсикPython

DIM X, L, M AS INTEGER

INPUT X

L = 2*X-30

M = 2*X+30

WHILE L <> M

  IF L > M THEN

    L = L - M

  ELSE

    M = M - L

  END IF

WEND

PRINT M

x = int(input())

L = 2*x-30

M = 2*x+30

while L != M:

  if L > M:

    L = L - M

  else:

    M = M - L

print(M)

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

var x, L, M: integer;

begin

  readln(x);

  L := 2*x-30;

  M := 2*x+30;

  while L <> M do begin

    if L > M then

      L := L - M

    else

      M := M - L;

  end;

  writeln(M);

end.

алг

нач

    цел x, L, M

    ввод x

    L := 2*x-30

    M := 2*x+30

    нц пока L <> M

      если L > M

        то

          L := L - M

        иначе

          M := M - L

      все

    кц

    вывод M

кон

Си++

#include <iostream>

using namespace std;

int main()

{

    int x, L, M;

    cin >> x;

    L = 2*x-30;

    M = 2*x+30;

    while (L != M) {

      if (L > M)

        L = L - M;

      else

        M = M - L;

    }

    cout « M « endl;

    return 0;

}

 

21.

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

 

 

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

DIM A, B, T, M, R AS INTEGER

A =-20: B = 20

M = A: R = F(А)

FOR T = A TO B

    IF F(T) < R THEN

        M = T

        R = F(T)

    END IF

NEXT T

PRINT R

FUNCTION F(x)

    F = 9*(x-15)*(x+17)+2

END FUNCTION

var a,b,t,M,R: integer;

    Function F(x:integer): integer;

        begin

            F := 9*(x-15)*(x+17)+2

        end;

begin

    a :=-20; b := 20;

    M := a; R := F(a);

    for t := a to b do begin

        if (F(t) < R) then begin

            M := t;

            R := F(t)

        end

    end;

    write(R)

end.

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

#include <iostream>

using namespace std;

int F(int x)

{

return 9*(x-15)*(x+17)+2;

}

int main()

{

    int a, b, t, M, R;

    a =-20; b = 20;

    M = a; R = F(a);

    for (t = a; t <= b; t++) {

        if (F(t) < R) {

            M = t; R = F(t);

        }

    }

    cout « R « endl;

}

алг

нач

цел a, b, t, M, R

a :=-20; b := 20

M := a; R := F(a)

нц для t от a до b

если F(t) < R

то

M := t; R := F(t)

все

кц

вывод R

кон

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

нач

знач := 9*(x-15)*(x+17)+2

кон

Python

def f(x):

    return 9*(x-15)*(x+17)+2

a =-20

b = 20

M = a

R = F(a)

for t in range(a, b+1):

    if (f(t) < R):

        M = t

        R = f(t);

print(R)

 

22.

Ис­пол­ни­тель Вы­чи­та­тель пре­об­ра­зу­ет число, ко­то­рое за­пи­са­но на экра­не. У ис­пол­ни­те­ля Вы­чи­та­тель две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

 

1. Вычти 2

2. Вычти 5

 

Пер­вая из них умень­ша­ет число на экра­не на 2, вто­рая умень­ша­ет его на 5. Про­грам­ма для Вы­чи­та­те­ля – это по­сле­до­ва­тель­ность ко­манд. Сколь­ко есть про­грамм, ко­то­рые число 22 пре­об­ра­зу­ют в число 2?

23.

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4, которые удовлетворяют всем перечисленным ниже условиям?

 

(x1→x2) ∧ (x2→x3) ∧ (x3→x4) = 1

(¬x1 ∧ y1 ∧ z1) ∨ (x1 ∧ ¬y1 ∧ z1) ∨ (x1 ∧ y1 ∧ ¬z1) = 1

(¬x2 ∧ y2 ∧ z2) ∨ (x2 ∧ ¬y2 ∧ z2) ∨ (x2 ∧ y2 ∧ ¬z2) = 1

(¬x3 ∧ y3 ∧ z3) ∨ (x3 ∧ ¬y3 ∧ z3) ∨ (x3 ∧ y3 ∧ ¬z3) = 1

(¬x4 ∧ y4 ∧ z4) ∨ (x4 ∧ ¬y4 ∧ z4) ∨ (x4 ∧ y4 ∧ ¬z4) = 1

 

В ответе не нужно перечислять все различные наборы значений переменных

x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

24.

Дано на­ту­раль­ное число A > 0. Тре­бу­ет­ся вы­ве­сти такое ми­ни­маль­но воз­мож­ное нечётное на­ту­раль­ное число K, при ко­то­ром сумма 1*2 + 3*4 + … + K*(K+1) ока­жет­ся боль­ше A.

Для ре­ше­ния этой за­да­чи уче­ник на­пи­сал про­грам­му, но, к со­жа­ле­нию, его про­грам­ма – не­пра­виль­ная.

Ниже эта про­грам­ма для Ва­ше­го удоб­ства при­ве­де­на на пяти язы­ках про­грам­ми­ро­ва­ния.

 

 

Бей­сикPython

DIM A,S,K AS INTEGER

INPUT A

S = 0

K = 1

WHILE S <= A

    S = S + K*(K+1)

    K = K + 1

WEND

PRINT K

END

a = int(input())

s = 0

k = 1

while s <= a:

    s = s + k*(k+1)

    k = k + 1

print(k)

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

var a, s, k: integer;

begin

    read(a);

    s := 0;

    k := 1;

    while s <= a do begin

        s := s+k*(k+1);

        k := k+1;

    end;

    writeln(k)

end.

алг

нач

    цел a, s, k

    ввод a

    s := 0

    k := 1

    нц пока s <= a

        s := s+k*(k+1)

        k := k+1

    кц

    вывод k

кон

Си++

#include <iostream>

using namespace std;

int main() {

    int a, s, k;

    cin >> a;

    s = 0;

    k = 1;

    while (s <= a) {

        s = s+k*(k+1);

        k = k+1;

    }

    cout « k « endl;

    return 0;

}

 

 

 

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

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

2. Ука­жи­те два наи­мень­ших зна­че­ния A, при ко­то­рых про­грам­ма вы­ве­дет вер­ный ответ.

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

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

25.

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

 

 

БейсикPython

CONST N = 40

DIM A (1 TO N) AS INTEGER

DIM I, J, K AS INTEGER

FOR I = 1 TO N

     INPUT A(I)

NEXT I

     END

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

# использовать две

# целочисленные

# переменные j, k

a = []

n = 40

for i in range(n):

     a.append(int(input()))

...

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

const n = 40;

var

    a: array [0..n-1] of integer;

     i, j, k: integer;

begin

    for i := 0 to n-1 do

        readln(a[i]);

     ...

end.

алг

нач

цел N = 40

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

цел i, j, k

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

ввод a[i]

кц

...

кон

Си++

#include <iostream>

using namespace std;

#define n 40

     int main() {

     int a[n]; int i, j, k;

     for (i = 0; i < n; i++) std::cin >> a[i];

    ...

     return 0;

}

 

26.

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

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

В начальный момент в первой куче было 10 камней, во второй куче — S камней, S > 10.

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

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

Задание 1.

Назовите все значения S, при которых Петя может выиграть первым ходом.

Задание 2.

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

Задание 3.

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

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

27.

На вход про­грам­ме (как ва­ри­ант, из вход­но­го файла text.dat) подаётся текст на ан­глий­ском языке. Ввод этих сим­во­лов за­кан­чи­ва­ет­ся точ­кой (дру­гие сим­во­лы, от­лич­ные от «.» во вход­ных дан­ных от­сут­ству­ют; в про­грам­ме на языке Бей­сик сим­во­лы можно вво­дить по од­но­му в стро­ке, пока не будет вве­де­на точка). Тре­бу­ет­ся на­пи­сать как можно более эф­фек­тив­ную про­грам­му (ука­жи­те ис­поль­зу­е­мую вер­сию языка про­грам­ми­ро­ва­ния, на­при­мер, Borland Pascal 7.0), ко­то­рая будет опре­де­лять и вы­во­дить на экран, какая ан­глий­ская буква встре­ча­ет­ся во вход­ной по­сле­до­ва­тель­но­сти чаще всего и сколь­ко имен­но раз. Строч­ные и про­пис­ные буквы при этом не раз­ли­ча­ют­ся. Если таких букв не­сколь­ко, то про­грам­ма долж­на вы­во­дить на экран ту из них, ко­то­рая стоит по ал­фа­ви­ту рань­ше.

На­при­мер, пусть файл со­дер­жит сле­ду­ю­щую ин­фор­ма­цию:

It is not a simple task. Yes!

Тогда чаще всего встре­ча­ют­ся буквы I, S, T. (слово Yes в под­сче­те не участ­ву­ет, так как рас­по­ло­же­но после точки). Сле­до­ва­тель­но, в дан­ном слу­чае, про­грам­ма долж­на вы­ве­сти

I 3.