Задание 26. Умение обрабатывать целочисленную информацию с использованием сортировки: все задания

Ответом к заданию по информатике может быть целое число, десятичная дробь (записывайте её через запятую, вот так: 2,5), последовательность цифр или букв (пишите без пробелов: 97531).

Версия для печати

1. Задание#T30262

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

За один ход из позиции

можно получить любую из четырёх позиций:

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

В начальный момент в первой куче было камней, во второй куче – камней,

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

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

Задание 1.

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

Задание 2.

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

Задание 3.

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

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

Показать разбор

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

(допускаются иные формулировки ответа, не искажающие его смысла)

Задание 1.

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

Задание 2.

Возможные значения :

В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако при

Петя может получить позицию

а при

– позицию

В первом случае после хода Вани возникнет одна из позиций

во втором случае – одна из позиций

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

Задание 3.

Возможное значение : После первого хода Пети возможны позиции

В позициях

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

Ваня может получить позицию

разобранную в задании Игрок, после хода которого возникла эта позиция (в данном случае – Ваня), выигрывает следующим ходом.

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

Рис. 1. Граф всех партий, возможных при описанной стратегии Вани. Ходы Пети показаны сплошными стрелками, ходы Вани – пунктирными стрелками. Заключительные позиции обозначены прямоугольниками.

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

Указания по оцениванию

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

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

Задание 1 выполнено, если выполнены оба пункта: для пункта А перечислены все удовлетворяющие условию значения и только они; для пункта Б указано верное значение и только оно. Обоснование найденных значений не обязательно.

Задание 2 выполнено, если верно указана выигрышная для Пети позиция (любая из двух возможных) и описана соответствующая стратегия.

Задание 3 выполнено, если правильно указана выигрышная для Вани позиция и построено дерево всех возможных при выигрышной стратегии партий (и только их).

Во всех случаях стратегии могут быть описаны так, как это сделано в примере решения, или другим способом.

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 3 тыс. раз. С ним справились 79% пользователей.

2. Задание#T30179

За один ход из позиции

можно получить любую из четырёх позиций:

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

В начальный момент в первой куче было камней, во второй куче – камней,

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

Задание 1.

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

Задание 2.

Задание 3.

Показать разбор

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

(допускаются иные формулировки ответа, не искажающие его смысла)

Задание 1.

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

Задание 2.

Возможные значения :

В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако при

Петя может получить позицию

а при

– позицию

В первом случае после хода Вани возникнет одна из позиций

во втором случае – одна из позиций

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

Задание 3.

Возможное значение : После первого хода Пети возможны позиции

В позициях

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

Ваня может получить позицию

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

Указания по оцениванию

Во всех случаях стратегии могут быть описаны так, как это сделано в примере решения, или другим способом.

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 2 тыс. раз. С ним справились 80% пользователей.

3. Задание#T29799

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

За один ход из позиции

можно получить любую из четырёх позиций:

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

В начальный момент в первой куче было 16 камней, во второй куче – камней,

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

Задание 1.

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

Задание 2.

Задание 3.

Показать разбор

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

(допускаются иные формулировки ответа, не искажающие его смысла)

Задание 1.

Петя может выиграть первым ходом, если

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

Задание 2.

Возможные значения :

В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако при

Петя может получить позицию

а при

– позицию

В первом случае после хода Вани возникнет одна из позиций

во втором случае – одна из позиций

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

Задание 3.

Возможное значение : После первого хода Пети возможны позиции

В позициях

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

Ваня может получить позицию

Рис. 1. Граф всех партий, возможных при описанной стратегии Вани. Ходы Пети показаны сплошными стрелками, ходы Вани показаны пунктирными стрелками. Заключительные позиции обозначены прямоугольниками.

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

Указания по оцениванию

Задание 1 выполнено, если перечислены все удовлетворяющие условию значения и только они. Обоснование найденных значений не обязательно.

Во всех случаях стратегии могут быть описаны так, как это сделано в примере решения, или другим способом

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 1 тыс. раз. С ним справились 83% пользователей.

4. Задание#T29770

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

За один ход из позиции

можно получить любую из четырёх позиций:

Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

В начальный момент в первой куче было камней, во второй куче – камней,

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

Задание 1.

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

Задание 2.

Задание 3.

Показать разбор

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

(допускаются иные формулировки ответа, не искажающие его смысла)

Задание 1.

