Musala Soft Logo Конкурс по програмиране на Musala Soft и PC Magazine Bulgaria PC Magazine Bulgaria Logo
  Състезателна система
Сезон 2010 - 2011
Сезон 2009 - 2010
Сезон 2008 - 2009
Сезон 2007 - 2008
Сезон 2006 - 2007
Сезон 2005 - 2006
Сезон 2004 - 2005
Правила
Задача 1
Задача 2
Задача 3
Задача 4
Задача 5
Задача 6
Класиране
Финален кръг
Сезон 2003 - 2004
Сезон 2002 - 2003
Сезон 2001 - 2002
Сезон 2000 - 2001

Задача 3 от брой 12/2004 - ПОДАРЪК - Анализ


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

Да разделим задачата на две – първо да разберем къде сме в момента, след което да се придвижим възможно най-бързо от текущата си позиция до целта. Втората част се реализира лесно използвай алгоритъм намиращ най-късите пътища от целта до всички позиции на картата (например, алгоритъм на Dijkstra за най-къси пътища в граф от един връх до всички останали). Така, когато разберем къде сме били в началото и съответно къде сме сега, ще можем веднага да се придвижим по най-късия възможен път от текущата позиция до целта. Сега остава да разберем началната/текущата позиция – двете са взаимно определящи се, защото поредицата от направени ходови ни дава как сме се изместили спрямо началната позиция и съответно как да се върнем до нея, ако знаем текущата.

Нека да приемем, че търсим къде е текущата позиция в картата. За целта поддържаме списък с възможните текущи позиции – отначало това са всички проходими полета, които имат същата околност като тази, която се „вижда” около началната позиция. На всяка стъпка избираме посока, в която да се движим, гледайки попътните неизвестни позиции. Гледането не ни струва нищо и няма причина да не видим какви са неизвестните позиции около нас, защото те увеличават нашето знание за картата, а от там и възможността да определим текущата позиция. Изборът на посока, в която да се движим, зависи от реализирания алгоритъм (или комбинация между тях). Може да изберем:

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

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

Ето накратко идеята на Ростислав Руменов, заел второ място на 0.741 точки от победителя: „След като прочета картата, знам какво съдържа тя. После за всяка клетка която не е "нула" намирам минимално време, за което ще се стигне до партито. След това правя нещо като вълна, в която първоначално са всички клетки и на всеки ход на вълната след като огледам терена премахвам някои от тези клетки и така поддържам списък с възможни местоположения, който все повече и повече намалява. Изборът на ход правя като вземам някое от възможните местоположения и избера посоката, с която най-бързо ще стигна до партито, като си отбелязвам клетки, през които съм минал защото не е рационално да минавам пак през тях.”

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

Карта 1. Карта с 5 идентични стаи. Тъй като за три от стаите верният път е наляво, а за две – надясно, логично би било решенията да тръгнат първо наляво. Отново, тъй като за три от стаите верният път е нагоре, а за 2 – надолу, програмите трябва да тръгнат нагоре. Решенията на голяма част от участниците успяха да намерят оптималния път за достигане до целта.

Карта 2. Карта с 8 идентични стаи. Тук само решението на Ростислав Руменов намери оптималния отговор, останалите решения се представиха минимум два пъти по-зле.

Карти 3 и 4. Целта на тези две карти беше да се провери доколко участниците правят предварителен анализ на картата. Вижда се, че има три еднакви стаи, които се различават само с едно квадратче. Ако някой състезател тръгне първо надолу и програмата му работи детерминирано, т.е. за еднакви входни данни получава еднакви изходни данни и няма елемент на случаен избор, то той ще загуби време. Причината затова е че тест 3 и тест 4 представляват еднакви карти, но с различни начални и крайни позиции. По този начин ако след като състезателят е вървял надолу той тръгне надясно, ще получи добър отговор на единия, но слаб на другия, и обратно. Затова, с цел да се спести време, една “умна” програма би трябвало да анализира картата около себе си, а именно да разбере в коя от трите стаи се намира чрез ходове наляво и един ход нагоре. След това, използвайки алгоритъм на Dijkstra, да намери най-краткия път до целта.

Карта 5. Празна карта. Резултатите варираха от 255 до 951, но никой състезател не намери най-доброто решение.

Карта 6. При тази карта липсва моментът на определяне на местоположението по картата, защото Мечо Пух се намира в квадратче, чиято околност е уникална. Така остава само да се изпълни алгоритъмът на Dijkstra, с които да се определи оптималният път до партито. Въпреки това имаше програми, които не намират оптималното решение.

Карта 7. Един малък квадрат 3 на 3 е размножен 3 пъти по хоризонтална и 3 по вертикала, формирайки квадрат 9 на 9. Този квадрат е размножен много пъти по случаен начин върху картата, а партито се намира в долния десен ъгъл на картата. Тук има два подхода за решаване – първо да се определи местоположението на Пух и после да се изпълни алгоритъма на Dijkstra, или направо да се тръгне към партито, т.е. да се върви винаги надолу и надясно, понеже следвайки тази логика със сигурност ще се стигне до целта ( както се вижда, по картата няма препятствия).

Карта 8. Също както на карта 7 е получен квадрат 9 на 9, от който после е получен един по-голям правоъгълник, който пък е размножен много пъти. Така по картата има много еднакви участъци. Тук само програмата на Васил Жеков единствена дава далеч по-добър отговор от програмите на останалите състезатели.

Победител в кръга е Деян Чакъров от София с 82.454 точки. Честито!


За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.

Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.