Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 6 камней, а в другой 8 камней; такую позицию мы будем обозначать (6, 8). За один ход из позиции (6, 8) можно получить любую из четырёх позиций: (7, 8), (12, 8), (6, 9), (6, 16). Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 55. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 55 или больше камней.
В начальный момент в первой куче было 13 камней, во второй куче – S камней, 1 ≤ S ≤ 41.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по ней игрока, которые не являются для него безусловно выигрышными, то есть не гарантируют выигрыш независимо от игры противника.
Укажите такое значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). В узлах дерева указывайте игровые позиции. Дерево не должно содержать партий, невозможных при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не будет верным ответом на это задание.
St: array[1..3] of string = ('Будапешт', 'Рим', 'Киев');
Nas: array[1..3] of real = (9.9, 61.5, 44.3);
Kr: array[1..3] of string = ('Венгрия', 'Италия', 'Украина');
{Сведения о численности населения приведены по данным ресурса
CountryMeters по состоянию на 03.07.2014}
var
i: integer;
begin
write('Введите 1-Венгрия, 2-Италия, 3-Украина -> ');
readln(i);
if i in [1..3] then
writeln('Страна- ', Kr[i], ', столица- ', St[i], ', население (млн.чел.)- ', Nas[i])
else
writeln('Неверный ввод!')
end.
Тестовое решение:
Введите 1-Венгрия, 2-Италия, 3-Украина -> 2
Страна- Италия, столица- Рим, население (млн.чел.)- 61.5
<символ> ::= <буква> | <знак>
<буква> ::= 'a' | 'b' | 'c' | ... | 'y' | 'z'
<знак> ::= '+' | '-'
<терм> ::= <буква> [ <терм> ]
<операнд> ::= [ <знак> ] <терм>
<строка> ::= <операнд> [ <операнд> ]
Ниже приведена программа на языке Pascal.ABC, реализующая разбор входной строки и её упрощение по правилам приведения подобных членов.
const
n = 30; {максимальное количество операндов, я так захотел!}
pm = ['+', '-']; {символы <знак>}
letter = ['a'..'z'];{символы <буква>}
type
tOper = record
sgn: integer;
vars: string
end;
tM = array[1..n] of tOper;
taSort = array[1..n] of string;{для сортировки}
var
s: string;
l, p: integer;
symb: set of char;
procedure GetSymbol(var c: string);
{
Сканирует строку s с позиции p и возвращает элемент <символ>
Продвигает курсор p к первому необработанному символу строки s
}
var
found: boolean;
begin
found := false;
c := '';
while (p <= l) and (not found) do
begin
if s[p] in symb then begin
found := true;
c := s[p]
end;
p := p + 1
end
end;
procedure Sort(var a: taSort; kol: integer);
{Сортировка вставкой}
var
i, j: integer;
x: string;
flag: boolean;
begin
for i := 2 to kol do
begin
x := a[i];
j := i - 1;
flag := False;
while (j > 0) and (not flag) do
if x < a[j] then
begin
a[j + 1] := a[j];
j := j - 1
end
else flag := True;
a[j + 1] := x
end
end;
function GetSign(c: char): integer;
begin
case c of
'+': Result := 1;
'-': Result := -1;
else Result := 0
end
end;
procedure GetOper(var oper: tOper);
{
Строит элемент <операнд> максимально возможной длины и упорядочивает
составляющие его символы в лексикографическом порядке.
Если операнд построить невозможно, в oper.vars помещается пустая строка.
Процедура обращается к процедурам GetSymbol и Sort.
}
var
i, n: integer;
c, c1: string;
ExitFlag: boolean;
a: taSort;
begin
c := '';
ExitFlag := false;
GetSymbol(c1); {попытаемся получить знак}
if c1[1] in pm then oper.sgn := GetSign(c1[1])
else begin
oper.sgn := 1;
c := c1
end;
repeat
GetSymbol(c1);
if c1 = '' then ExitFlag := true
else if c1[1] in pm then begin
p := p - 1;
ExitFlag := true
end
else
c := c + c1
until ExitFlag;
if c <> '' then
begin
n := Length(c);
for i := 1 to n do a[i] := c[i];
Sort(a, n);
c := '';
for i := 1 to n do c := c + a[i];
oper.vars := c
end
else oper.vars := ''
end;
procedure Add2M(var a: tM; c: tOper; var pn: integer);
{
Ищет среди элементов массива a.vars элемент, совпадающий с с.vars.
При нахождении алгебраически добавляет c.sgn к a[i].sgn, в противном случае
добавляет в массив новый элемент a[i], увеличивая pn на 1.
При вызове pn - количество элементов в массиве.
}
var
i: integer;
c1: string;
found: boolean;
begin
c1 := c.vars;
i := 1;
while (i <= pn) and (not found) do
begin
found := (c1 = a[i].vars);
if found then a[i].sgn := a[i].sgn + c.sgn
else i := i + 1
end;
if not found then begin
a[i].sgn := c.sgn;
a[i].vars := c1;
pn := pn + 1
end
end;
function Convert(k: integer): string;
begin
case k of
-1: Result := '-';
0: Result := '';
1: Result := '+';
else begin
Str( k, Result);
if k > 0 then Result := '+' + Result
end
end
end;
var
c, cz: string;
n1, i: integer;
opr: tOper;
a: tM;
begin
symb := pm + letter;
p := 1;
n1 := 0;
writeln('Введите исходное выражение');
readln(s);
s := LowerCase(s); {перевод символов в нижний регистр}
l := Length(s);
repeat
GetOper(opr);
Add2M(a, opr, n1)
until p > l;
if n1 > 0 then
begin
cz := Convert(a[1].sgn);
if cz = '+' then cz := '';
if cz = '' then c := ''
else c := cz + a[1].vars;
for i := 2 to n1 do
begin
cz := Convert(a[i].sgn);
if cz <> '' then c := c + cz + a[i].vars
end
end
else c := '';
if c='' then c:='0';
if c[1]='+' then c:=copy(c,2,Length(c)-1);
writeln('Результат: ', c)
end.
Тестовое решение:
Введите исходное выражение
abc + a+bca -acb+abc+abc +a
Результат: 3abc+2a
Введите исходное выражение
ab-bca+bc+cba+abc-ba+cba+da+adb+bad-db
Результат: 2abc+bc+ad+2abd-bd