Петя может выиграть первым ходом, если

Задание 2.

Возможные значения :

В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако при

Петя может получить позицию

а при

– позицию

В первом случае после хода Вани возникнет одна из позиций

во втором случае – одна из позиций

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

Задание 3.

Возможное значение : После первого хода Пети возможны позиции

В позициях

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

Ваня может получить позицию

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

Указания по оцениванию

Во всех случаях стратегии могут быть описаны так, как это сделано в примере решения, или другим способом

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 1 тыс. раз. С ним справились 80% пользователей.

5. Задание#T9822

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

. Тогда за один ход можно получить любую из четырёх позиций:

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

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

В начальный момент в первой куче было пять камней, во второй куче – камней;

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

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

Задание 1

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

Задание 2

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

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

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

Задание 3

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

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

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

Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы).

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

Показать разбор

Содержание верного ответа и указания по оцениванию
(допускаются иные формулировки ответа, не искажающие его смысла).

Задание 1

Петя может выиграть своим любым ходом при .
.

Задание 2

Возможное значение

Задание 3

Возможное значение

Указания по оцениванию

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

Это задание составил Дмитрий Богданов специально для Яндекса

Это задание решали 7 тыс. раз. С ним справились 18% пользователей.

6. Задание#T9807

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

Тогда за один ход можно получить любую из четырёх позиций:

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

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

В начальный момент в первой куче было камней, во второй куче – камней;

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

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

Задание 1

Укажите все такие значения числа при которых Петя может выиграть за один ход.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение когда такая ситуация возможна.

Задание 2

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

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

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

Задание 3

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

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

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

Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы).

Показать разбор

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

(допускаются иные формулировки ответа, не искажающие его смысла)

Задание 1

Петя может выиграть при

Задание 2

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

После хода Вани может возникнуть одна из четырёх позиций:

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

Замечание для проверяющего. Ещё одно возможное значение для этого задания – число В этом случае Петя первым ходом должен утроить количество камней в меньшей куче и получить позицию

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

Задание 3

Возможное значение После первого хода Пети возможны позиции:

В позициях

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

Ваня может получить позицию

Эта позиция разобрана в п. Игрок, который её получил (теперь это Ваня), выигрывает своим вторым ходом.

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

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

Рис. Дерево всех партий, возможных при Ваниной стратегии. Ходы Пети показаны пунктиром; ходы Вани – сплошными линиями. Прямоугольником обозначены позиции, в которых партия заканчивается.

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

Указания по оцениванию

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

Задание выполнено, если выполнены оба пункта: а) и б), т.е. для п. а) перечислены все значения удовлетворяющие условию (и только они), для п. б) указано верное значение (и только оно).

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

Задание выполнено, если правильно указана позиция, выигрышная для Вани, и построено дерево всех возможных при Ваниной стратегии партий (и только их).

Во всех случаях стратегии могут быть описаны так, как это сделано в примере решения, или другим способом.

Это задание взято из демовариантов ФИПИ 2018-2020

Это задание решали 6 тыс. раз. С ним справились 25% пользователей.

7. Задание#T8657

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

Пример. Заданный набор слов: {АНТАРКТИДА, АНТРАЦИТ, АБАРА, АБАЖУР, БББ, БАОБАБ, БАР}. Первым ходом Петя пишет Б (он мог написать Б или А). Вова в ответ дописывает А и получает БА (он мог ещё получить ББ). Вторым ходом Петя получает БАР и выигрывает.

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

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

Задание 1

Укажите, у кого есть выигрышная стратегия при исходном наборе слов {ГДЕЖЗИКЛ, КЛМНБВГ}. Опишите эту стратегию.
Укажите, у кого есть выигрышная стратегия при исходном наборе слов {ДВАДВА…ДВА, ПОРАПОРА…ПОРА} (в первом слове ДВА повторено раза, т.е. его длина букв; во втором слове ПОРА повторено раза, т.е. его длина букв). Опишите эту стратегию.

Задание 2

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

Задание 3

Рассмотрим набор слов {СТОЛ, СТОЛЕТИЕ, СПОРТ, КОЛЕСО, КОЛБА, КАК}. У кого из игроков есть выигрышная стратегия для этого набора? Приведите в виде рисунка или таблицы дерево всех партий, возможных при этой стратегии.

Показать разбор

Содержание верного ответа и указания по оцениванию

(допускаются иные формулировки ответа, не искажающие его смысла)

Общая идея решения

Если в наборе только одно слово, то все ходы игроков единственно возможные. Если длина слова нечётная, то выигрывает Петя; если длина чётная – Вова.

Аналогично, пусть для некоторого слова существует единственная возможность продолжить его до слова из набора. Если длина продолжения нечётная, то выигрывает тот игрок, который ходит; если длина чётная, выигрывает его противник.

Задание 1

Выигрышная стратегия есть у Пети. Первым ходом он пишет К. В конце игры у игроков должно получиться слово КЛМНБВГ. Длина слова равна (нечетная), поэтому последнюю букву напишет Петя.
Выигрышная стратегия есть у Пети. Первым ходом он пишет Д. После этого у игроков должно получиться слово ДВАДВА...ДВА. В этом слове букв. Петя напишет -ю, -ю, -ю и т.д. буквы. Поэтому -ю букву напишет Петя, и, следовательно, выиграет Петя.

Задание 2

Нужно в слове КЛМНБВГ поставить на первое место букву Г. Например, можно поменять местами первую и последнюю буквы; получится слово ГЛМНБВК.

Полученный набор слов: {ГДЕЖЗИКЛ, ГЛМНБВК}. Теперь оба слова начинаются с буквы Г, и Петя должен написать Г. Вова пишет Д, получается ГД. Теперь в конце игры получится слово ГДЕЖЗИКЛ. Длина слова – букв. Поэтому выиграет Вова.

Задание 3

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

Указания по оцениванию

Предварительные замечания

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

Пункты 1А и 1Б считаются выполненным, если (I) правильно указано, кто из игроков имеет выигрышную стратегию в на данном наборе, и (II) описаны выигрышные стратегии – так, как это сделано в образце решения, или любым другим способом (таблица, словесно и т.д.).

Первое задание считается выполненным полностью, если выполнены полностью оба пункта: 1А и 1Б.

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

Задание 2 считается выполненным, если описана выигрышная стратегия Вовы.

Задание 3 считается выполненным, если правильно построено дерево всех возможных партий для выигрышной стратегии Вовы.

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

Это задание решали 3 тыс. раз. С ним справились 16% пользователей.

8. Задание#T4918

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

. За один ход из позиции

можно получить любую из четырёх позиций:

. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

В начальный момент в первой куче было камней, во второй куче – камней,

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

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

Задание 1.

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

Задание 2.

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

Задание 3.

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

Показать разбор

Содержание верного ответа
(допускаются иные формулировки ответа, не искажающие его смысла)

Задание 1.

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

Задание 2.

Возможные значения : , . В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако при

Петя может получить позицию

, а при

позицию

В первом случае после хода Вани возникнет одна из позиций

, во втором случае – одна из позиций

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

Задание 3.

Возможное значение : . После первого хода Пети возможны позиции

. В позициях

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

Ваня может получить позицию

, разобранную в задании . Игрок, после хода которого возникла эта позиция (в данном случае – Ваня), выигрывает следующим ходом.

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

На рисунке эти же партии показаны в виде графа (оба способа изображения допустимы).

Рис. . Граф всех партий, возможных при описанной стратегии Вани.

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

Указания по оцениванию	Баллы
В задаче от ученика требуется выполнить три задания. Количество баллов в целом соответствует количеству выполненных заданий (подробнее см. ниже). Ошибка в решении, не искажающая основного замысла и не приведшая к неверному ответу, например, арифметическая ошибка при вычислении количества камней в заключительной позиции, при оценке решения не учитывается. Задание выполнено, если выполнены оба пункта: для пункта А перечислены все удовлетворяющие условию значения (и только они), для пункта Б указано верное значение (и только оно). Обоснование найденных значений не обязательно. Задание выполнено, если верно указана выигрышная для Пети позиция (любая из двух возможных) и описана соответствующая стратегия. Задание выполнено, если правильно указана выигрышная для Вани позиция и построено дерево всех возможных при выигрышной стратегии партий (и только их). Во всех случаях стратегии могут быть описаны так, как это сделано в примере решения, или другим способом
Выполнены все три задания
Не выполнены условия, позволяющие поставить балла, и выполнено хотя бы одно из следующих условий. – Выполнено задание . – Выполнены задания и
Не выполнены условия, позволяющие поставить или балла, и выполнено хотя бы одно из заданий и
Не выполнено ни одно из условий, позволяющих поставить , или балла
Максимальный балл

