На 19 ноември направихме официално откриване на националния конкурс по програмиране на PC Magazine и Телерик. На сбирката представихме конкурса, неговите правила, цели и формат на провеждане. Обяснихме в детайли условието на първата конкурсна задача “Игра на тролове”, възможни принципни подходи за решаване, дори демонстрирахме на живо как може да се напише някакво (макар и не много добро) решение на алгоритмичната и на приложната част на задачата. За тези от вас, които не можаха да присъстват, сме записали видео:
Задача #1 за сезон 2012/2013 – игра на тролове
Игра на тролове
Задача #1 от конкурса на Telerik
и PC Magazine Bulgaria, 2012/2013
Дивите тролове са недружелюбна, мистична и миришеща раса, обитаваща дълбоките гори на още по-мистичния и измислен континент Азерот. В хобитата им навлизат дейности като състезания по надяждане със дървесна смола, турнири на ловци на глави, дразнене на каменни гиганти, надлъгване, пушене на камъни, дебнене на питомни крави в размножителен период, пускане на досадни коментари в Интернет и още много други неща, до които въображението на читателя може да достигне, но моралът не позволява да бъде написано.
Изследвания на INT32 (Института за Наблюдение на Троловете, основан през 1932 г.) разкриват, че напоследък троловете все по-често играят една интересна и находчива игра, която от института наричат “Игра на тролове”. Те дори са склонни да я играят с чуждоземци (например хора). Е, ако съответния чуждоземец има нещастието да изгуби… ще оставим това на историята да разкаже. От друга страна, при печалба, троловете позволяват на чуждоземецът свободно да обитава техните земи, което дава огромни възможности за наблюдение на културата на тези толкова интересни създания, дори участие в хранителния им режим.
За да не рискуват последствията (и миризмата) от една игра с троловете, учени от Казмоданския Висше Образователно-Разузнавателен Елитен Чародейски Институт (КВО-РЕЧИ) съвместно с INT32 са решили да изпратят парен робот (няма пари за слънчеви батерии), програмиран да изиграе успешна игра на предстоящите турнири и след това да наблюдава троловете, в името на научния прогрес. Тъй като в КВО-РЕЧИ и INT32 няма много програмисти, те молят вас за помощ. Ще помогнете ли за разкриването на вечната мистерия на троловете?
Описание на “Игра на тролове”
Играта се играе в квадратно поле, съставено от N*N квадратни плочки (всяка страна има по N плочки), като на всяка плочка има кули от каменни кубчета, наредени едно върху друго. В играта се въвеждат концепцията на “съседни плочки“, “съседни кули” и “височина на кула“. Височина на кула наричаме броя кубчета, от които се състои една кула върху дадена плочка. Две плочки са съседни, ако имат обща страна, т.е. една плочка може да има най-много 4 съседни плочки (ако е в някой от ъглите има 2, а ако е на някоя от страните, без да е в ъгъл, има 3). Съседни кули съответно ще наричаме всички кули, които са върху съседни плочки.
В началото на играта няма кули, с еднакви височини, които да са съседи. Играчът получава право на точно C на брой хода, като може на всеки ход да прави точно една от следните две операции:
- Да добавя едно кубче върху някоя кула (т. е. увеличаване на височината на една кула).
- Да взема едно кубче от някоя кула (т. е. намаляване на височината на една кула).
За един ход, играчът може да вземе или добави точно едно кубче от някоя от кулите. Съответно сумарно броят кубчета, които играчът може да вземе или добави за цялата игра съответства на броя ходове, на които има право.
В играта има едно интересно правило – ако на някой ход от играта две или повече съседни кули са с еднаква височина, всичките кубчета в тези кули се премахват от полето автоматично, без това допълнително да отнема ход на играча. Всъщност в далечен Азерот тролът-съдия-шаман следи за правилата и когато две или повече съседни кули се изравнят по височина, той ги изравнява със земята с тайнствен ритуал и в крайна сметка на засегнатите плочки остават по точно 0 кубчета.
На края на играта играчът печели точки, равни на броя премахнати кубчета от полето (т.е. броя първоначални кубчета минус останалите на полето кубчета). Съответно целта на играча е в рамките на позволения брой ходове да играе така, че на игралното поле да останат възможно най-малко кубчета.
Алгоритмична задача – стратегия за “Игра на тролове”
Напишете програма (алгоритъм), която управлява парния робот на КВО-РЕЧИ, така че той да играе “Игра на тролове” възможно най-успешно, спрямо дадените ходове и игрално поле.
Входни данни
Входните данни се четат от конзолата. На първия ред стои числото C – броят ходове, на които роботът има право. На втория ред стои числото N – дължината на страната на квадратното игрално поле (т.е. броя плочки във всеки ред и всяка колонка в игралното поле).
На следващите N реда стоят по точно N положителни цели числа на ред. Всеки ред числа описва един ред плочки от игралното поле – всяко число на реда показва колко кубчета има върху всяка една плочка от този ред (т.е. височината на кулата, намираща се на тази плочка).
Входните данни винаги ще бъдат валидни и в описания формат.
Изходни данни
Изходните данни трябва да бъдат точно в описания по-долу формат, в противен случай е възможно парният робот да бъде изяден от троловете, а на алгоритъмът да бъдат присъдени съответно 0 точки в класирането.
Изходните данни се печатат на стандартния изход (конзолата). На изхода трябва да бъдат отпечатани точно C на брой реда (т.е. колкото е броят позволени ходове), всеки от които съдържа една команда и две цели положителни числа, разделени с по точно една шпация (интервал).
Командата може да бъде “put” или “take” (без кавичките) – съответно обозначаваща поставяне или вземане на кубче. Двете цели положителни числа описват съответно редът и колонката (т.е. координатите на кулата), от които трябва да бъде извършено поставянето или вземането на кубче.
Забележка: троловете и програмистите започват да броят от 0 – тоест координатите на първата плочка на първия ще бъдат 0 0, а не 1 1. Съответно координатите на втората плочка на първия ред ще бъдат 0 1, координатите на третата плочка на първия ред ще бъдат 0 2 и т.н.
Ако изходът е правилно форматиран, но съдържа по-малко от C на брой реда, се считат за изиграни само толкова ходове, колкото редове са били изведени.
Ограничения
- Числата C и N са цели и са в сила ограниченията 1 ? C, N ? 1000.
- В началото никоя кула няма да има височина по-голяма от 1000
- Програмата трябва да завършва своята работа за най-много 3 секунди. След третата секунда програмата ще бъде спряна автоматично.
- Ако на една плочка не са останали кубчета, ако програмата се опита да вземе кубче от тази плочка, този ход ще се счита за “пропилян”, тоест нищо няма да се случи, но играчът няма да бъде наказан.
- Възможно е крайният резултат да е отрицателен (например ако само добавяме кубчета, без да вземаме и без да се случват изравнявания на височини).
- При невалиден ход (например невалидна команда координати извън игралното поле) играчът може да получи наказание по преценка на журито.
Пример
|
Примерен вход |
Примерен изход |
| 2 4 1 2 3 4 5 6 7 8 9 1 8 7 1 2 3 4 |
put 2 3 take 3 1 |
Обяснение
|
Ход 1: повишаваме седмицата с едно |
Резултат: 3 съседни осмици и зануляване |
Ход 2: намаляваме двойката с едно |
Резултат: 3 съседни единици и зануляване |
|
1 2 3 4 5 6 7 8 9 1 8 7 1 2 3 4 |
1 2 3 4 5 6 7 8 9 1 8 8 1 2 3 4 |
1 2 3 4 5 6 7 0 9 1 0 0 1 2 3 4 |
1 2 3 4 5 6 7 0 9 1 0 0 1 1 3 4 |
| Краен резултат: За първи ход на полето са останали 8 + 8 + 7 кубчета по-малко (автоматично 8 + 8 + 8, но сме добавили 1). За втори ход сме намалили с още 4 кубчета (автоматично 1 + 1 + 1 и още 1 от вземане на кубче). Разликата между първоначалния брой кубчета и крайния брой кубчета след изиграване на ходовете е 27 и това е резултатът ни за този пример. | |||
Още един пример
|
Примерен вход |
Примерен изход |
| 4 3 1 2 3 5 6 7 9 1 8 |
take 0 2 take 0 2 take 0 2 take 0 2 |
| Краен резултат: просто сме опитали да вземем 4 пъти от тройката на първия ред. Първият път се получават две съседни двойки и те се нулират. Следващите 3 хода са празни (опитваме да вземем от празна плочка). Като резултат получаваме 5 точки от първия ход и по 0 от останалите 3 хода (общо 5 точки). Забележка: това е валидно поведение, независимо че не печели възможно най-много точки. | |
Задача по приложно програмиране – визуализация на “Игра на тролове”
Учените от КВО-РЕЧИ не се изчерпват от идеи бързо. Освен алгоритъм за игра с троловете, имат нужда и от визуализация на това как е протекла играта, за да може да изследват както поведението на алгоритъма, така и какви подобрения могат да направят, за бъдещи срещи.
Малко по-формално описано, учените искат освен алгоритъма, още едно софтуерно приложение, което да използва същия алгоритъм, който е ползван за играта, но този път им трябва всеки ход да бъде описан в HTML формат.
Вашата задача е да напишете програма, която играе и визуализира “Игра на тролове”, като:
- Приема същите входни данни в описания вече формат или в друг формат по ваше желание.
- Форматът трябва да бъде описан по някакъв начин – било със подсказки по време на изпълнение на програмата или в допълнителен файл, или по друг начин.
- По желание може да се реализира и потребителски интерфейс за интерактивно въвеждане на игралното поле.
- Генерира отделна уеб страница за всеки ход от играта.
- Страницата трябва визуализира състоянието на игралното поле в този момент и може да съдържа и друга полезна информация (по ваш избор).
- Всяка страница трябва да има връзка (hyperlink) към страниците описващи предишния и следващия ход. По желание може да бъде реализирано автоматично преминаване към следващия ход (с 1 или няколко секунди изчакване).
- Начинът на визуализация не е строго дефиниран – състезателите имат свобода да решат как ще покажат игралното поле (таблица, картинки с камъни, само числа, графики, стилове, интерактивност, …), както и да визуализират текущия ход, така че визуализацията да бъде удобна и привлекателна за разглеждане.
- Състезателите имат право да ползват както HTML, така и CSS и JavaScript, такива че страниците да изглеждат коректно на съвременен уеб браузър от 2012 г.
- Приложението има права за четене и писане в директорията, в която се намира изпълнимият му файл.
- Отваря автоматично страницата, описваща първия ход:
- Това може да стане чрез извикване на уеб браузъра по подразбиране.
- По желание състезателите имат право да вградят визуализацията в собственото си приложение, при положение че тя е базирана на HTML и работи по същия начин, както в по-известните съвременни браузъри.
- Приемане на входни данни за играта.
- Генериране на толкова на брой изходни файлове, колкото ходове трябва да бъдат изиграни.
- Визуализиране на отделните страници и навигация между тях (например чрез браузър или вградена визуализация в приложението).
Обобщени задължителните функционалности на приложението
Начинът, по който изискваните функционалности са имплементирани не е строго определен и състезателите могат да проявят въображение и творчество. Насърчаваме добавянето на всякакви допълнителни функционалности по идея на състезателите, оригинални подходи и привлекателен дизайн.
Критерии за оценяване
Оценяване на алгоритмичната част
При оценяването ще бъдат ползвани 5 различни по големина игрални полета.
- Всеки алгоритъм ще бъде пуснат да играе на всяко едно от игралните полета.
- Резултат на един алгоритъм е сумата от резултатите му на различните игрални полета.
- Накрая, алгоритъмът с най-висок общ резултат, ще получи 10 точки в крайното класиране, а останалите ще получат пропорционален процент от тези точки, закръглен до цяло число.
- Ако резултатът на най-добрия алгоритъм е G, а резултатът на някой от алгоритмите е P, то този с резултат P ще има крайни точки = P/G * 10, закръглено до цяло число.
- Пример: ако играят алгоритми A, B и C, и алгоритъм B има резултат 520, алгоритъм C – 260, а алгоритъм A – 95 точки, крайните точки в класирането ще са следните: B – 10 точки; C – 5 точки; A – 2 точки.
- Максимални точки в крайното класиране за алгоритмичната част: 10
Критерии за оценяване на приложната част
Оценяването на приложната задача ще се извърши по-следните критерии:
- Коректност (доколко задължителните функционалности работят) – 3 точки
- Справяне с грешки (справяне с некоректно поведение и непредвидени ситуации) – 1 точка
- Ползваемост (доколко е удобна и интуитивна е работата с приложението) – 2 точки
- UI дизайн (доколко са приятни и удобни интерфейсът и визуализацията) – 2 точки
- Оригинални функции и решения, които да впечатлят журито – 2 точки
- Максимални точки в крайното класиране за приложната част: 10
Допълнителни изисквания
Задачите позволяват използването на различни езици за програмиране и технологии (например C#, PHP, C, C++, Delphi, Python, WPF, Windows Forms, Java, Swing, Flash, JavaScript, HTML5). Всички предадени решения ще бъдат тествани в Windows 7 среда съгласно общите условия на конкурса.
За алгоритмичната част се изисква да бъде предаден пълен сорс код + изпълним файл за Windows (.exe). Ако програмирате на език, който по природа не създава изпълними .exe файлове (например PHP, Python, Java или JavaScript), използвайте подходящ компилатор (потърсете в Интернет).
За приложната част се изисква да бъде предаден пълен сорс код + изпълним файл. Състезателите имат право да изберат начина, по който тяхното приложение ще бъде стартирано, така че това да е удобно в Windows среда (приложението може също да бъде web-базирано и да се отваря през браузър). Тъй като оценяването на приложната част ще бъде извършвано и от гледната точка на потребител (а потребителите искат да стартират едно приложение възможно най-бързо и лесно), сериозни затруднения при намирането и стартирането на приложението могат да намалят присъдените от журито точки.
Характеристики на системата, върху която ще бъде проведено тестването
- Intel® Xeon® CPU E31225 @ 3.10 GHz
- 16 GB RAM
- 128 MB Video Memory (dedicated) Intel® HD Graphics video card
- 232 GB HDD
- Microsoft Windows 7 64-bit OS
Краен срок
Краен срок за предаване на решения: 16 декември 2012 г.
Инструкции за предаване на решения ще бъдат публикувани в раздел “Качи решение” в следващите седмици
Конкурс по програмиране на PC Magazine Bulgaria и Телерик – сезон 2012/2013
Конкурсът по програмиране развива алгоритмичното мислене на състезателите и техните способности да разработват решения на практически проблеми от разработката на софтуер, да построяват технологични решения базирани на съвременни софтуерни платформи, езици за програмиране и технологии, да работят в екип, да си разделят задачите по проекта и да постигат съвместно по-добри резултати. Той обединява уменията на добрите състезатели по алгоритми с уменията на добрите софтуерни инженери, които разработват приложен софтуер и в крайна сметка подготвя състезателите за живота и за реална работа в софтуерната индустрия, където се изискват проучване, дизайн, разработка, тестване, внедряване и поддръжка на цялостни продукти и софтуерни решения. Това прави конкурса много ценен за младите хора, които искат да станат кадърни софтуерни инженери, и дава възможност за развитие на практически умения, които един ден състезателите ще използват в професията си.
Сезон 2012/2013
През този сезон конкурсът ще навлезе в 18-тата поредна година от съществуването си, а за втора поредна година състезателите ще се борят както с алгоритмични проблеми, така и с приложната част на софтуерното инженерство. В състезанието може да участват както индивидуални участници, така и отбори до двама души.
В различните кръгове състезателите ще работят в много от сферите в софтуерното инженерство, започвайки от по-лесни за решаване проблеми и придвижвайки се към все по-комплексни приложения, решаващи реални проблеми и задачи от софтуерната индустрия.
Темите на задачите за съответните кръгове ще гравитират около съответния учебния материал, изучаван в Софтуерната Академия на Телерик.
Междинни кръгове
Състезанието се състои от няколко междинни кръга и един финален кръг. Междинните кръгове се провеждат приблизително веднъж на месец и се състоят в следния формат:
- Журито публикува условие на задача за съответния кръг на главната страница на конкурса, както и в секция “Задачи“
- Участниците имат 20-дневен срок (или повече, ако в условието на задачата е споменат по-дълъг срок) да предадат решение. Решенията се предават чрез секцията “Качи решение” (освен ако условието на задачата не гласи друго)
- Журито оценява алгоритмичните и приложните части на предадените решения
- Журито публикува резултатите от междинните кръгове на главната страница на конкурса
- Журито обновява генералното класиране в секция “Класиране“
Резултатът за определен междинен кръг се определя от сбора на резултатите за приложната и алгоритмичната част на отбора за съответния кръг
Генералното класиране се формира като за всеки отбор се съберат резултатите, които отборът има на кръговете, в които е участвал. Съответно, в колкото повече кръгове участва един отбор, толкова по-голям шанс има да излезе напред в генералното класиране.
Финален кръг
На финалния кръг на състезанието се класират първите 30 отбора в генералното класиране (журито си запазва правото да промени тази бройка, спрямо показаните резултати от състезателите, като следва своевременно да съобщи за такава промяна).
Финалния кръг се провежда в два състезателни дни, присъствено (за отбори от двама състезатели е нужно присъствието на поне единия).
- Първия ден се дава условието на задача с приложна и алгоритмична част (както на междинните кръгове). Всеки отбор решава задачата на място и трябва да предаде алгоритмичната и приложната част на решението си в рамките на 12 часа (този период може да бъде удължен по преценка на журито).
- На втория ден всеки отбор представя приложната част на решението си пред журито и останалите участници в рамките на 10 минути, като журито и останалите участници имат право да задават въпроси. Журито поставя оценки на приложната част по време на представянето. Идеята на представянето е всеки отбор да може възможно най-добре и пълно да представи решението си на приложната част, с цел да получи по-висока оценка. Журито заседава и решава крайните оценки на приложната част. Алгоритмичната част се оценява автоматизирано. Финалния резултат на всеки отбор се определя от сбора на резултата му от приложната и алгоритмичната част на финалния кръг
- След представянията на втория ден се провежда награждаване и закриване на състезанието
Финалния кръг ще се проведе в София, като датите и мястото ще бъдат предварително обявени.
Регламент
Подробно описание на регламента за сезон 2012/2013 може да намерите в секция “Регламент“.
Награди
На финалния кръг на състезанието ще бъдат раздадени големите награди (лаптопи, таблети, монитори…) на най-добре представилите се. Допълнително, организаторите си запазват правото да дават награди на междинните кръгове, като тези награди могат да варират (тениски, сертификати, компютърно оборудване и прочие).