Битката за гьола (Жабокалипсис)
Финал на конкурса на Telerik и PC Magazine Bulgaria, сезон 2012/2013

 

Всяка жаба да си знае гьола, но с това глобално затопляне гьоловете на героите в този кръг започват да стават все по-трудноузнаваеми. По последни данни около 18 жаби се борят за оцеляване в намаляващите водни ресурси.

Гьоловете на нашите жаби са малко по-особени – те не са какви да е локви, а са идеални кръгове, в които жабите се помещават. Във всеки гьол има по две жаби, които никак не обичат да се допират една до друга. Толкова не обичат, че като се допрат – умират. Когато гьолът е достатъчно голям това не е проблем. Но както казахме глобалното затопляне е започнало да влияе на тези райски кътчета за нашите жаби – гьоловете се смаляват!

Ако жабите ни можеха да говорят, щяха да кажат, типично по каубойски: “В този гьол няма място и за двамата (двете) ни”. Може би нашите жаби не са толкова далеч от каубоите, защото освен че така биха казали, те са се научили да ползват огнестрелно оръжие. Това прави битката за територия в гьола още по-интересна, нали? Още по-екстремни стават нещата, когато разберем, че жабите ни са доста чувствителни на липса на вода. В момента, в който и най-малката част от тях напусне гьола, жабите умират.

Ще помогнете ли на вашата жаба (нямате си жаба? — е, вече си имате), като напишете програма, която я упътва така, че да оцелее по-дълго от другата жаба в гьола? Е… и в двата случая поне ще ядем жабешки бутчета.

Описание на поведението на жабите и гьола

Гьолът ще представим като окръжност, с център (0,0) и радиус 100 в Евклидова координатна система.

Съответно жабите също ще бъдат кръгове, всяка с радиус 3.5.

Първата жаба се намира на позиция (-80, 0), а втората се намира на позиция (80, 0), тоест симетрично на центъра на гьола по координатната ос X.

За всяка единица време, жабите могат да извършат общо 2 действия, като двете жаби извършват тези действия едновременно:

  • Стрелба в определена посока
  • Скок в определена посока

Също така, за всяка единица време гьолът свива радиусът си с 1, тоест за общо 100 хода гьолът ще стане с радиус 0.

Една жаба може да скочи най-много на разстояние 2 от текущата си позиция. Жабите са много бързи и скокът става мигновено, тоест пренебрегва се времето за придвижване.

Когато една жаба стреля, тя произвежда куршум, който се движи в посоката, в която е изстрелян, със скорост 10 за единица време. Това означава, че ако в първата единица време е изстрелян куршум от (80, 0) към центъра (0, 0), то на втората единица време този куршум ще е стигнал до (70, 0) и в следващите ходове ще продължи да се движи.

Жабите не стрелят точно по нормалния начин – техните куршуми отскачат от водата, като разстоянието между два отскока на един куршум е точно 1. Куршумът може да порази жаба само ако попадне в нея при отскок. Тоест, ако една жаба се намира на една от позициите, на които куршумът ще отскочи, тя ще бъде убита. Математически, ако позицията, от която куршумът отскача, се съдържа в кръга описващ жабата, жабата ще бъде убита.

Куршумът винаги тръгва от центърът на жабата, като първите 3 отскока се пренебрегват (тъй като попадат в стрелящата жаба). Ако куршумът не уцели жаба, той излиза извън гьола.

Посоката на стрелба и посоката на скок се определят с “целево местоположение”, тоест мястото към което скача/стреля жабата. При скок това място може да е извън обсега на жабата, при което жабата ще скочи в тази посока и ще падне там където ? свършва обсега. При стрелбата важи същото правило, с изключението че стрелбата няма обсег, т.е. в определена единица време е гарантирано, че куршумът ще стигне до целта (но не е гарантирано, че там ще има отскок) и след това ще продължи.

Например ако имаме жаба на позиция (-80, 0) и ? кажем да скача към позиция (0,0), то на следващия ход жабата ще бъде на позиция (-78, 0). Скачане и стреляне по диагонал също е възможно, както и във всяка друга посока.

След като стреля веднъж, една жаба има нужда от 7 единици време (хода) за да презареди, през което време не може да стреля.

Ако окръжността, която описва една жаба, пресече или допре окръжността, която описва друга жаба, и двете жаби умират и “двубоят” завършва наравно.

Ако окръжността, която описва една жаба, пресече или допре ръбът на гьола (т.е. ако част от жабата излезе извън гьола), жабата умира и ако втората жаба е все още жива в този момент, втората печели (и обратно).

Възможно е две жаби се уцелят едновременно с куршуми, “двубоят” също завършва наравно. Едновременно означава за една и съща единица време (тоест не е от значение на кой отскок са уцелени едната или другата жаба, достатъчно е в един от отскоците това да се е случило).

Алгоритмична задача – стратегия за управление на жаба

Напишете програма, която управлява една жаба, спрямо правилата описани по-горе. Алгоритъмът ще бъде стартиран веднъж за всеки ход, като на всеки ход ще му бъде подавано текущото състояние на гьола, наред с всички куршуми и жаби. Алгоритъмът трябва да изчисли най-доброто действие, което може да предприеме за текущия ход и да го изпечата на стандартния изход, след което да приключи своята работа.

Входни данни

Входните данни се въвеждат от стандартния вход (конзолата)

На първия ред от входните данни стои числото R – текущият радиус на гьола (при първото стартиране на алгоритъма, това число ще бъде 100).

На следващия ред стоят 2 реални и 1 цяло число, разделени с интервали. Двете реални числа описват координатите на жабата, която алгоритъмът управлява (съответно x и y). Цялото число описва след колко единици време жабата ще може да стреля отново (при първото стартиране на алгоритъма, това число е 0, обозначаващо, че е възможна стрелба веднага).

На следващия ред под същата форма е описана жабата на противника

На следващия ред стои едно цяло число N – броят на куршумите, които се намират в гьола в момента.

На всеки един от следващите N реда е описан един куршум, в следния формат:

4 реални числа, разделени с интервали, първите 2 от които описват текущата позиция на куршума, а втората двойка – позицията, на която би стигнал куршумът, ако не уцели жаба (позицията е възможно да бъде извън гьола).

Изходни данни

Изходните данни се печатат на стандартния изход (конзолата).

Алгоритъмът трябва да изведе точно 2 реда на стандартния изход.

Първия ред трябва да съдържа команда за скок, в следния формат:

move координатиX координатиY

Втория ред трябва да съдържа команда за стрелба, в следния формат:

shoot координатиX координатиY

Ако алгоритъмът прецени, че не се нуждае от задаване на някоя от командите, трябва да изпечата празен ред на нейното място.

Ограничения

  • Алгоритъмът трябва да завършва работата си в рамките на 0.2 секунди, в противен случай ще бъде прекъсван автоматично и ще бъде считано, че просто е дал празни команди за тази единица време.

Оценяваща система

Текущата версия на оценяващата система можете да намерите тук: http://downloads.academy.telerik.com/svn/pc-magazine/Public/season-2012-2013/final-round/BattleExecutor.zip

Приложна задача – симулация на Жабокалипсис

За приложната задача, направете приложение, което симулира битката между две жаби, като:

  • Зарежда два алгоритъма, които да бъдат противопоставени един срещу друг
  • Визуализира самата битка между двата алгоритъма
  • Показва резултати от битката, както и статистическа информация (напр. брой на изстрелите, общо изминато разстояние и т.н.)
  • Дава възможност за игра на човек срещу компютър (или човек срещу човек)

Както обикновено, подтикваме състезателите да проявят творчество, като сами преценят как да имплементират изброените функционалности. Възможно е визуализацията да бъде 2D или 3D, приложението да работи в уеб среда или в Desktop режим (а защо да не бъде и Windows Store App). Журито ще оцени положително допълнителни функционалности и оригинални решения.

Критерии за оценяване

Оценяване на алгоритмичната част

При оценяването всеки алгоритъм ще бъде изправен срещу всеки друг алгоритъм. За победа, на един алгоритъм ще се присъждат 2 точки, за равенство – 1, а за загуба – 0. Накрая алгоритъмът с най-много точки ще бъде обявен за победител и ще получи 10 точки в крайното класиране, а останалите – съответната част от тези точки.

Оценяване на приложната част

Оценяването на приложната задача ще се извърши по-следните критерии:

  • Коректност (доколко са имплементирани посочените функционалности) – 2 точки
  • Справяне с грешки (справяне с некоректно поведение и непредвидени ситуации) – 2 точки
  • Ползваемост (доколко е удобна и интуитивна е работата с приложението) – 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
    • за предалите приложна част на WinRT, тестването на приложната част ще бъде извършено на система с минимални характеристики OS Windows 8 64-bit, 6 GB RAM, Intel i7-720QM, 1GB ATI Mobility Radeon HD 4250.