Задача #5 от конкурса по програмиране - Къртим мивки, лепим плочки


10

 

Здравейте колеги,

Вече е публикувана задачата за 5-ти кръг на конкурса. Можете свободно да дискутирате задачата, без да споделяте конкретни решения и код.

Условието, както обикновено, е на сайта на конкурса: 

http://konkurs.pcmagbg.net/task-5-season-2012-2013/

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

Тези дни ще се ангажираме и с обновяване на генералното класиране - обещаваме го отдавна, но все не остава време. Вече е крайно време и ще го свършим тези дни.

Поздрави,

Жоро




Отговори



0
Бай Иван няма да направи повече от 85 410 крачки.

от silistra (561 точки)


3

Здравейте колеги :)

Лично аз подходих доста безотговорно към задачата - отделих около 3-4 часа в неделя и единственото, което скалъпих беше едно BFS, което се пуска за всяка плочка, която първоначално се е застъпвала с друга, вече поставена. Чрез това обхождане на съседните клетки си осигурявам, че разстоянието, което Бай Иван ще измине е минимално. Дали обаче е най-ефективното място за поставяне на плочката е друг въпрос... и честно да си призная има случаи, в които изминаването на няколко крачки повече ще осигури по-плътно запълване на пространството и по-малко крачки като цяло...
Ще се радвам да се запозная с нечие решение, което решава този и евентуално други, по-сложни проблеми, които са изникнали в последствие...

Поздрави,

Пирин

Edit: забравих кода... 


от pirin (1101 точки)


3

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

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

Хубавото е, че дори не се наложи да оптимизираме. Алгоритъмът свършва работа за 0,2 сек, дори при 1000 елемента.

КОД


от krasi.nikolov (1412 точки)


0
Това което си направил, може да даде 5-10% по добри резултати за много елементи и евентуално доста по добри за малко елементи. Честно казано, просто времето не стига и затова оставихме първото нещо което работеше. Проверих едно запълване на полето и оставаха не повече от 5-10% празни полета, а това е основен признак за ефективност.

от krasi.nikolov (1412 точки)


1

https://github.com/nader-dab/CSharp-Homeworks/tree/master/PC-Magazine/BreakingSinks

При нас алгоритъма се опитва да постави всяка фигура на първоначалните й координати, в реда в които са постъпили на входа. Ако фигурата се застъпва с друга, увеличаваме разстоянието за преместваме и започваме да въртим всички позиции с този брой стъпки водейки се по circles in taxi cab geometry логиката:

 http://en.wikipedia.org/wiki/Manhattan_distance

Поставяме фигурата на първата свободна позиция.

За приложната част не ни остана време :<

 


от nader.dabour (546 точки)


2

Ето това е нашата приложна част, не е кой знае какво, но поне е правена с желание и интерес 


от kaobg (212 точки)


2

Eeeeeeeee верно ли? Последен кръг... много жалко.... :)

Ето решението ни за този :


С колежката Рали Никифорова заложихме на онлайн приложение със възможност за игра за двама. Използвали сме signalR като свръзка, JS за клиенстката част и C# за сървърната.
Играта върви едновременно и на сървъра и при клиента, за да няма чийтове от страна на клиента. Всичко се валидира от сървъра според неговата инстанция на играта.
http://sinkbreaker.apphb.com/

Много ми е интересно видях, че има алгоритъм за 0,2 секунди, трябва да разгледам как сте подходили. Моя свършва за 1.8сек в най-лошия сценарии - 1000 квадрата на позиция 1 1. Фигурите ги обработвам веднага щом се подадът, не чакам да се застъпят.

Ето го кода за алгоритъма:
https://sinkbreakeralgo.codeplex.com/SourceControl/latest

 


от KOCTEHYPKATA (5259 точки)


0
Остава още един - финалния присъствен - но на него ще влязат само първите 30 отбора от генералното класиране (в момента има такова до 4 кръг), като спрямо резултатите до момента, първите 14 отбора влизат гарантирано.



1

Много готин конкурс...Исках да участвам още от самото начало...но нямах никакви познания...Сега вече понатрупах малко и се пуснах...За първи път в конкурса....за първата ми рекурсия в живота..представям ви сорса на Бай Иван, както и неговия скромен UI...за напред повече...

Браво колеги, страхотни решения! Де да имаше малко повече време, може би щяха да лъснат още по красиви неща...сигурен съм... :) Успех на всички!

Отбора: Николай Желязков и Румен Тонев


от zhelyazkovn (2949 точки)


0
Олеее да е.... :Д еми бяха късните часове... :D объркани са ми тези фигури :Д еми, нищо здраве да е... Благодаря ти за коментaра... :) (y)

от zhelyazkovn (2949 точки)