Глоссарий :
- ВС (выигрышная стратегия) - Будем говорить, что игрок имеет выигрышную стратегию (ВС),
если он может выиграть при любых ходах противника за конечное число шагов
- Вершина/позиция - начальная, промежуточное или финальное состояние игры. Из начальных и промежуточных позиций
игроки могут делать ходы. Из финальных состояний делать ходы нельзя. Достижение финальной позиции означает окончание игры.
Для финальных вершин введем обозначения:
- Win (W)- выигрышная позиция. Игрок, достигший вершины "Win"Б считается победителем
- Lose (L) - проигрышная позиция. Игрок, попавший в вершины "Lose", считается проигравшим.
Победителем объявляется его соперник
- Ход игрока - переход из одной позиции в другую по определенным правилам. Ход игрока можно считать ориентированным ребром в графе.
- Раскраска вершины - Если, при начале игры из данной вершины, у одного из игроков есть ВС (выигрышная стратегия),
то считается, что вершина может быть раскрашена в "цвета" этого игрока.
- Раскрасить вершину - значит определить, в цвета какого из игроков она может быть раскрашена.
- Граф игры - двудольный, ориентированный, невзвешанный, ациклический граф, в котором:
Описание игры:
Два игрока, Петя и Ваня, играют в игру с одной кучей камней.
Игра организована по следующим правилам:
- Игроки ходя поочередно. Первый ход всегда делает Петя;
- Каждый ход игрок может увеличить количество камней в куче одим из перечисленных способов:
- на a камней;
- на b камней;
- ровно на 50% процентов, если это возможно;
- в d раз;
- Игра завершается когда количество камней в куче становится не менее N.
При этом считается, что игрок сделал ход в вершину/позицию "Win".
- Победителем объявляется игрок, достигший вершины/позиции "Win" (сделавшй последний/победный ход)
- В начальный момент времени в куче может находиться S камней ( 1 ≤ S ≤ N-1)
- Гарантируется, что для любой стартовой позиции есть игрок (Петя или Ваня) у которого существует выигрышная стратегия.
.
Задание: По описанию игры построить "граф игры". Определить следующие характеристики построенного графа:
- Количество вершин, имеющих раскраску в "цвета Пети", сумму степеней этих вершин;
- Список вершин, имеющих раскраску в "цвета Вани", в порядке возрастания их номеров
- Определить самую длинную (по количеству ходов) траекторию развития игры. Если таких несколько, то вывести "наименьшую в лексико-графическом смысле".
Напишите программу, решающую поставленную задачу.
Входные данные:
Одна строка со значения
N, a, b, d (1 ≤
a, b, N ≤ 1000, 1<
d<100 )
Выходные данные:
1 строка: Количество вершин, имеющих раскраску в "цвета Пети", сумму степеней этих вершин (два числа через пробел);
2 строка: Список вершин, имеющих раскраску в "цвета Вани", в порядке возрастания их номеров (в строку, через пробел)
3 строка: Траектория максимальной длины - последовательность вершин, составляющих тракеторию игры.
Если таких несколько, то вывести "наименьшую в лексико-графическом порядке" (вершины сравниваются как числа)
(в строку, через пробел, последняя вершина должна иметь название "Win" )
Пример
| Входные данные |
Выходные данные |
Пояснения |
| 16 1 3 2 |
11 13
1 3 5 7
1 2 3 4 5 6 7 8 Win |
1 строка ответа:
В "цвета Пети" раскрашены вершины 2,4,6,8-15.
Из вершин 8-15 Петя должен сразу перейти вершину "Win".
Из вершины "6" Петя обязан перейти в вершину "7".
Из вершины "4" Петя, сохраняя ВС может перейти в вершины "4", "7"
Из вершины "2" Петя, сохраняя ВС может перейти в вершины "3", "5"
2 строка ответа:
В "цвета Вани" раскрашены вершины 1,3,5,7
3 строка ответа:
Максимальная траектория игры может содержать 9 вершин (включая вершину "Win").
Таких траекторий три:
1 2 3 4 5 6 7 8 Win
1 2 3 4 5 6 7 10 Win
1 2 3 4 5 6 7 14 Win
в ответе указана наименьшая в лексико-графическом порядке
граф игры |
| 51 3 5 2 |
38 47
1 3 5 7 9 11 13 15 17 23 24 25
1 2 3 6 9 12 15 18 23 26 Win |
|
Рекомендации по решению:
- используя принцип BFS, сделать раскраску вершин.
- построить словарь/список компонентов смежности для "графа игры"
- используя принцип DFS, найти максимальную траекторию.
Поиск траектории можно упростить, если "развернуть" граф игры, то есть изменить в нем направление всех ребер.
Получиться дерево с одним истоком в вершине "Win", в котором используя DFS несложно найти путь максимальной длины.