Это задание составили эксперты «СтатГрада» для Яндекса

9. Задание#T4891

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

. За один ход из позиции

можно получить любую из четырёх позиций:

. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

В начальный момент в первой куче было камней, во второй куче – камней,

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

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

Задание 1.

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

Задание 2.

Задание 3.

Показать разбор

Содержание верного ответа
(допускаются иные формулировки ответа, не искажающие его смысла)

Задание 1.

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

Задание 2.

Возможные значения : , . В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако при

Петя может получить позицию

, а при

позицию

В первом случае после хода Вани возникнет одна из позиций

, во втором случае – одна из позиций

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

Задание 3.

Возможное значение : . После первого хода Пети возможны позиции

. В позициях

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

Ваня может получить позицию

На рисунке эти же партии показаны в виде графа (оба способа изображения допустимы).

Рис. . Граф всех партий, возможных при описанной стратегии Вани.

Указания по оцениванию	Баллы
В задаче от ученика требуется выполнить три задания. Количество баллов в целом соответствует количеству выполненных заданий (подробнее см. ниже). Ошибка в решении, не искажающая основного замысла и не приведшая к неверному ответу, например, арифметическая ошибка при вычислении количества камней в заключительной позиции, при оценке решения не учитывается. Задание выполнено, если выполнены оба пункта: для пункта А перечислены все удовлетворяющие условию значения (и только они), для пункта Б указано верное значение (и только оно). Обоснование найденных значений не обязательно. Задание выполнено, если верно указана выигрышная для Пети позиция (любая из двух возможных) и описана соответствующая стратегия. Задание выполнено, если правильно указана выигрышная для Вани позиция и построено дерево всех возможных при выигрышной стратегии партий (и только их). Во всех случаях стратегии могут быть описаны так, как это сделано в примере решения, или другим способом
Выполнены все три задания
Не выполнены условия, позволяющие поставить балла, и выполнено хотя бы одно из следующих условий. – Выполнено задание . – Выполнены задания и
Не выполнены условия, позволяющие поставить или балла, и выполнено хотя бы одно из заданий и
Не выполнено ни одно из условий, позволяющих поставить , или балла
Максимальный балл

Это задание составили эксперты «СтатГрада» для Яндекса

10. Задание#T4864

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

. За один ход из позиции

можно получить любую из четырёх позиций:

. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

В начальный момент в первой куче было камней, во второй куче – камней,

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

Задание 1.

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

Задание 2.

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

Задание 3.

Показать разбор

Содержание верного ответа
(допускаются иные формулировки ответа, не искажающие его смысла)

Задание 1.

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

Задание 2.

Возможные значения : , . В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако при

Петя может получить позицию

, а при

– позицию

В первом случае после хода Вани возникнет одна из позиций

, во втором случае – одна из позиций

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

Задание 3.

Возможное значение : . После первого хода Пети возможны позиции

. В позициях

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

Ваня может получить позицию

На рисунке эти же партии показаны в виде графа (оба способа изображения допустимы).

Рис. . Граф всех партий, возможных при описанной стратегии Вани.

Указания по оцениванию	Баллы
В задаче от ученика требуется выполнить три задания. Количество баллов в целом соответствует количеству выполненных заданий (подробнее см. ниже). Ошибка в решении, не искажающая основного замысла и не приведшая к неверному ответу, например, арифметическая ошибка при вычислении количества камней в заключительной позиции, при оценке решения не учитывается. Задание выполнено, если выполнены оба пункта: для пункта А перечислены все удовлетворяющие условию значения (и только они), для пункта Б указано верное значение (и только оно). Обоснование найденных значений не обязательно. Задание выполнено, если верно указана выигрышная для Пети позиция (любая из двух возможных) и описана соответствующая стратегия. Задание выполнено, если правильно указана выигрышная для Вани позиция и построено дерево всех возможных при выигрышной стратегии партий (и только их).Во всех случаях стратегии могут быть описаны так, как это сделано в примере решения, или другим способом.
Выполнены все три задания.
Не выполнены условия, позволяющие поставить балла, и выполнено хотя бы одно из следующих условий. – Выполнено задание . – Выполнены задания и .
Не выполнены условия, позволяющие поставить или балла, и выполнено хотя бы одно из заданий и .
Не выполнено ни одно из условий, позволяющих поставить , или балла.
Максимальный балл

