сряда, 3 февруари 2010 г.

Факултет по Магически Изкуства

Представям на вашето внимание извадка от трисеместиалния курс на студентите във Факултета по Магически Изкуства наречен "Супергероизъм" воден от ред известни супергерои.
Конкретната извадка е подготвена(според слухове) от небезизвестен ФМИистски джедай-падуан-програмист-супергерои, смятан от някои за гений, а от други за средностатистически алкохолик:


Цивилизованият свят има нужда от вас!
Директорът на болницата "Свети Бог" доктор О. Болиии е решил да инвестира в модерна изцяло електронна система за извършване на операции. Чифт механични ръце извършват самата операция, а хирургът само им казва от време на време да го карат по-внимателно с ножовете, че не са евтини.
На фирма "е.т. Зорнитса" е възложена задачата да напише софтуера за това чудо на техническата мисъл. Проблемът е, че машината борави с много, много информация, а трябва да работи много, много бързо. Решението е, разбира се, някаква структура от данни, която да поддържа много бързи операции Insert, Find и Delete.
Нещо подобно:
И, тъй като никой, никога не е правил нещо подобно, на вас се пада честта да имплементирате първата в света Хеш таблица.
Но, тъй като системата трябва да е много, много(много!) бърза, само това не е достатъчно. Трябва да напишете и една-две оптимизации. Шефът ви(Зорнитса) мисли, че следната идея би била необходима:
Разбира се, може и по много други начини да се забърза. Важно е накрая да работи добре и да не бъде отрязан нечий крак по погрешка, защото ще трябва да плащате неустойки. От собствените си крака.

Можете да приемете, че съществува (глобална функция / клас / метод / каквото там решите), която да се грижи за самото хеширане.
Тоест, имате функция от вида: int hash(HashTable& table, T& element)
Която съпоставя число на елемент от някакъв шаблонен тип.
Можете да приемете и, че за основни типове(int, string, pair) тази функция има някаква разумна имплементация.
И под "Можете да приемете", се има предвид "Трябва да напишете".


Wish upon A* 
Михаир е толкова щастлив днес! Той най-после успя да сглоби своя супер-хипер-мега як робот, съставен изключително от скъсани контролни по СДП и опаковки от вафли Мура. Този робот, известен още като Станчо, притежава завидни умения в областта на унищожението с лазери и мачкането на хора. За нещастие, Михаир не е прекалено добър в програмирането и още не е успял да накара Станчо да се придвижи повече от три крачки без да падне на земята. Трябва да се направи Pathfinding Algorithm за Станчо. Това е вашата задача.
Според Михаир следният алгоритъм би трябвало да свърши достатъчно добра работа:
http://en.wikipedia.org/wiki/A* ...но какво ли разбира той.

Дадена е правоъгълна матрица с размери NxM. Това е разхвърляната стая лабиринтът, върху което се движи Станчо.
Всяко поле от матрицата е число от -2 до 10.
Ако числото е -1, то това поле е напълно непроходимо.
Ако числото е -2, то това е вход / изход от лабиринта. Ще има точно две такива.
Иначе, числото показва колко секунди ще отнеме на Станчо да мине през това поле.
Интересува ни за колко най-малко време се стига от входа до изхода. И по какъв точно път. Представете си нещо такова:



Само че с по-малко цветове и много повече нули и единици.


Тежък ден за чичо Харалампий

Напук на икономическата криза, днес Данон са пуснали промоция на киселото мляко. Това са добри новини за чичо Харалампий, който е собственик на кварталния супермаркет - ще продаде много. Ноо се оказало, че вграденият радар за промоции на всяка една бабичка в близките 30 морски мили усетил промоцията и те се наредили пред магазина. Отдалече се вижда всяка бабичка по колко кофи мляко може да носи, а всяка кофа мляко(5.3 кг) се маркира на касата за по 10 секунди. Има огромна опашка от N бабички и много по-малко количество касиерки(а именно - K, номерирани от 1 до ... ами K). Всяка бабичка, когато дойде нейният ред, иска да знае на коя каса има най-къса опашка, че да се нареди на нея. Ако има няколко еднакви възможности, тя ще иска да се нареди на най-близката каса(т.е. тази с най-малък номер). Всяка бабичка, естествено, пита Харалампий. Той трябва да знае. Той трябва да знае!

Вашата задача, ако решите да я приемете, е да създадете софтуер, който казва на Харалампий каквото му трябва да знае.
Програмата трябва да приема първо две числа:
N и K, N < 1000000, K < 1000
След това, приема още N числа - броя кофи мляко, които ще си купи всяка бабка.
Връща N числа в интервала [1, K] - на коя каса отива всяка бабичка.

И ако си мислите, че сложност O(N*K) е приемлива - вие очевидно не сте виждали разярена софийска бабичка.
И ако си мислите, че такива неща като STL са много хубави - е кофти шанс, защото Харалампий не е и чувал за тях и в неговия компилатор тези неща ги няма.
От пусто в празно.
Истрен получил за рождения си ден комплект от N еднакви колби. Всяка колба(i) е свързана със следващата(i+1) с точно една хоризонтална тръбичка(една пренебрежимо малка тръбичка) на определена височина( h_i ).
И понеже Истрен си е малко гламав, започнал да налива вода в дупката. Налял той H милиметра вода в първата колба. Водата, разбира се, се разпределила в съседните стъкларии според разните му там физични закони.
И сега Истрен много го сърби да разбере по колко точно вода има във всяка колба. Стига му да знае с точност до 0.0001мм. Можете да приемете, че колбите са мнооооого високи и никога няма да прелеят.

Дадени са числото N и числото H.
След това са дадени N-1 числа, като i-тото от тях е h_i.
N е по-малко от 100.

Пример(лесен):
2 8
3

Отговор:
4 4

За нещо такова става въпрос:

Няма коментари: