XV конкурс по програмиране на PC Magazine Bulgaria и Мусала Софт




XV конкурс по програмиране на PC Magazine Bulgaria и Мусала Софт

PCMagazine, Брой 11
Категория: Обучение , Любопитно
Етикети: Конкурс по програмиране
PC MAGAZINE
12.11.2009

XV конкурс по програмиране на PC Magazine Bulgaria и Мусала Софт

Стартира вторият кръг от конкурса по програмиране под патронажа наФакултета по математика и информатика към СУ

Факултетът по математика и информатика (ФМИ, http://www.fmi.uni-sofia.bg/) на Софийски университет „Св. Климент Охридски” - най-старото и най-авторитетно висше учебно заведение в България, утвърдило се като световноизвестен научноизследователски център в областта на природо-математическите и обществените науки - обучава студенти в съвременни и приоритетни специалности: Математика, Приложна математика, Информатика, Компютърни науки, Информационни системи, Софтуерно инженерство и Статистика. ФМИ има над 2500 студенти и докторанти, 15 катедри и допълнителни помощни звена (компютърни лаборатории, центрове и др.). ФМИ притежава силен изследователски потенциал и участва с изследователски екипи в множество научни и приложни проекти по Фонд научни изследвания на МОМН, Иновационен фонд и конкурсите на Седма рамкова програма на ЕС в партньорство с водещи български и чуждестранни софтуерни компании. ФМИ успешно партнира и сътрудничи със сродни факултети от български и европейски университети.

Огради меда

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

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

Формално погледнато, пчелната пита, на която се разиграва действието, може да се разглежда като „празна“мрежа от квадратчета (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.

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

В 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 точки, разбира се).

Крайният срок за участие във втория кръг е 10 декември. Решения на задачата се приемат през сайта http://konkurs.musala.com/

 

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


Съдържание: