XIV конкурс по програмиране на PC Magazine Bulgaria и Мусала Софт

Кръг на Факултета по математика и информатика

В този брой на сп. PC Magazine Bulgaria стартира втори кръг от четиринадесето издание на най-елитния частен конкурс по програмиране в страната, организиран съвместно от списанието и фирма Мусала Софт. Вторият кръг на конкурса се провежда с подкрепата на Факултетa по математика и информатика (http://www.fmi.uni-sofia.bg/) към Софийският университет „Св. Климент Охридски” (най-старото и най-авторитетно висше учебно заведение в България, утвърдило се като световноизвестен научноизследователски център в областта на природо-математическите и обществените науки) е отговорен за обучението и изследванията в областите Математика, Приложна математика, Компютърни науки, Информационни технологии и Софтуерно инженерство. ФМИ има над 2500 студенти и аспиранти, 15 катедри и допълнителни помощни секции (компютърни лаборатории и т.н.).

Маниашка писта

Цяла есен гората поемаше безспирните дъждове, идващи като знак за нови предизвикателства за Мечо Пух и приятелите му. За нещастие обаче скромното мазе на Мечо, което беше пълно (всъщност препълнено) с гърненца мед, се наводни и медът толкова се разреди, че по-скоро бе се получила медовина, която дори Мечо отказваше да пие поради ниското съдържание на фруктоза и захароза. Освен това подпочвените води от проливните дъждове издълбаха множество тунели, част от които се оказа, че свързват мазетата на голям брой животни, членуващи в Международната Експериментационна Чудотворна Организация под Егидата на Програмистите на Интегрални Чипове. Предизвикани от съдбата и с угризения на съвестта заради целия похабен мед, Мечо и приятелите му са решени да започнат изграждането на дълго планираната бобслей писта в гората. Вече разполагащи с тунелите, които ще се използват за улеи в пистата, проблем остава само липсата на лед... Но какво е някакъв си лед за животни с толкова мед?! Разредените от дъждовете медове са готови да бъдат използвани за смазващо вещество по всеки от така наречените „мед-слей“ улеи. Поради различните физични характеристики, на всеки вид мед съответства стойност M, показваща „маниакалността“ на улея, смазан с този вид мед. А „интересът“ към един улей зависи от това колко общо улея, смазани със същия вид мед, започват от или завършват в някое от мазетата, свързани от улея. Целта е така да се смажат улеите с различните видове мед, че да се максимизира сумата на произведенията на маниакалността и интерес за всеки улей.

На първия ред на входния файл maniac.in са записани естествените числа N, М и K (N<=400, М<=10000, K<=30), съответстващи на броя на мазетата, броя на улеите и броя на видовете мед. На втория ред са записани K на брой естествени числа от интервала [1;100], задаващи маниакалността за медовете 1,2,...,K. На третия ред са записани 2N-3 на брой естествени числа в интервала [1;100] – интереса към улей, смазан с мед, използван в 1,2,...,2N-3 на брой улея, започващи или завършващи в едно и също мазе. Следват М реда с по две числа A и B (1<=А,B<=N), показващи съответно от кое мазе започва и в кое мазе завършва поредният улей. Между никои две мазета няма повече от един улей и няма улеи, свързващи едно и също мазе.

В изходния файл maniac.out запишете M на брой реда. Всеки ред трябва да съдържа номера на меда, използван за смазване на поредния улей. Номерацията започва от 1 и съответства на подредбата на улеите във входния файл.

Примерен вход:
5 7 2
10 20
50 10 100 0 5 10 0
1 2
1 3
1 4
2 3
2 4
3 4
4 5

Примерен изход:
2
1
1
2
2
1
1 

Коментар по изхода:
Използваме мед #2 за улея (1,2), мед #1 за улея (1,3) и т.н.

Броят на улеите, смазани с мед #2, започващи или завършващи в някои от мазетата 1 или 2, са 3 на брой: (1,2), (2,3), (2,4). Това значи, че интересът към този улей е 100. Маниакалността на мед #2 е 20, откъдето маниакалността на улея (1,2) е равна на 20*100. Маниакалността на улей (1,3) е 10*100. Маниакалността на улей (1,4) е 10*0. Маниакалността на улей (2,3) е 20*100.
Маниакалността на улей (2,4) е 20*100.
Маниакалността на улей (3,4) е 10*0.
Маниакалността на улей (4,5) е 10*100.
Сумата на произведенията на маниакалността и интереса е 20*100+10*100+ 10*0+20*100+20*100+10*0+10*100.

Крайният срок участие във втория кръг е 10 декември. Решения на задачата се приемат през сайта http://konkurs.musala.com/