Про­грам­мист писал про­грам­му, для опре­де­ле­ния ко­ли­че­ства цифр в целом по­ло­жи­тель­ном числе, не боль­шем 10⁹. Про­грам­мист то­ро­пил­ся, и до­пу­стил ошиб­ку. (Ниже для Ва­ше­го удоб­ства про­грам­ма пред­став­ле­на на четырёх язы­ках про­грам­ми­ро­ва­ния.)

По­сле­до­ва­тель­но вы­пол­ни­те сле­ду­ю­щее.

1.  На­пи­ши­те, что вы­ве­дет эта про­грам­ма при вводе числа 578.

2.  Най­ди­те все ошиб­ки в этой про­грам­ме (их может быть одна или не­сколь­ко). Ука­жи­те все стро­ки (одну или более), со­дер­жа­щие ошиб­ки, и для каж­дой такой стро­ки при­ве­ди­те пра­виль­ный ва­ри­ант. Об­ра­ти­те вни­ма­ние, что тре­бу­ет­ся найти ошиб­ки в име­ю­щей­ся про­грам­ме, а не на­пи­сать свою, воз­мож­но, ис­поль­зу­ю­щую дру­гой ал­го­ритм ре­ше­ния. Ис­прав­ле­ние ошиб­ки долж­но за­тра­ги­вать толь­ко стро­ку, в ко­то­рой на­хо­дит­ся ошиб­ка.

3.  Ука­жи­те одно число для ко­то­ро­го эта про­грам­ма будет ра­бо­тать верно.

Дан це­ло­чис­лен­ный мас­сив из 20 эле­мен­тов. Эле­мен­ты мас­си­ва могут при­ни­мать целые зна­че­ния от 0 до 1000 вклю­чи­тель­но. Опи­ши­те на есте­ствен­ном языке или на одном из язы­ков про­грам­ми­ро­ва­ния ал­го­ритм, поз­во­ля­ю­щий найти и вы­ве­сти мак­си­маль­ное зна­че­ние среди дву­знач­ных эле­мен­тов мас­си­ва, не де­ля­щих­ся на цифру стар­ше­го раз­ря­да. Если в ис­ход­ном мас­си­ве нет эле­мен­та, зна­че­ние ко­то­ро­го яв­ля­ет­ся дву­знач­ным чис­лом и при этом не крат­но цифре стар­ше­го раз­ря­да дан­но­го числа, то вы­ве­ди­те со­об­ще­ние «Не най­де­но».

Ис­ход­ные дан­ные объ­яв­ле­ны так, как по­ка­за­но ниже на при­ме­рах для не­ко­то­рых язы­ков про­грам­ми­ро­ва­ния и есте­ствен­но­го языка. За­пре­ща­ет­ся ис­поль­зо­вать пе­ре­мен­ные, не опи­сан­ные ниже, но раз­ре­ша­ет­ся не ис­поль­зо­вать не­ко­то­рые из опи­сан­ных пе­ре­мен­ных.

Две по­дру­ги, Катя и Ира, иг­ра­ют в сле­ду­ю­щую игру. Перед по­дру­га­ми лежит куча кам­ней. Де­вуш­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Катя. За один ход де­вуш­ка может до­ба­вить в кучу один или два камня или уве­ли­чить ко­ли­че­ство кам­ней в куче в два раза. На­при­мер, имея кучу из 10 кам­ней, за один ход можно по­лу­чить кучу из 11, 12 или 20 кам­ней. У каж­дой де­вуш­ки, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

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

В на­чаль­ный мо­мент в куче было S кам­ней, 1 ≤ S ≤34.

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

Вы­пол­ни­те сле­ду­ю­щие за­да­ния. Во всех слу­ча­ях обос­но­вы­вай­те свой ответ.

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

б)  Ука­жи­те такое зна­че­ние S, при ко­то­ром Катя не может вы­иг­рать за один ход, но при любом ходе Кати Ира может вы­иг­рать своим пер­вым ходом.

Опи­ши­те вы­иг­рыш­ную стра­те­гию Иры.

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

Для каж­до­го ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Кати.

3.  Ука­жи­те зна­че­ние S, при ко­то­ром:

– у Иры есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая ей вы­иг­рать пер­вым или вто­рым ходом при любой игре Кати, и

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

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

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

На вход про­грам­ме в пер­вой стро­ке по­да­ет­ся число дан­ных N о сто­и­мо­сти роз. В каж­дой из по­сле­ду­ю­щих N строк на­хо­дит­ся ин­фор­ма­ция в сле­ду­ю­щем фор­ма­те:

<Ком­па­ния><Улица><Вид><Цена>

где <Ком­па­ния>  — стро­ка, со­сто­я­щая не более, чем из 20 сим­во­лов без про­бе­лов, <Улица>  — стро­ка, со­сто­я­щая не более, чем из 20 сим­во­лов без про­бе­лов, <Вид>  — сим­вол Б, К или Ж, <Цена>  — целое число в диа­па­зо­не от 100 до 500, обо­зна­ча­ю­щее сто­и­мость одной розы.

<Ком­па­ния> и <Улица>, <Улица> и <Вид>, а также <Вид> и <Цена> раз­де­ле­ны ровно одним про­бе­лом.

При­мер вход­ной стро­ки:

Тор­г­Цвет Са­до­вая Ж 225

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

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

7 5 0