5. Penguin Airlines C# Advanced изпит


1
Здравейте колеги! Искам да споделя с вас решението си (макар и не за 100т) на една много весела задача. Това е решение писано за 5 мин. изпратено послената минута (буквално), за мое голямо учудване то изкара 44т. Много съм любопитен вие как сте я решили :)



Отговори



1
Аз се опитах с една таблица така: линк, но без резултат. Очаквах, че може да има тестове само с едно прекачване, обаче уви, само нулевите тестове минаха. Предполагам, че може да се реши по моя начин с някаква рекурсия, но това е непозната територия за мен :)

от ZachD (273 точки)


2
За 100 точки задачата се решава с графи и по-точно с алгоритъма Union-find.

от kon.simeonov (5238 точки)


0
Или bfs, dfs, или друго, само дето не на всяка заявка.

от cuki (7696 точки)


2
Моето решение, което е подобно на колегата evilshadow. За 3-я вариант пускам един BFS, който явно върши работа, но не и за зададеното време. 4 теста ми гърмяха за време. А въпросният union-find алгоритъм ... доста адекватен звучи за обучаващи се във 2ри курс по програмиране.    

от pecata (114 точки)


1
Миналата година, 5-та задача беше с топологично сортиране. Този тип задачи винаги са били такива и целта им е да направят диференциация между студентите. Задачите се дават, не за да ги решите, а за да се сблъскате с проблем, който не сте решавали до момента и да се чувствате предизвикани. Според вас има ли смисъл да дадем задачи, на които масово ще изкарате по 500 точки?

от INKolev (4141 точки)

0
Pecata, според мен Коцето го каза с идеята да знаем как се решава, а не че са очаквали да го решим по този начин.
Както Ванката написа идеята е да има предизвикателство и така да се научим да мислим outside of the box както се казва.

Иначе поздравления за резултата , който си изкарал :)