Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежат две кучи кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может до­ба­вить один ка­мень в одну из куч и два камня в дру­гую или же уве­ли­чить ко­ли­че­ство кам­ней в любой куче в два раза. На­при­мер, пусть в одной куче 6 кам­ней, а в дру­гой 8 кам­ней; такую по­зи­цию мы будем обо­зна­чать (6, 8). За один ход из по­зи­ции (6, 8) можно по­лу­чить любую из четырёх по­зи­ций: (7, 10), (8, 9), (12, 8), (6, 16). Чтобы де­лать ходы, у каж­до­го иг­ро­ка есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

В на­чаль­ный мо­мент в пер­вой куче было 8 кам­ней, во вто­рой куче  — S кам­ней, 1 ≤ S ≤ 32.

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

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

За­да­ние 1.

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

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

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

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