Это задание составили эксперты «СтатГрада» для Яндекса

11. Задание#T4837

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

. За один ход из позиции

можно получить любую из четырёх позиций:

. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

В начальный момент в первой куче было камней, во второй куче – камней,

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

Задание 1.

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

Задание 2.

Задание 3.

Показать разбор

Содержание верного ответа
(допускаются иные формулировки ответа, не искажающие его смысла)

Задание 1.

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

Задание 2.

Возможные значения : , . В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако при

Петя может получить позицию

, а при

– позицию

В первом случае после хода Вани возникнет одна из позиций

, во втором случае – одна из позиций

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

Задание 3.

Возможное значение : . После первого хода Пети возможны позиции

. В позициях

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

Ваня может получить позицию

На рисунке эти же партии показаны в виде графа (оба способа изображения допустимы).

Рис. . Граф всех партий, возможных при описанной стратегии Вани.

Указания по оцениванию	Баллы
В задаче от ученика требуется выполнить три задания. Количество баллов в целом соответствует количеству выполненных заданий (подробнее см. ниже). Ошибка в решении, не искажающая основного замысла и не приведшая к неверному ответу, например, арифметическая ошибка при вычислении количества камней в заключительной позиции, при оценке решения не учитывается. Задание выполнено, если выполнены оба пункта: для пункта А перечислены все удовлетворяющие условию значения (и только они), для пункта Б указано верное значение (и только оно). Обоснование найденных значений не обязательно. Задание выполнено, если верно указана выигрышная для Пети позиция (любая из двух возможных) и описана соответствующая стратегия. Задание выполнено, если правильно указана выигрышная для Вани позиция и построено дерево всех возможных при выигрышной стратегии партий (и только их). Во всех случаях стратегии могут быть описаны так, как это сделано в примере решения, или другим способом.
Выполнены все три задания.
Не выполнены условия, позволяющие поставить балла, и выполнено хотя бы одно из следующих условий. – Выполнено задание . – Выполнены задания и .
Не выполнены условия, позволяющие поставить или балла, и выполнено хотя бы одно из заданий и .
Не выполнено ни одно из условий, позволяющих поставить , или балла.
Максимальный балл

Это задание составили эксперты «СтатГрада» для Яндекса

12. Задание#T1932

. Тогда за один ход можно получить любую из четырёх позиций:

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

В начальный момент в первой куче было шесть камней, во второй куче – камней;

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

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

Задание 1

Укажите все такие значения числа , при которых Петя может выиграть за один ход.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение , когда такая ситуация возможна.

Задание 2

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

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

Задание 3

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

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

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

Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы).

Показать разбор

Задание 1

Петя может выиграть при .
.

Задание 2

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

. После хода Вани может возникнуть одна из четырёх позиций:

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

Замечание для проверяющего. Ещё одно возможное значение для этого задания – число . В этом случае Петя первым ходом должен утроить количество камней в меньшей куче и получить позицию

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

Задание 3

Возможное значение : . После первого хода Пети возможны позиции:

. В позициях

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

Ваня может получить позицию

. Эта позиция разобрана в п. . Игрок, который её получил (теперь это Ваня), выигрывает своим вторым ходом.

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

Рис. . Дерево всех партий, возможных при Ваниной стратегии. Ходы Пети показаны пунктиром; ходы Вани – сплошными линиями. Прямоугольником обозначены позиции, в которых партия заканчивается.

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

В соответствии с Порядком проведения государственной итоговой аттестации по образовательным программам среднего общего образования (приказ Минобрнауки России от

, зарегистрирован Минюстом России

)

«61. По результатам первой и второй проверок эксперты независимо друг от друга выставляют баллы за каждый ответ на задания экзаменационной работы ЕГЭ с развёрнутым ответом...

62. В случае существенного расхождения в баллах, выставленных двумя экспертами, назначается третья проверка. Существенное расхождение в баллах определено в критериях оценивания по соответствующему учебному предмету. Эксперту, осуществляющему третью проверку, предоставляется информация о баллах, выставленных экспертами, ранее проверявшими экзаменационную работу».

Существенным считается расхождение в или более балла за выполнение любого из заданий

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

Это задание взято из демовариантов ФИПИ 2018-2020

0 баллов сегодня

дней без пропуска

ср

чт

пт

сб

вс

пн

вт