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

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

1.  Пе­ре­ри­суй­те и за­пол­ни­те таб­ли­цу, ко­то­рая по­ка­зы­ва­ет, как ра­бо­та­ет про­грам­ма при ар­гу­мен­тах, при­над­ле­жа­щих раз­лич­ным об­ла­стям (A, B, C, D и E). Гра­ни­цы (точки 1, 7, 13 и 19) при­над­ле­жат за­штри­хо­ван­ным об­ла­стям (B и D со­от­вет­ствен­но).

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

2.  Ука­жи­те, как нужно до­ра­бо­тать про­грам­му, чтобы не было слу­ча­ев её не­пра­виль­ной ра­бо­ты. (Это можно сде­лать не­сколь­ки­ми спо­со­ба­ми, до­ста­точ­но ука­зать любой спо­соб до­ра­бот­ки ис­ход­ной про­грам­мы.)

Дан це­ло­чис­лен­ный мас­сив из 30 эле­мен­тов. Эле­мен­ты мас­си­ва могут при­ни­мать зна­че­ния от 0 до 100 и со­дер­жат ито­го­вые баллы участ­ни­ков олим­пи­а­ды по ин­фор­ма­ти­ке. Опи­ши­те на рус­ском языке или на одном из язы­ков про­грам­ми­ро­ва­ния ал­го­ритм, ко­то­рый поз­во­ля­ет под­счи­тать и вы­ве­сти сред­ний балл среди участ­ни­ков, став­ших призёрами олим­пи­а­ды (призёрами олим­пи­а­ды стали школь­ни­ки, на­брав­шие более 50 бал­лов). Га­ран­ти­ру­ет­ся, что хотя бы один участ­ник олим­пи­а­ды стал её призёром. Ис­ход­ные дан­ные объ­яв­ле­ны так, как по­ка­за­но ниже. За­пре­ща­ет­ся ис­поль­зо­вать пе­ре­мен­ные, не опи­сан­ные ниже, но раз­ре­ша­ет­ся не ис­поль­зо­вать часть из них.

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

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

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

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

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

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

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

За­да­ние 1

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

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

За­да­ние 2

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

– Петя не может вы­иг­рать за один ход;

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

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

За­да­ние 3

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

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

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

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

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

На вход про­грам­ме по­да­ют­ся све­де­ния о пас­са­жи­рах, за­бро­ни­ро­вав­ших по Ин­тер­не­ту авиа­би­ле­ты (толь­ко тех, у кого время бро­ни­ро­ва­ния ещё не ис­тек­ло). В пер­вой стро­ке за­да­но те­ку­щее время: через двое­то­чие два целых числа, со­от­вет­ству­ю­щие часам (от 00 до 23  — ровно 2 сим­во­ла) и ми­ну­там (от 00 до 59  — ровно 2 сим­во­ла). Во вто­рой стро­ке со­об­ща­ет­ся число пас­са­жи­ров N, ко­то­рое не мень­ше 3, но не пре­вос­хо­дит 1000. Каж­дая из сле­ду­ю­щих N строк имеет сле­ду­ю­щий фор­мат:

<Фа­ми­лия> <время окон­ча­ния брони>,

где <Фа­ми­лия>  — стро­ка, со­сто­я­щая не более чем из 20 не­про­бель­ных сим­во­лов; <время окон­ча­ния брони>  — через двое­то­чие два целых числа, со­от­вет­ству­ю­щие часам (от 00 до 23  — ровно 2 сим­во­ла) и ми­ну­там (от 00 до 59  — ровно 2 сим­во­ла). <Фа­ми­лия> и <время окон­ча­ния брони> раз­де­ле­ны одним про­бе­лом. Све­де­ния от­сор­ти­ро­ва­ны в по­ряд­ке вре­ме­ни, когда про­из­во­ди­лось бро­ни­ро­ва­ние. Все зна­че­ния вре­ме­ни от­но­сят­ся к те­ку­щим сут­кам.

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

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

10:00

3

Ива­нов 13:00

Пет­ров 10:00

Си­до­ров 13:12

Ре­зуль­тат ра­бо­ты про­грам­мы на этих вход­ных дан­ных:

Пет­ров

Ива­нов