Големи бомби

Задача #3 от конкурса на Telerik и PC Magazine Bulgaria, сезон 2012/2013

 

В Га-нгнамландия нещата не са розови. И не само защото розовият цвят всъщност не съществува сам по себе си (http://www.youtube.com/watch?v=S9dqJRyk0YM), а и защото там постоянно се водят войни за щяло и нещяло. Или по-конкретно, водят се, защото едно щяло нещо дето друго нещяло да ще да му го даде – стандартни неща. Сега тече поредният конфликт и вие сте призовани да помогнете с невероятните си лидерски умения – или пък с невероятните си умения в програмирането (а защо не и с двете).

Войната, която тече в момента, е за ресурси. Най-важният ресурс в Га-нгнамландия е една специфична подправка – Га-нгнам-сол, чиято цена е огромна на чуждестранните пазари. Враждуващите страни са малки феодални групировки от надцакващи се фермери. Всяка групировка притежава определен брой солни находища, върху които е построила солни мини, като към този момент всички имат еднакви приходи. Тъй като тези фермери не са склонни да живеят на равни начала, те се опитват да разрушат чуждите мини и в същото време да защитят своите мини от нападения. Естествено, нападенията и изграждането на защити струват пари, но тъй като фермерите живеят по мотото “не на мен да ми е добре, а на вуте да му е зле”, са склонни да се простят със спестяванията си, само и само да надцакат останалите. Пък и са намерили находчив начин да воюват икономично и изгодно.

Основната единица, която фермерите ползват за нападение, е гуцито с гърмелка (GG), а основният пазач е оборудваното пиле (OP). Пилетата и гуцитата могат да се позиционират на определени координати на полето и да се нападат. Това се постига с малко обучения (в които не се нараняват никакви животни) и фураж, който не струва скъпо. В една стандартна битка, пилетата пазят позициите, на които са разпределени, а групи от гуцита нападат солните мини, като се опитват да ги взривят. Тъй като гуцитата могат да копаят тунели под земята, те могат да се озоват на произволна позиция в бойното поле, така че защитаващите фермери обикновено поставят пилетата в близост до мините. Когато гуцитата и пилетата попаднат в битка, гуцитата правят камикадзе атака срещу пилетата, като ако успеят едновременно пилетата и гуцитата биват унищожени, а ако пилетата успеят да унищожат гуцитата преди завършването на камикадзе атаката, пилетата оцеляват и продължават да пазят позициите си. Най-силното оръжие на фермерите е “голямата бомба“. Тя представлява… голяма бомба, която може да бъде зареждана с домашна ракия, за да ? бъде увеличена мощността. Бомбата може да бъде хвърлена навсякъде по полето, унищожавайки всичко в радиуса на взрива си.

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

Описание на битките, единиците, защитаващите и атакуващите

Единица ще наричаме всеки обект в битката – гуци с гърмелка (GG), оборудвано пиле (OP), солна мина, бомба. Всяка битка се провежда на поле, върху което защитникът е наредил своите мини и защитаващи единици, с цел да предпази възможно най-много мини и единици. Полето можем да разглеждаме като първи квадрант на двумерна Евклидова координатна система, в която всички координати са неотрицателни цели числа (но разстоянията не са цели числа). Атакуващият, от своя страна, праща свои единици на определени координати, с цел да унищожи единиците и мините на защитаващия се. Това става, като атакуващият дава команди, които да бъдат изпълнявани. Всяка команда се изпълнява напълно, преди да бъде изпълнена следващата.

Цени на единици

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

Цените на единиците са както следва:

• гуци с гърмелка (GG): 7 пари
• оборудвано пиле (OP): 1 пари
• солна мина: 6 пари
• бомба с радиус нула (т.е. унищожава само единиците на съответните координати): 10 пари
  • увеличаване на радиуса с 1: +10 пари
  • увеличаване на радиуса с 2: +20 пари
  • няма ограничение за увеличаване на радиуса, освен ресура пари, които атакуващия има

Парите, с които атакуващия и защитаващия разполагат са както следва:

атакуващ: 200 пари

защитаващ: 200 пари

Забележка: валутната единица не е от значение в случая, затова ще ползваме 10 пари, 5 пари, 20 пари и т.н.

Придвижване и позициониране

Атакуващият може в даден момент да прати определен брой гуцита на определена позиция на полето. Когато това стане, гуцитата вече се считат за “използвани” и не могат да бъдат ползвани отново, а ресурсите за тях са изразходени. Съответно, смислено за атакуващия е да праща гуцита само на координати, на които те ще проведат битка с единици на защитаващия се. Гуцитата винаги се движат в група от 1 или повече.

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

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

Защитаващият може да позиционира точно една група от пилета (групата се състои от 1 или повече пилета) или точно една мина на една позиция – но не и двете едновременно, тоест не може да има мина върху която има пилета.

Битки

Всяка бойна единица (GG и OP) има обсег (радиус в който може да напада други единици). Битка се провежда, когато група единици на атакуващия (той може да има точно една група единици на полето в даден момент) е в обсега на поне една група единици на защитаващия се, или обратно.

Обсега е максималното евклидово разстояние, на което една единица може да нанесе поражения. Разстоянието между 2 точки се изчислява по формулата Dist = sqrt((x1 – x2)^2 + (y1 – y2)^2), където x1 и y1 са координатите на едната точка, x2 и y2 – на другата, ^2 означава втора степен, а sqrt означава корен квадратен – тоест това е стандартната формула за разстояние между 2 точки в Евклидовата равнина.

Обсега на единиците е както следва:

• гуци с гърмелка: 1.5
• оборудвано пиле: 2

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

Когато определена единица влезе в обсега на гуцитата, те се подготвят да се взривят, като ако успеят, взривяват всички единици в обсега си. Това, дали ще успеят зависи от броя пилета, в чиито обсег са гуцитата:

• Ако група гуцита с брой C е в обсега на точно C*2 или по-малко на брой пилета, то гуцитата ще успеят да се взривят и унищожат всички пилета в своя обсег, които е 1.5 (това не е задължително да са всички C*2 пилета, тъй като пилешкия обсег е по-голями някой от тези пилета може да са на разстояние по-голямо от 1.5).
  • В този случай всички солни мини, които са в обсега на гуцитата, също ще бъдат унищожени.
• Ако група гуцита с брой C е в обсега на точно C*2+1 или повече на брой пилета, то гуцитата ще бъдат унищожени преди да успеят да се взривят и нито едно пиле (или мина) няма да пострада.

Големите бомби

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

Голямата бомба може да има радиус (обсег) нула, което означава, че ще унищожи само единицата, която е на същите координати, на които е пусната бомбата. Също така, радиуса на бомбата може да бъде по-голям, в който случай всички единици на разстояние съответния радиус ще бъдат унищожени, но всяко увеличение струва пари (виж по-горе в “Цени на единици”).

Aтакуващият може да използва най-много 1 бомба за цялото сражение.

Забележка: не е възможно бомбата да унищожи единици (гуцита с гърмелки) на атакуващия.

Бойното поле

Както вече казахме, бойното поле се състои от точките с целочислени координати в първи квадрант на двумерна Евклидова координатна система. Това поле обаче не заема целия квадрант, тъй като той е безкраен, а е ограничено до 100 по оста X и 100 по оста Y. Това означава, че най-отдалечените от началото на бойното поле (0, 0) координати, на които е възможно да има единици са (100, 100).

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

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

Задача за алгоритъм (изпълнимия файл) – стратегия за атакуващия

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

Задача за генериране на тест (текстовия файл) – разположение на защитата

Напишете входни данни, в описания по-долу формат за входни данни, които описват разположение на единици на защитаващия се върху бойно поле, като се съобразявате с наличния ресурс от 200 пари (не задължително всичките) и с размерите 100 на 100 на бойното поле. Входните данни трябва да бъдат валидни и в описания по-долу формат, в противен случай тестът няма да бъде вземан предвид.

Входните данни трябва да бъдат записани в стандартен текстов файл (.txt) с ASCII кодировка, който може да бъде преглеждан в Windows среда чрез текстов редактор Notepad. За примери може да видите тестовите файлове публикувани за предишни кръгове на задачата (публичното хранилище на състезанието е на този адрес: http://downloads.academy.telerik.com/svn/pc-magazine/Public/)

Предаването на теста ще става чрез поставянето му в папката algorithm, наред с изпълнимия файл за алгоритмичната задача. Файлът трябва да бъде именован както е името на потребителя, който го е изпратил (например ако потребителят е george.s.georgiev, то файлът трябва да носи името george.s.georgiev.txt).

При тестването, входните данни от теста ще бъдат подадени на всеки един алгоритъм, включително и на алгоритъма на автора.

Входни данни

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

Входните данни се състоят от команди за поставяне на единици, които описват единиците в полето на защитаващия се. Командите са два вида:

• Поставяне на група оборудвани пилета:
  • Формат: chickens брой координатаX координатаY
  • Пример: chickens 5 10 11 ще постави група от 5 пилета на координати (10, 11)
• Поставяне на солна мина:
  • Формат: mine координатаX координатаY
  • Пример: mine 15 4 ще постави солна мина на координати (15, 4)

Не е възможно 2 команди във входните данни да имат съвпадащи координати, т.е. да се постави мина върху мина, мина върху пилета, пилета върху мина или два пъти на едни и същи позиции да се поставят пилета.

На първия ред от стандартния вход се въвежда числото N – броят команди, които ще опишат поставянето на единиците на защитаващия се.

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

Входните данни ще бъдат винаги валидни и в описания формат.

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

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

Изходните данни се състоят от команди, които описват единиците, с които атакуващия атакува единиците на защитаващия се. Командите са два вида:

• Пращане на група гуцита с гърмелки:
  • Формат: pigs брой координатиX координатиY
  • Пример: pigs 7 10 11 ще прати група от 7 гуцита да се взривят на координати (10, 11)
• Пращане на голяма бомба:
  • Формат: bomb радиус координатиX координатиY
  • Пример: bomb 2 13 4 ще взриви бомба с радиус 2 на координати (13, 4)

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

Ограничения

• Размерите на бойното поле са 100 по X и 100 по Y (включително).
• Сборът на цената на единиците на защитника е не повече от 200 (това трябва да бъде спазено и в тестовете на участниците).
• Сборът на цената на единиците на атакуващия трябва да бъде не повече от 200
• Не може 2 групи единици от една и съща страна да се разполагат на една и съща позиция. Възможно е обаче атакуващия да постави група единици на едни и същи координати с група единици на защитаващия.
• При проверката за всички сметки свързани с координати и разстояния ще бъде ползван стандартен 64-битов тип данни с плаваща запетая (известен като double в по-известните програмни езици), като стойностите ще бъдат закръгляни до 3-тата цифра след десетичната запетая.
• Програмата трябва да завършва своята работа за най-много 1 секунда. След изтичане на времето програмата ще бъде спряна автоматично.

Примери

С тези примери ще онагледим правилно форматиран вход и изход. Примерите имат за цел само да покажат правилния формат, а не да дават оптимално решение на задачата.

Примерен вход	Примерен изход
4 chickens 5 1 2 chickens 6 3 2 mine 2 2 chickens 4 3 3	pigs 7 3 4 pigs 4 2 2 pigs 3 1 3
Първа, втора и трета команда на атакуващия + резултат Обяснение: На горните картинки кафявата точка е група гуцита, червените точки са групи пилета, а синята точка е солна мина. При първата команда, атакуващия праща 7 гуцита на координати (3, 4). Те са в обсега на 2 групи пилета – (3, 2) и (3, 3) – общо 6 + 4 = 10 пилета. От своя страна, горната група пилета са в обсега на гуцитата, но долната не е (тъй като е на растояние 2). Тъй като общия брой пилета, които са в битка с гуцитата, е по-малък от броя гуцита умножен по две, гуцитата успяват да се взривят и да унищожат пилетата на координати (3, 3). При втората команда са пратени гуцита точно на координатите на мината, но те са в обсега на 2 групи пилета, чиято бройка надвишава умножената по две бройка на гуцитата и съответно гуцитата са унищожени без да се взривят. На третата команда са пратени 3 гуцита на координати (1, 3), които са в обсега на 1 група от 5 пилета. Тези пилета не са достатъчни да спрат гуцитата от взривяване и биват унищожени. В допълнение, солната мина на координати (2,2) е достатъчно близко до гуцитата, за да бъде в техния обсег и също бива унищожена. Накрая остава 1 група от 6 пилета на координати (3, 2). Общата сума на цените всички унищожени единици на защитника за отделните команди е: 4 + 0 + (5 + 6) = 15. Тъй като в края на атаката защитникът няма оставащи солни мини, сумата се удвоява и става 30 – съответно резултатът на атакуващия алгоритъм за този тест е 30.

 

Примерен вход	Примерен изход
8 mine 2 2 mine 3 2 chickens 30 2 1 chickens 30 3 1 chickens 34 1 2 chickens 34 4 2 chickens 30 2 3 chickens 30 3 3	bomb 2 3 2
Обяснение:Защитникът е изразходил всичките пари като е скупчил голямо количество пилета, защитаващи 2 солни мини. Атакуващия пуска бомба с радиус 2 върху едната солна мина, като този радуис е достатъчен, при тази подредба на единиците на защитника, да унищожи всички единици. Общата цена на унищожените единици е 200 и поради липсата на оцелели мини, тази сума се удвоява и става 400 – съответно резултатът на атакуващия алгоритъм за този тест е 400.

Приложна задача – имплементация на “Големи бомби”

Напишете програма, която дава възможност да се извършват всички дейстия от задачата “големи бомби”. Програмата трябва да приема потребителски вход, който описва полето на защитника – като това може да става чрез текстов файл или въвеждане от клавиатурата на входни данни, или по друг начин – включително графичен потребителски интерфейс. Същото важи и за командите на атакуващия. В допълнение, програмата трябва да визуализира провеждането на цялата битка и резултатите от нея, като дава възможност за запазване на резултати и после визуализиране на тези резултати. Визуализацията може да бъде базирана на генериране на HTML файлове, които да се отварят през браузър, както и да ползва някоя друга технология, например печатане на ASCII символи върху конзолата, графика с OpenGL, DirectX, XAML, или каквато и да било друга платформа, позволяваща визуализация (включително и конзолна визуализация при желание).

Обобщено, приложението трябва да поддържа:

• Въвеждане на единиците на защитаващия се
• Въвеждане на командите на атакуващия
• Визуализация на битката
• Визуализация на резултати
• Възможност за запазване на резултати и преглеждане на таблица с резултати на играчи – т.нар. scoreboard, hall/wall of fame и т.н.

Начинът на имплементация и технологиите, които могат да бъдат ползвани не са строго определени, с цел участниците да имат свобода и да проявят творчество и оригиналност. Възможно е добавяне на нови функционалности в приложението, както и добавяне на нови видове единици и възможности в правилата на “Големи бомби”, стига да остава възможността да се ползват изискваните функционалности и да важат зададените правила (било то като има различни режими или друго решение).

Приложението може да бъде уеб, десктоп, както и WinRT-базирано. Единственото ограничение е да бъде изпълнимо под Windows 7 или Windows 8 и да бъде предоставен лесен начин за стартирането му в папката application.

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

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

При оценяването ще бъдат генерирани тестове от журито, с различни подредби на единици на защитаващия се играч. Освен това, ще бъдат ползвани коректните тестове пратени от участниците. Тежестта ще бъде 50 на 50, тоест тестовете на журито ще носят общо толкова точки, колкото общо тестовете предадени от участниците.

• Данните от всеки тест на журито, както и данните от всеки тест на участниците, ще бъдат подадени на всеки един предаден алгоритъм.
• За всеки тест ще се намира най-добрия резултат на алгоритъм и той ще получи максималните точки за този тест, а останалите ще получат съответния процент от тези точки за този тест (т.е. скалирането се извършва за всеки тест).
• Например, ако за задачата има 10 теста от които 5 са на състезатели и 5 на журито, то всеки ще носи по 1 точка.
  • Ако на първото поле най-добре представилият се алгоритъмът G има резултат 30
  • алгоритъмът M има резултат 15,
  • а алгоритъмът L има резултат 10, то
  • в крайна сметка точките за този тест са:
    • G: 1 точка
    • M: 0.5 точки
    • L: 0.33 точки
• По същия начин се оценяват всички тестове, точките се сумират и след това се закръглят до цяло число
• Максимални точки в крайното класиране за алгоритмичната част: 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.

Краен срок

Краен срок за предаване на решения: 25 февруари 2013 г, 23:59:59 часа.

Решенията се предават в студентската система на Академията на Телерик, на адрес http://telerikacademy.com/Courses/Courses/Details/13 според инструкциите, описани в раздела “Качи решение” на официалния сайт на състезанието.