Вопрос № 1046082 - Информатика

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

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

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

Выполните задание и сравните с предлагаемым решением.

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

Выполните задание и сравните с предлагаемым решением.

[Демовариант ФИПИ, 2006.]

У исполнителя Утроитель две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 3.
Первая из них увеличивает число на экране на 1, вторая – утраивает его.
Программа для Утроителя – это последовательность команд.
Сколько есть программ, которые число 1 преобразуют в число 29?

Задан алгоритм преобразования некоторой последовательности символов, на каждом шаге которого выполняются следующие операции:
1) в конец последовательности, имеющейся перед выполнением шага, дописывается ее копия, развернутая зеркально (символы записываются в обратном порядке);
2) в конце получившейся последовательности удаляется количество символов, равное номеру шага выполнения алгоритма.
Для входной последовательности символов 1234 приведены результаты выполнения первых двух шагов алгоритма:
1: 1234432
2: 123443223443
Для входной последовательности символов ALGORITM после 10-го шага преобразования на позиции 1024 будет находиться символ …

Sequence A[n] of natural numbers from 1 to M is ordered ascending the maximum number obtained from binary representation of a sequence member under cyclic shift preserving the number of digits (the larger umber has the larger ordinal number  for two equal maximum numbers). For example the binary representation for the number 19 will be 10011. The options obtained after cyclic shift will have the following representation:
.
And the maximum number is 28. Thus the sequencing key for number 19 will be 28, the sequencing key for the number say, 1025 will be 1536, etc.
For M=2000 in the position with ordinal number 1234 of the ordered sequence there is the following cardinal number …

A musical composition lasting 5 minutes 20 seconds was digitized with the 24 bit transformation and 44.1 kilohertz frequency. Further the file was converted by decreasing the discretization interval by two times and the number of  discretization levels by 16711680. Thus to transfer the transformed file through the communication line with the declared transfer speed of 7000 kbps it takes _____ seconds.
Give your answer rounding it to two digits after the decimal point.