Нещата обаче все още не са толкова розови. Кошерът не изглежда точно така, както Мечо си представяше – тъй като пчелите, като част от световното стопанство, също са в криза, стените на отделните клетки за мед изобщо не съществуват – били са разпратени по други пътеки. А понеже шестоъгълниците вече не са на мода, тенденцията е пчелите да строят кошери с квадратни клетки.i Така в момента Пух е изправен пред една мрежа от стълбове, между които медът се движи напълно свободно. Сега Мечо и пчелите играят следната игра: редуват се да свързват съседни стълбове – и който успее да загради клетка изцяло, получава меда в нея и правото (а всъщност и задължението) да свързва отново. Печели този, който е получил повече клетки с мед. При равенство, печели вторият играч (тъй като все пак първият е имал предимството да е първи).
Очевидно, сам Мечо ще загуби всяка следваща игра срещу чудовищно умния мулти-процесорен организъм на кошера. Помогнете му! Напишете програма, която играе играта вместо него. Иначе рискувате да остане без мед през зимата – кой тогава ще е главният герой в останалите задачи?!
На първия ред от входния файл
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 точки, разбира се).