Нещата обаче все още не са толкова розови



Дата14.01.2019
Размер52.9 Kb.
Огради меда
След като успешно помогнахте на Мечо Пухикс да се справи с римляните (или поне всички се надяваме, че е така) и родът е продължен (знаете колко зле могат да се отразят нещата с променянето на историята, след като вече се е случила, нали...), Мечо Пух отново е изправен пред проблемите на ежедневието. А именно – проточилата се икономическа криза го доведе до сериозно заслабване и застрашително гладуване. След като пробва какво ли не, Пух вече премина към отчаяни мерки – днес той успя да влезе в най-големия кошер в гората.

Нещата обаче все още не са толкова розови. Кошерът не изглежда точно така, както Мечо си представяше – тъй като пчелите, като част от световното стопанство, също са в криза, стените на отделните клетки за мед изобщо не съществуват – били са разпратени по други пътеки. А понеже шестоъгълниците вече не са на мода, тенденцията е пчелите да строят кошери с квадратни клетки.i Така в момента Пух е изправен пред една мрежа от стълбове, между които медът се движи напълно свободно. Сега Мечо и пчелите играят следната игра: редуват се да свързват съседни стълбове – и който успее да загради клетка изцяло, получава меда в нея и правото (а всъщност и задължението) да свързва отново. Печели този, който е получил повече клетки с мед. При равенство, печели вторият играч (тъй като все пак първият е имал предимството да е първи).


Формално погледнато, пчелната пита, на която се разиграва действието, може да се разглежда като “празна” мрежа от квадратчета (empty grid) с N реда и M колони – всяко квадратче представлява клетка с мед, като при всеки ход един от двамата играчи добавя някоя от страните на квадратче(та), свързвайки крайните й точки. В момента, в който даден играч загради изцяло дадено квадратче, то се счита за “завладяно” от него и играчът е длъжен отново да свърже (някои други) две точки.


Примерно разиграване върху пита 2 x 2. Пчелите, тъй като са мнозинство спрямо Мечо, винаги са първи. И, естествено, използвайки едновременно интелектуалната мощ на хилядите (иначе по отделно безполезни) работнички, печелят. От началото Мечо играе „огледално” спрямо тях, надявайки се да раздели питата на две отделни части и да осигури равенство. Пчелите правят жертва на ход 7 и Мечо я приема, обаче това го обрича на загуба – тъй е длъжен да направи още един ход, при което свързва централната точка с тази вдясно от нея. Пчелите моментално се възползват и свързват останалите клетки във верига, побеждавайки с 3 на 1.


Очевидно, сам Мечо ще загуби всяка следваща игра срещу чудовищно умния мулти-процесорен организъм на кошера. Помогнете му! Напишете програма, която играе играта вместо него. Иначе рискувате да остане без мед през зимата – кой тогава ще е главният герой в останалите задачи?!


На първия ред от входния файл dnh.in ще получите числата K, N и M. Числото K означава кой ход подред в играта трябва да направите (K=1 за първия ход на пчелите, K=2 за първия ход на Мечо, K=3 за втория ход на пчелите и т.н.). Забележете, че няколко последователни свързвания от един играч (всяко, потенциално без последното, водещо до придобиване на квадратче) се считат за един ход. На следващия ред ще получите числото T – броя страни, които другият играч е добавил в предния си ход (при K = 1, естествено, T = 0, иначе T ≥ 1). На всеки следващите T реда ще получите по две числа R и C, означаващи новите страни в реда, в който са добавени на предния ход от другия играч. Нечетно R означава долната страна на C-тото квадратче от (R/2)-вия ред (или горната страна на C-тото квадратче от (R/2+1)-рия ред) при номериране на редовете от горе надолу с 1, 2, 3 и т.н. и на квадратчетата на всеки ред от ляво надясно с 1, 2, 3 и т.н. Четно R означава дясната страна на (C-1)-вото квадратче от (R/2)-рия ред (или лявата страна на C-тото квадратче от същия ред). На кратко, това е най-интуитивната номерация.
В изходния файл dnh.out трябва да изпишете T, броя на добавените страни от Вашия ход, и на следващите T реда да опишете всяка една от тези страни в съответния ред (в гореописания формат). Ако не можете да направите ход (всички страни за добавени), изведете само 0.
Примерното разиграване от картинката:


Ход

Пчелите dnh.in

Пчелите dnh.out

Мечо dnh.in

Мечо dnh.out

1

1 2 2

0


1

1 1





2




2 2 2

1

1 1



1

5 2


3

3 2 2

1

5 2



1

1 2





4




4 2 2

1

1 2



1

5 1


5

5 2 2

1

5 1



1

2 1





6




6 2 2

1

2 1



1

4 3


7

7 2 2

1

4 3



1

3 1


Повратният момент в играта...

8




8 2 2

1

3 1



2

2 2


3 2

9

9 2 2

2

2 2



3 2

3

2 3


4 2

4 1





10

Целта на този „фиктивен” ход е все пак програмата Ви да разбере, че играта е свършила.

10 2 2

3

2 3



4 2

4 1


0

Ограничения:

В 60% от тестовете, 2 ≤ N ≤ 7 и 2 ≤ M ≤ 7. В останалите 40%, 8 ≤ N ≤ 50, 8 ≤ M ≤ 50.

Разрешено е решението да създава и ползва до 100 временни файла в папката, в която работи, с обща големина не повече от 1 GB (100 е максималният брой на файловете в конкретен момент – иначе може да създавате и да триете колкото желаете).



Гарантирано е, че всяка започната игра ще се разиграва коректно до края, т.е. няма да се смесват ходовете на две различни игри, няма да се прескачат ходове и пр. Всички числа във входа ще са цели и неотрицателни и ще дават валидна информация. Временните файлове, направени от решението Ви, няма да бъдат изтривани или променяни между две различни разигравания (поддържането им е изцяло Ваша отговорност).
Оценяването ще се извърши по следния начин: решението на всеки участник X ще бъде пуснато срещу решението на всеки друг участник Y по два пъти – всеки по веднъж в ролята на Мечо и в ролята на пчелите (първия път X e пръв на ход, втория път - Y). Счита се, че X е победил ако има повече квадратчета от Y или ако е втори и има равен брой квадратчета с Y (в противен случай е загубил). При две победи на X над Y, на X се присъждат 3 точки (а на Y - нула). При една победа и една загуба, на X се присъжда 1 точка (също както и на Y). При две загуби, X получава 0 точки (а Y, разбира се, 3). При невалиден ход (или изход, несъответстващ на гореописания формат) от страна на някого, играта се прекратява с победа за другия, независимо от текущото състояние на пчелната пита. Общият резултат на X се образува от сбора на точките, получил от двойките игри с всеки друг (резултатът накрая се „оразмерява” до емблематичните 100 точки, разбира се).


i Бел. авт.: първоначалната идея беше играта да се състои на "нормална" пчелна пита, т. е. вариант не с квадратчета, а с шестоъгълници. Въпреки че решихме да използваме по-стандартната версия, окуражаваме Ви да помислите и върху другата алтернатива, която се оказа далеч по-малко изследвана.


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница