Musala Soft and PC Magazine Bulgaria

Конкурс по програмиране на Musala Soft и PC Magazine Bulgaria

Състезателна система

Задача 5 от брой 2/2001 - ЛАБИРИНТЪТ НА КЪСМЕТА

Условието на задача 5 можете да изтеглите от тук (RTF Format).

Коментари по условието на задача 5:
Журито на конкурса се извинява за следната допусната неточност в условието на задачата: В условието е зададено следното ограничение за броя на хората в лабиринта K:(1<=К<=N*N). Ограничението, което вашите решения трабва да удовлетворяват е (1<=К<=(N+1)*(N+1)).

Класиране :

Място	Име	Град	Точки
1	Николай Николов	Ямбол	17
2	Трендафил Трифонов	Велико Търново	15
3	Николай Чилев	София	12
3	Стоян Йорданов	София	12
5	Петър Кормушев	Пазарджик	10
5	Петър Събев	Русе	10
5	Свилен Колев	София	10
8	Владимир Молотков	София	8
8	Петко Минков	Пловдив	8
8	Тихомир Тодоров	Велико Търново	8
11	Валери Цеков	Грамада	6
12	Камен Добрев	София	4
13	Владимир Недев	Варна	2
13	Деян Ламбов	Пловдив	2
13	Димитър Димитров	Добрич	2
13	Петър Петров	София	2
17	Екатерина Георгиева	Русе	0

-	Владимир Молотков (закъсняло решение)	София	12
-	Ивайло Бадинов (закъсняло решение)	Силистра	8
-	Стефан Минков (закъсняло решение)	Габрово	0

Пълното класиране по тестове можете да видите тук .

Тестовете:
Тестовете, въз основа на които журито е формирало класирането са достъпни за всички. Можете да ги вземете от тук (ZIP Format) .

Коментар по решението и резултатите на участниците:
Очевидно задача 5 от конкурса затрудни участниците - това споделиха и самите те в писмата си. Нито едно от изпратените решения не решаваше задачата напълно, на което се дължи и липсата на участник с максимален брой точки. Шампион на кръга с 17 точки е Николай Николов от Ямбол, чиято програма не успя да реши вярно само последния тестов пример. Втори се нареди Трендафил Трифонов от Велико Търново с 15 точки, а трето място си поделят софиянците Николай Чилев и Стоян Йорданов с по 12 точки. Най-често използваният подход от участниците при решаването на задачата е да се плануват пътищата за бягство един по един, като се спазва някакъв принцип на движение - примерно винаги да се избира най-прекия път до повърхността. Тази идея не е лоша, но в повечето случаи вместо до оптималния отговор, води до отговор близък до него. Друг използван подход е да се направят всички възможни пътища за всички затворници и да се изберат тези, които водят до оптималното решение. С този алгоритъм, винаги ще получаваме правилен отговор, но когато размерът на куба стане голям, програмата работи твърде бавно и не се вмества във времевия лимит. Един начин да получим коректен и ефективен алгоритъм за решаването на тази задача е свеждането й до поток в мрежа - това е и идеята, която ще намерите описана в решението на журито.

Алгоритмичният анализ на задача 5 можете да прочетете тук (RTF Format).

Участници (по дата и час на последното получено решение):
1. Тихомир Тодоров - Велико Търново - 05.03.2001, 20:44
2. Валери Цеков - Грамада - 08.03.2001, 14:23
3. Владимир Недев - Варна - 12.03.2001, 22:21
4. Петър Събев - Русе - 13.03.2001, 13:16
5. Петко Минков - Пловдив - 13.03.2001, 21:15
6. Свилен Колев - София - 14.03.2001, 18:19
7. Екатерина Георгиева - Русе - 15.03.2001, 11:33
8. Камен Добрев - София - 15.03.2001, 15:59
9. Николай Чилев - София - 15.03.2001, 18:30
10. Трендафил Трифонов - Велико Търново - 15.03.2001, 18:45
11. Димитър Димитров - Добрич - 15.03.2001, 18:52
12. Стоян Йорданов - София - 15.03.2001, 21:18
13. Владимир Молотков - София - 15.03.2001, 23:17
14. Деян Ламбов - Пловдив - 15.03.2001, 23:35
15. Петър Кормушев - Пазарджик - 15.03.2001, 23:47
16. Петър Петров - София - 15.03.2001, 23:50
17. Николай Николов - Ямбол - 15.03.2001, 24:00
18. Стефан Минков - Габрово - 18.03.2001, 12:13 ---> закъсняло решение
19. Ивайло Бадинов - Силистра - 18.03.2001, 20:47 ---> закъсняло решение
20. Владимир Молотков - София - 19.03.2001, 19:07 ---> закъсняло решение

Решенията на всички участници:
За да може всеки лично да се убеди защо класирането е такова и защо има X, а не Y точки, публикуваме всички изпратени решения заедно с изходните кодове на всички програми (с изключение на тези, които пожелаха сорсът им да не се публикува). Можете да ги разгледате от тук (ZIP Format). За всеки участник е създаден и един .log файл, който отразява как са преминали тестовете върху програмата му. Въпросният .log файл се дава само за да добиете представа защо получавате точките, които са ви дадени, но не винаги отразява точната причина за провала на тестовете. Имайте предвид това.

Контестации:
Контестации могат да се подават от всички участници, стига да са основателни . Ще се разглеждат само претенции на участници, които са оценени неправилно в резултат от грешка на журито. Моля преди да изпратите контестация, внимателно прочетете условието на задачата за да прецените дали тя е основателна. Журито ще отговори на всички ваши въпроси, свързани с оценяването. Можете да ни пишете на адрес: konkurs@sagabg.net.

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

Supported by Musala Soft Ltd.