Зуля

Образоват ельный порт ал «РЕШУ ЕГЭ» (http://информат ика.решуегэ.рф) 31. C 3 № 6201. Два игрока, Паша и Вова, играют в следующую игру. Перед игроками лежит куча кам­

ней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу 1 камень или добавить в кучу 10 камней. Например, имея кучу из 7 камней, за один ход можно по лучит ь кучу из 8 или 17 камней. У каждого игрока, чт обы делат ь ходы, ест ь неограниченное количе­ ст во камней. Игра завершает ся в т от момент , когда количест во камней в куче ст ановит ся не менее 52. Победит елем счит ает ся игрок, сделавший последний ход, т о ест ь первым получивший кучу, в ко т орой будет 52 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 51.

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

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

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

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

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

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

32. C 4 № 5323. По каналу связи передаёт ся последоват ельност ь положит ельных целых чисел Х1, Х2,

... все числа не привышают 1000, их количест во заранее неизвест но. Каждое число передаёт ся в виде от дельной т екст овой ст роки, содержащей десят ичную запись числа. Признаком конца переда­ ваемой последоват ельност и являет ся число 0.

Участ ок последоват ельност и от элемент а ХT до элемент а XT+N называет ся подъёмом, если на

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

1)Т = 1 или ХT-1 > ХT

2)XT+N - последний элемент последоват ельност и или XT+N > XT+T+1. Высот ой подъёма называет ся разност ь XT+N - Х1. Подъём счит ает ся значит ельным, если высот а подъёма больше величины мини­

мального элемент а эт ого подъема.

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

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

Получено чисел: ...

Найдено значительных подъемов: ...

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

Перед т екст ом программы крат ко опишит е алгорит м решения задачи.

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

144

17

21

27

3

7

9

11

25

0

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

Получено чисел: 9 Найдено значит ельных подъемов: 1