Проектиране и Анализ на Компютърни Алгоритми

Теми на курсовите проекти

Версия 0.83

Изисквания

Всяка задача трябва да бъде реализирана на един от програмните езици C, C++ или Java и да се компилира на един от следните компилатори:

· Microsoft Visual C++ 7.1 (VS.NET 2003).

· Sun JDK 1.4.

· GNU Compiler Collection 3.3 (под Debian Linux)

Предава се архивен файл (на някой от популярните компресиращи програми), чието съдържание е описано по-долу с име факултетния номер на студента с формат:

fn<факултетен номер>_<име на проблема>.<разширение на архива>

Пример: fn42870_maxpath.zip.

Архивът трябва да не съдържа директории и да съдържа единствено:

· Сорс кода на вашата програма – трябва да бъде именуван със съответното име на проблема плюс стандартното разширение за съответният език (например maxpath.cpp). Поради спецификата на изложените проблеми се позволява да се използва само един файл с код. Изключение правят интерактивните програми (с визуализация) за които ще е позволено да имат повече от един файл с код и поради факта че ще се тестват ръчно.

· Проектен файл, или скрипт който да компилира кода в зависимост от използваните средства за разработка.

· Изпълним файл.

· Документация на задачата по шаблон.

· 3 примерни теста, които показват, че вашата програма работи правилно. Тестовете трябва да се състоят от номерирани двойки входен + изходен файл и да спазват изискванията за формата на входа и изхода. Имената на примерните тестове трябва да са като имената на входния и изходния файл за съответната задача, но с добавен номер след тях (напр. за задача "perm" това трябва да са файловете perm1.inp, perm1.out, perm2.inp, perm2.out, perm3.inp и perm3.out). Вашите примерни файлове могат да бъдат използвани за тестване на решенията на ваши колеги., така че не трябва да са тривиално лесни.

Изискванията за самата програма

· Да решава точно и единствено зададената задача, без да извършва други действия (например да променя системният часовник, да чете/пише от/по екрана или изтрива файловете от текущото устройство).

· Да спазва стриктно формата на входните и изходните данни.

· Да бъде написана четливо. Сорс кодът трябва да е лесен за разбиране и проследяване как работи. Това съответно означава да се именуват променливите и подпрограмите с подходящи имена, да се слагат коментари на местата с тежка логика, кодът да се подравнява (форматира) по подходящ начин, сложните подпрограми да се разделят на няколко по-прости, да се пише по най-много от 1 израз на ред и т.н.

· Предложеният изпълним файл да може да се получи от предложения сорс код при компилацията му с използване само на стандартните за компилатора библиотеки (да не се използват нестандартни библиотеки). Използването на стандартни библиотеки се позволява само за задачи над 25 точки, включително.

· Да генерира винаги еднакъв изход при еднакви входни данни (ако се използва генератор на псевдослучайни числа, трябва да се внимава да се генерират винаги еднакви редици от числа).

· Изходът, който се генерира да е резултат от изчислителен процес, реализиран в програмата. Не е позволено програмата просто да отпечатва някакви предварително изчислени данни (например ако задачата има малко възможности за входни данни).

· Да чете точно и единствено от файла с входните данни за съответния проблем (например maxpath.inp) и да пише единствено във файла с изходните данни (например maxpath.out) в текущата директория. Четене и писане от други файлове и директории не се позволява (включително и използването на временни файлове).

· Да използва не повече от 64MB оперативна памет.

Преподавателския екип и университета имат право да използва кода на проекта за образователни и научни цели, включително да го публикуват и модифицират.

Не се разрешава директно използване на чужд сорс код от книги, статии, Интернет или други източници! Позволено е използването на алгоритми от всякакви източници, стига студентът да ги разбира в детайли и да е написал сорс кода на програмата си собственоръчно от първия до последния ред. При установяване, че даден студент не разбира достатъчно добре собствената си програма или използвания в нея алгоритъм, работата му ще бъде анулирана!

Преподавателският екип ще оценява единствено програми които спазват стриктно правилата описани по-горе. Особено важно е да се спазват стриктно имената и форматите на входните и изходните файлове (поради автоматизирания процес на тестване, който ще бъде приложен).

Преподавателският екип ще санкционира студенти, които не спазват указаните или подразбиращите се изисквания – при злонамерени действия породени от вашите програми виновните ще се наказват по административен път.

Разпределението на задачите е публикувано на сайта на курса. Всяка задача е оценена по трудност с число – максималният брой точки който може да се спечели от нея. Посоченият брой точки за задачата е максимален и ще бъде присъден само ако решението е наистина правилно и достатъчно ефективно. За неоптимални решения ще се дава частичен брой точки. Студент, който е решил правилно задачи за над 30 точки може да получи най-много до 30 точки.

Условия на задачите

Задача 1. Cocktail – Коктейл на катедрата – 10т.

Катедрата на Станчо често организира коктейли заради научните й успехи. Интересното за неговата катедра е, че всички от нея са големи ценители на минералната вода. Станчо също не прави изключение. За всеки коктейл той има план за това каква минерална вода и в какъв ред трябва да пие. На масата са наредени разнообразни марки минерална вода (може да се повтарят). Тъй като членовете на неговата катедра имат проблем с обръщането, особено когато употребяват минерална вода, Станчо може да се движи само от ляво надясно. За да не прави лошо впечатление, той не иска да налива от една бутилка повече от веднъж. Освен от минералната вода Станчо се интересува и от комбинаторика. За това той иска да разбере по колко начина може да изпълни плана си за текущия коктейл. Понеже обикновено в разгара на такива коктейли Станчо губи голяма част от математическите си способности, той се нуждае от програма, която да реши задачата.

Входни данни:

Входните данни са дадени в текстов файл с име cocktail.inp. На първия ред от файла има някаква последователност от букви от ‘a’ do ‘z’ представляващи съкращения на видовете минерална вода наредени по масата от ляво надясно ( т.е. всеки вид минерална вода се представя уникално с малка латинска буква). Вторият ред също се състои от малки латински букви представляващи програмата на Станчо за тази вечер. Дължината на никой от низовете не надвишава 1000 символа.

Резултат:

Резултатът трябва да се запише в текстов файл с име cocktail.out. На единствения ред от изходния файл трябва да се запише броят на начините, по които Станчо може да реализира програмата си, ако се движи само от ляво на дясно и налива от всяка бутилка най много по-веднъж. (Ако не може да реализира програмата си, този брой трябва да е 0).

Примерен входен файл:

aabbab

Примерен резултатен файл:

Задача 2. Perm – Пермутации – 10т.

Дадено е мултимножество M. На различните му пермутации са съпоставени естествените числа 0, 1, 2... в съответствие с лексикографската им наредба. Да се проектира и реализира ефективен алгоритъм, който по дадено число P намира P-тата по лексикографски ред пермутация на мултимножеството M. Да се оцени сложността на алгоритъма в средния и в най-лошия случай.

Входни данни:

Входните данни се задават в текстов файл с име perm.inp. На първия ред на входния файл стои едно число K – брой пермутации, които програмата трябва да възстанови по поредния им номер (1 ≤ K ≤ 1000). Следват K двойки редове. На първия от всяка двойка има две цели числа N и P, разделени с интервал (1 ≤ N ≤ 12). На втория ред има N числа разделени с интервал описващи зададеното мултимножество.

Резултат:

Резултатът трябва да се запише в текстов файл с име perm.out. Файлът трябва да се състои от точно K реда. На всеки ред трябва да има по една пермутация съответстваща на указания й номер във входния файл, записана като последователност от числа, разделени с интервал.

Примерен входен файл:

4 0

1 2 3 4

3 1

1 2 3

6 718

1 2 3 5 6 4

5 2

1 2 1 2 1

Примерен резултатен файл:

1 2 3 4

1 3 2

6 5 4 3 1 2

1 1 2 2 1

Задача 3. Family – Родословно дърво – 10т.

Родствени връзки на планетата ФМИ са доста объркани. Те се събират в групи, така че фмитяните могат да имат както един, така и десет родителя и никои не е учуден от стотина деца. Фмитяните са свикнали с техния начин на живот, и го намират за много естествен, но в планетарния парламент това объркано родословно дърво води до объркване. Там се събират най-достойните фмитяни и затова, за да не се засегне някои по време на дискусии е решено първо да се дава думата на най-възрастните фмитяни, след това на по-младите и най-накрая на най-младите и бездетни фмитяни. Разбира се спазването на това решение не е тривиална задача. Не винаги фмитяните познават всичките си родители. Ако по грешка, някой говори преди родителите си или прародителите си, тогава става голям скандал. Задачата е да се напише програма която, да определи реда на изказване във фмитянския парламент, и да прекратят скандалите веднъж за винаги.

Входни данни:

Входните данни са дадени в текстов файл с име family.inp. Първия ред от него съдържа само числото N (1 <= N <= 10 000) – броя на членовете на фмитянския парламент. Според вековните традиции членовете на парламента са номерирани с естествените числя от 1 до N. Следват точно N реда, като i-тия ред съдържа списък с децата на i-тия член на парламента. Списъка с децата с поредица от номерата на децата в произволен ред разделени с интервали. Списъкът може да е празен. Списъкът, дори и празен, завършва с 0.

Резултат:

Резултатът трябва да се запише в текстов файл с име family.out. Той съдържа една единствена линия, списък с членовете на фмитянския парламент по реда на изказване, разделени с интервали. Ако задачата има няколко решения, отпечатайте някое от тях. Поне едно решение винаги съществува.

Примерен вход:

4 1 0

1 0

3 0

Примерен резултат:

2 4 3 1

Задача 4. Teams – Два отбора – 10т.

Дадена е група от N човека. Всеки член на групата има един или повече приятели в нея. Да се напише програма, която разделя групата на два отбора, така че всеки член на всеки отбор трябва да има поне един приятел в противниковия отбор.

Входни данни:

Входните данни са дадени в текстов файл с име teams.inp. Първия ред от него съдържа само числото N (N ≤ 100) – броя на членовете в групата. Членовете на групата са номерирани с числата от 1 до N. Следват N реда, като i-тия ред съдържа списък с приятелите на i-тия член на групата. Списъкът завършва с 0. Приятелството е винаги взаимно.

Резултат:

Резултатът трябва да се запише в текстов файл с име teams.out. На първия ред от него се съдържа броят на хората в първия отбор или нула, ако не е възможно да се раздели групата на два отбора. Ако задачата има решения на втория ред от резултата трябва да се запише списък с хората от първия отбор, разделени с един интервал. Ако задачата има няколко решения, трябва да се отпечата някое от тях.

Примерен вход:

2 3 0

3 1 0

1 2 4 5 0

3 0

Примерен резултат:

1 4 5

Задача 5. Power – Повдигане на степен – 10т.

Дадени са целите числа N, M и Y. Да се напише програма, която намира всички цели числа X в интервала [0, M-1] такива, че X^N mod M = Y.

Входни данни:

Входните данни са дадени в текстов файл с име power.inp. Той съдържа само една линия с числата N, M и Y разделени с интервал (0 < N < 1 000 000 001, 1 < M < 100 000 001).

Резултат:

Резултатът трябва да се запише в текстов файл с име power.out. Отпечатайте в него всички числа за X на една линия, разделени с един интервал, Числата трябва да бъдат отпечатани в нарастващ ред. Ако не съществува X с търсеното свойство отпечатайте -1.

Примерен вход:

2 5 1

Примерен резултат:

1 4

Задача 6. Exam – На изпит – 10т.

Студентите се явяват на изпит. За всеки студент се знае времето, когато е готов за изпитване T₁ (т.е. за колко време си развива въпросите и ги предава), колко минути са необходими за завършване на изпита T2 (т.е. за колко време преподавателят му проверява развитите въпроси и го изпитва по тях) и време, когато трябва да е свободен T₃ (T₁ и T₃се измерват в минути от началото на изпита). По време на изпита има опашка пред преподавателя. Опашката е като на всеки изпит – който свърши по-рано с въпросите си, бива изпитан по-рано, защото се нарежда на по-предна позиция на опашката. Ако преподавателят е зает с някой студент, другите чакат. Възможно е някои студенти да не са свободни в T_3. Възможно е също в някои моменти преподавателят да си почива, ако няма никой на опашката. Преподавателят е добър човек и може да премести началото на изпита по-рано, така че всички студенти да бъдат свободни в съответното за тях T₃ (изчислено спрямо началото на изпита преди да бъде преместено). Вашата задача е да напишете програма която да изчисли колко минути по-рано трябва да се премести изпита. Преместването трябва да е с минимален брой минути.

Входни данни:

Входните данни са дадени в текстов файл с име exam.inp. Първия ред от него съдържа числото N (1 ≤ N ≤ 100) – броя на студентите. Следващите N реда съдържат T1, T2, T3 (0 ≤ T1 ≤ T3 ≤ 600, 1 ≤ T2 ≤ 240). Всички T1 са различни.

Резултат:

Резултатът трябва да се запише в текстов файл с име exam.out. Отпечатайте в него минималният брой минути, с които трябва да се премести началото на изпита или 0 ако студентите имат достатъчно време и преместване не е необходимо.

Примерен вход:

110 10 120

70 40 150

95 15 400

60 10 160

Примерен резултат:

Задача 7. Multigame – Мултиигра – 10т.

Вероятно вече знаете играта, в която всеки от двамата играчи взема от 1 до 3 пула от купчина. Губи този които вземе последния пул. Нека обобщим играта. Да предположим че играчите не могат да вземат не 1, 2 или 3 пула, а k₁, k₂, .. k_m пула. Задачата е да се определи кой печели при оптимална игра на двамата играчи, при условие, че играч 1 прави първия ход. За загубил играта се счита този играч, който е направил последния ход, т.е. печели играчът, който е на ред и няма валиден ход. За тази игра е добре известно, че може да се определи оптималният следващ ход без да се знае нищо за предишните ходове.

Входни данни:

Входните данни са дадени в текстов файл с име multigame.inp. Първия ред от него съдържа числата N и M (N <= 1 000 000, М <= 50) – броят на пуловете и броят на числата k1, k2, .. km. На втория ред са числата k1, k2, .. km разделени с интервал.

Резултат:

Резултатът трябва да се запише в текстов файл с име multigame.out. Отпечатайте в него 1, ако печели първия играч или 2 ако печели втория.

Примерен вход:

17 3

2 1 3

Примерен резултат:

Задача 8. Hospitals – Болници – 10т.

Кметът на града Горно Нанадолнище е осигурил пари по европейски проект за построяването на две високо технологични болници, където да работят най-добрите лекари от града. След дълго проучване на нуждите на гражданите на Горно Нанадолнище, както и на тежкия трафик и архитектурния план на града, консултантите по проекта избрали общо N възможни места из всички квартали на града за построяване на новите болници. Също така, те предложили двете болници да бъдат построени така, че най-отдалеченото от избраните места спрямо по-близката му от двете бъдещи болници да е колкото се може по-малко – уж за да може линейките да стигат колкото се може по-бързо без значение в кой квартал се намира се намира някой болен. Това разбира се не е най-правилното решение, но пък има ли някой кмет, който винаги да взима правилни решения – още повече щом консултантите по проекта предлагат решение на възложената им задача !?

Напишете програма която по зададен брой N (1<N<501) избрани места и M директни между пътя между някои двойки места намира кои две от местата да бъдат определени за построяването на болниците, за да е колкото се може по-малко най-голямото от разстоянията от всяко избрано място до по-близката му болница. За всеки две от избраните места е вярно, че може да се стигне от едното до другото по дадените M пътя. Между двойка места може да има повече от един директен път

Входни данни:

Входните данни са дадени в текстов файл с име hospitals.inp. На първия ред са записани две числа – N и M. Следват M реда с по три числа I, J и L на всеки – първите две са двойка различни места от избраните (местата се индексират с числата от 1 до N), а третото е дължината на пътя между тях (положително число – не по-голямо от 1 000 000).

Резултат:

Резултатът трябва да се запише в текстов файл с име hospitals.out.На единствения ред запишете три числа разделени с интервал. Първото число трябва да е търсеното разстояние, а второто и третото да са местата, където да се построят болници, за да се постига това разстояние. От всички възможни отговори изведете този, който е лексикографско (речниково) най-малък. Последователността на отговорите трябва да отговаря на последователността на входните данни.

Примерен вход:

4 4

1 2 10

2 3 10

3 4 10

4 1 10

Примерен резултат:

10 1 2

Задача 9. Domat – Домати - 10т.

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

За тяхно съжаление обаче коридорите в сградата на факултета водели само от стаята на една катедра до стаята на друга катедра (или евентуално до същата стая). Ето защо било много вероятно по пътя си те да трябва да преминат през стаите на други катедри. В тези случаи обаче имало неписано академично право, че всеки от посетителите трябва да поздрави лично всеки от хората в съответната катедра. Това естествено отнемало време. Време отнемало и ходенето през коридорите свързващи катедрите.

За ужас на Станчо и колегите му доматите, при техните домакини, намалявали прогресивно с времето. Ето защо те трябвало да стигнат максимално бързо там. Станчо бил достатъчно умен за да знае, че една компютърна програма може да намери оптималния по време път. Той обаче вече бил прекалено препил с минерална вода ето защо помолил вас да я напишете вместо него.

Входни данни:

Входните данни се задават в текстов файл с име domat.inp. На първия ред на входния файл стоят две числа – N и M. 1 ≤ N ≤ 1000 е броят на катедрите (и съответно стаите) във факултета на Станчо, а M е броя на коридорите в сградата. На следващите N реда стои по едно число – времето, за което Станчо и колегите му могат да поздравят всичките си домакини в съответната стая. На следващите M реда стоят по три числа – първите две са номера на стаи свързани с коридор, а третото е времето необходимо за преминаване на коридора. На последния ред стоят две числа - номера на катедрата на Станчо и номера на катедрата на по изследване на доматите.

Резултат:

Резултатът трябва да се запише в текстов файл с име domat.out. Файлът трябва да се състои от два реда. На първият трябва да стои минималното време, за което Станчо и колегите му могат да започнат разговора си с колегите си от катедрата по изследване на доматите. На вторият ред трябва да са записани номерата на катедри по най-бързия път, започвайки с тази на Станчо и завършвайки с тази по изследване на доматите, разделени с по един интервал.

Примерен входен файл:

5 6

1 2 3

2 3 2

3 4 1

1 4 6

5 3 8

4 5 4

1 5

Примерен резултатен файл:

1 4 5

Задача 10. LexSort – Лексикографско сортиране – 10т.

Един ден Станчо се сетил, че скоро не е сортирал числа лексикографски. При такова сортиране числата се сортират като в речник, т.е. 1 е преди 12, но 12 е преди 2 и т.н. . Този път обаче Станчо искал предизвикателство ето защо той искал да играе срещу програма, която се надява вие да напишете. Правилата на играта са прости. Станчо си намисля едно число N < 10^6. След това сортира числата и пита програмата ви на кое място е числото X.

Например ако N е 13, то последователността е 1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9. Тогава X = 2 отговора, който трябва да изкара вашата програма е 6.

Входни данни:

Входните данни се задават в текстов файл с име lexsort.inp. На първия ред на входния файл стоят две числа – N и X. 1 ≤ N ≤ 1000000 и 1 ≤ X ≤ N.

Резултат:

Резултатът трябва да се запише в текстов файл с име lexsort.out. Файлът трябва да се състои от един реда, на който да пише мястото на X в сортираната последователност.

Примерен входен файл:

13 2

Примерен резултатен файл:

Задача 11. Luggage - Багаж – 10т.

Времето, когато Станчо ще трябва да опакова багажа си в куфари и да отиде на съседната планета ФХ. Той има много интересни книги, които иска да вземе със себе си. За съжаление обаче, това е невъзможно, поради факта, че куфарите му не са безкрайни или дори безбройни. Целия обем, който Станчо може да отдели за книги е L. Той вече е проверил, коя от книгите му колко обем заема. Сега той се нуждае да избере най-интересните от тях. За целта той се надява някой от студентите по Пранка да му напише програма.

Входни данни:

Входните данни се задават в текстов файл с име luggage.inp. На първия ред на входния файл стоят две числа – 1 ≤ L ≤ 1000 и 1 ≤ N ≤ 1000 – броя на книгите, които Станчо притежава. На следващите N реда стоят по две числа – обема на книгата и това колко е интересна тя на Станчо.

Резултат:

Резултатът трябва да се запише в текстов файл с име luggage.out. На първия му ред трябва да е записано сумарно максималният интерес на избраните книги за Станчо. На втория трябва да са записани номерата на избраните книги, по реда им от входния файл, разделени с интервали.

Примерен входен файл:

10 4

5 10

4 7

6 14

8 20

Примерен резултатен файл:

2 3

Задача 12. Suffix – Строене на Suffix Array – 15т.

След като мита, че СтанчоСорт (Виж зад. Fastsort) е ултра-мега-бърз алгоритъм за сортиране бил разбит (оказало се, че тестове са много специфични и СтанчоСорт е просто един от известните алгоритми за сортиране чрез трансформация комбиниран с бъглива реализация на сортирането чрез вмъкване, /която се извиквала по 3 пъти, за да работи правилно/), Станчо отново се оттеглил и решил да покаже на света, че ще измисли нещо велико. Той вече имал база, на която да стъпи – знаел сортиране чрез вмъкване и още един алгоритъм, който не бил сигурен как се казва. За това решил да разработи нещо подобно и отново потънал из старата библиотека. Чел цял месец – прочел 4 книги за алгоритми и нищо не разбрал (освен сортирането чрез вмъкване което срещнал в едната). Изведнъж на средата на 5-тата той успял да разбере за какво става дума в едната глава. Тя била книга за алгоритми върху низове – нещо, което му звучало доста познато. Това, което горе долу разбрал било Suffix Array.

Нека е даден символен низ с символа. Тъй като в книгата реализациите са били на чисто C ще приемаме позициите в низа са числата от до а на позиция стои специален символ с код , който не се среща никъде преди нея. Тогава suffix или наставка на низа от позиция разбираме последователността от позиция до позиция включително (този низ пак има специален символ с код накрая и за това дължината му е ). Тогава suffix array представлява масив съдържащ всички suffix-а на низа така че те да са представени с позициите от които започват но да бъдат сортирани лексикографски по самите символи в тях. Например за низът “alabala” наставките ще се сортират по следният начин (“”, “a”, “abala”, “ala”, “alabala”, “bala”, “la”, “labala”) и тогава suffix array-ът на низът ще бъде (7, 6, 2, 4, 0, 3, 5, 1).

В книгата били предложени някои доста добри алгоритми за строене на suffix array. Станчо обаче не ги разбрал.

След известно време обаче той решил да опита да комбинира алгоритмичните си знания с бутилка минерална вода. За съжаление обаче нищо не се получило. Тогава му хрумнала гениалната идея да се опита да комбинира самите знания. Все пак си помогнал с бутилка минерална вода. Изсипал знанията вътре, затворил, раздрусал и я ударил на екс. Изведнъж изпаднал в момент на гениалност и измислил алгоритъм за строене на suffix array.

При строене на suffix array скоростта много пада от факта, че сравнението на два низа може да изисква време пропорционално на дължината на по-късия тъй като може да имат много дълги съвпадащи начални части (префикси). Сравнението обаче може да се ускори с помощта на следния факт: ако символите на позиция и позиция са равни то отношението на suffix-ите от позиции и е същото като отношението на suffix-ите от позиции и . Тогава, ако започнем от нарастващ масив (наредени числата от до ) и приложим обърнато сортиране чрез вмъкване (вмъкваме към края на масива отляво на дясно вместо към началото) като във всеки момент помним за сортираната вече част от масива всеки suffix на коя позиция се намира то ще построим целият suffix array.

От вас се иска да разберете и реализирате гореописаното. Suffix array е реална структура от данни, която се ползва за низови проблеми и за нея съществуват доста добри алгоритми за строене и използване, но ние сега не се интересуваме от тях.

Входни данни:

Входните данни са дадени в текстов файл с име suffix.inp. На единствения му ред се съдържа символен низ от букви и знаци (без специални символи като например интервал). Дължината на низа няма да надхвърля 30000 символа.

Резултат:

Резултатът трябва да се запише в текстов файл с име suffix.out. Той трябва да съдържа един ред съдържащ числата от Suffix Array-a на дадения низ разделени с интервал.

Примерен входен файл:

alabala

Примерен резултатен файл:

7 6 2 4 0 3 5 1

Задача 13. Tour – Обиколка на забележителности – 15т.

Станчо често развежда туристи из забележителностите на Софийски университет. Тъй като Софийският университет е уникален, а и туристите, които искат да го разглеждат, обикновено страдат от психични заболявания, то може да приемем, че всичко принадлежащо на Софийският Университет, е забележителност. Разходката представлява тръгване от някоя произволна забележителност (където се пристига с автобус), обиколка из забележителностите (преминава се само през някои забележителности в някакъв ред) и връщане на началното място (при автобуса). За да не бъдат отегчени туристите трябва да не се минава през едно и също място повече от веднъж и между две съседни забележителности да не се преминава повече от веднъж (например един път на отиване и един път на връщане). Тъй като Станчо цял ден не е пил минерална вода, а вече е започнала сбирката на неговата катедра, на която има крайно количество минерална вода, той иска да приключи максимално бързо с обиколката за да остане минерална вода и за него. Помогнете на Станчо да намери най-бързия маршрут за обиколка.

Входни данни:

Софийският университет е представен чрез неориентиран претеглен граф, като забележителностите са означени с върхове, а възможностите за преминаване между две съседни забележителности са означени с ребра. Входните данни са дадени в текстов файл с име tour.inp. На първия ред стоят две цели числа N и M, разделени с интервали, задаващи съответно броя на забележителности и броя възможности за преминаване между двойки забележителности в университета (1 ≤ N ≤ 800). Следват N реда, описващи времето, което е необходимо за разглеждане на всяка от забележителностите – цяло неотрицателно число брой в минути. Следват M реда описващи възможностите за придвижване от една забележителност към друга (ребрата в графа). Една такава възможност се описва от 3 числа, разделени с интервал – начална забележителност, крайна забележителност и време необходимо за преминаване (цяло неотрицателно число, указващо времето в минути). Възможно е преминаване и в двете посоки, като времето за преминаване е еднакво, но не се допуска в един маршрут да се преминава повече от веднъж по едно ребра на графа. Забележителностите са номерирани с числата от 1 до N. Възможно е да има няколко възможности за преминаване между някои двойки забележителности. В такъв случай е възможно маршрутът да се състои дори само от 2 забележителности, но това се допуска само ако на отиване и на връщане се минава по различни ребра на графа.

Резултат:

Резултатът трябва да се запише в текстов файл с име tour.out. На първия ред трябва да стоят две числа C и L. C указва броят на забележителностите участващи в оптималния маршрут, а L необходимото време. На всеки от останалите C реда трябва да има по едно число указващо номер на забележителност от маршрута. Тъй като се тръгва и се стига до една и съща забележителност то тя се извежда само веднъж във файла. Общото време за обиколката се получава като се сумират времената за всяка забележителност (началната се брои само веднъж) и пътищата по които е минато. Ако има повече от 1 най-бързи обиколки, трябва да се изведе лексикографски най-малката. Ако няма валидни според условието обиколки трябва да се изведе 0 0.

Примерен входен файл:

8 14

1 2 4

3 2 8

3 1 20

2 3 8

4 5 2

4 6 2

4 8 3

4 7 8

8 7 2

8 6 12

6 7 6

6 5 3

5 7 15

7 5 6

Примерен резултатен файл:

3 20

Задача 14. Cover – Покрития – 15т.

Дадено е число n и квадратна таблица с размери 2n+1 на 2n+1, която се състои от еднакви квадратни клетки. Всяка клетка съдържа стойност 0 или 1. Покриващо множество наричаме такова множество от 2n+1 клетки от таблицата, че в това множество има по точно една клетка от всеки ред и всеки стълб от таблицата.

Върху таблицата е допустима следната операция: Избираме произволно покриващо множество и за всяка клетка от него инвертираме стойностите в таблицата, т.е. всички клетки от това множество, които са били със стойност 0, стават със стойност 1, а всички клетки, които са били със стойност 1, стават със стойност 0.

Да се проектира и реализира ефективен алгоритъм, който определя дали след не повече от (2n+1)! на брой прилагания на горната операция може да се получи таблица, съдържаща не повече от 2n на брой клетки със стойност 1. Да се оцени сложността на алгоритъма в средния и в най-лошия случай.

Входни данни:

Входните данни се задават в текстов файл с име cover.inp. Първият ред съдържа едно цяло число n (1 £ n £ 100). Следващите 2n+1 реда съдържат описание на редовете от таблицата. Всеки ред от таблицата е описан от 2n+1 числа всяко, от които е или 0 или 1, разделени помежду си с един интервал.

Резултат:

Резултатът трябва да се запише в текстов файл с име cover.out. Първият ред на този файл трябва да съдържа съответно “YES” или “NO” в зависимост от това дали съществува решение или не. Останалите редове описват решението, ако има такова. Ако съществува решение, то трябва да бъде отпечатано като последователност от K пермутации на числата от 1 до 2n+1, предхождани от числото K само на ред. Всяка пермутация съответства на една операция инвертиране на покриващо множество, като тя задава за всеки от стълбовете от 1 до 2n+1 номерът на реда на клетката от съответния стълб, която трябва да се инвертира. Всяка от пермутациите трябва да се отпечата на отделен ред, а числата, които ги съставят, трябва да са разделени по между си с интервал.

Примерен входен файл:

1 1 1

1 1 0

1 0 1

Примерен резултатен файл:

YES

3 2 1

2 1 3

Задача 15. Min4 – Най-близки 4 върха в граф – 15т.

Картата на едно населено място е моделирана чрез свързан неориентиран граф с тегла по ребрата и по върховете. Път между два върха в графа наричаме последователност от върхове, започваща от началния връх и завършваща в крайния връх. Дължина на път наричаме сумата от тежестите на всички ребра, участващи в него, към която са добавени тежестите на всички междинни върхове, през които се преминава (началния и крайния не се броят). Разстояние между два върха наричаме дължината на най-късия път между тях. Да се проектира и реализира ефективен алгоритъм, който намира 4-те най-близки един до друг върха на графа, т.е. тези 4 върха, за които сумата от 6-те разстояния по между им е минимална. Да се определи сложността на алгоритъма в средния и в най-лошия случай.

Входни данни:

Входните данни се задават в текстов файл с име min4.inp. На първия ред на входния файл стоят две цели положителни числа N и M, разделени с интервал, които задават съответно броя върхове и броя ребра в графа (1 ≤ N ≤ 500, 1 ≤ M ≤ N*(N-1)/2). На следващия ред стоят N цели положителни числа, задаващи съответно теглата по върховете. Следващите M реда описват ребрата на графа. Всеки от тези редове съдържа по три числа, разделени с интервали, които задават съответно начален връх за реброто, краен връх за реброто и тегло (дължина). Всички тегла по върховете и по ребрата са цели положителни числа ненадвишаващи 30000.

Резултат:

Резултатът трябва да се запише в текстов файл с име min4.out. Файлът трябва да съдържа точно 2 реда. На първия ред трябва да стой сумата от дължините на пътищата между 4те най-близки върха, а на втория ред трябва да номерата на 4-те най-близки върха в графа разделени с интервал. Ако има няколко решения, да се отпечата само едно от тях.

Примерен входен файл:

12 16

7 9 5 1 1 2 4 2 5 3 8 8

1 2 17

1 4 4

1 9 3

1 12 9

2 6 20

2 4 1

3 6 4

3 7 9

4 6 1

4 7 11

4 8 3

5 9 8

7 8 5

8 12 2

9 11 6

10 12 5

Примерен резултатен файл:

2 4 6 8

Задача 16. Deheap - Дийкстра с пирамида – 15т.

Станчо наскоро бил чел за някакви пирамиди и фараони... Помислил си че ако разгледа картата на египет като граф вероятно ще открие скрити послания... Посланията обаче не могат да бъдат разбрани от простосмъртните, а само от алгоритмични гурута като станчо и студентите по ПрАнКА. Станчо много мислил и измислил че има една главна пирамида в египет... Опитен мистик като него веднага открил коя е тя. Оказало се обаче че има и една второстепенна. Станчо трябвало да стигне до главната пирамида, да вземе публичния ключ от нея и да отиде максимално бързо до второстепенната, къде се криел частният ключ. След това трябвало да събере публичният и частният ключ и щал да настъпи алгогедона – последната битка между логиката и алгоритмите. При успех станчо щял да получи за винаги компютър с 4 процесора AMD 64 и два терабайта рам... Който щял да бъде достатъчно мощен за да подкара дори най-тежките пасианси... Това много му се искало на Станчо обаче имал един проблем. Той не знаел коя е второстепенната пирамида. Отговорът на този въпрос се криел в главната пирамида. Пътищата между пирамидите са тежки, и изискват много минерална вода и домати за да се оцелее. Станчо вече се бил запасил с цяла цистерна минерална вода – достатъчно за да обиколи целият египет. Проблем обаче оставали доматите. Помогнете на Станчо и напишете програма която по дадена карта на египет намира необходимият брой домати за да стигне от главната пирамида до всяка от останалите.

Входни данни:

Входните данни се задават в текстов файл с име deheap.inp. На първия ред на входния файл стоят три цели положителни числа разделени с интервал – N, M и K (1 ≤ N ≤ 30000, 1 ≤ M ≤ 50000, 1 ≤ K ≤ N), които задават съответно броя на пирамидите, броя на пътищата и номерът на главната пирамида в египет. Следващите M реда описват по един път между две пирамиди. Всеки от тези редове съдържа по три числа, разделени с интервали, които задават съответно начална пирамида, крайна пирамида и необходимият брой домати за преминаване. Всички пътища са двупосочни, като броят им е сравнително малко което предполага че вашата програма ще трябва да се възползва от това по някакъв начин, иначе ще разгневите Станчо.

Резултат:

Резултатът трябва да се запише в текстов файл с име deheap.out. Той трябва да съдържа точно N числа, всяко на отделен ред, показващи необходимото количество домати за да се достигне от главната пирамида до пирамидата със съответният номер.

Примерен входен файл:

7 8 3

1 2 2

1 4 2

1 3 7

4 3 1

3 6 2

4 5 2

5 7 1

7 6 3

Примерен резултатен файл:

Задача 17. Islands – Острови – 15т.

След великото преселение на катедрите, породено от нечовешката липса на минерална вода, се оказало, че много от катедрите се били установили на островите в южния Пасифик, тъй като климата там бил най-подходящ за развитието на теорията. Не след дълго обаче се оказало, че нямало никакъв транспорт между отделните острови. За това Ректора предложил да се построят мостове така че да е възможно да се премине между всеки два острова минавайки по един или повече мостове. Академичния съвет приел това предложение при условие, че общата дължина на мостовете е минимална.

Станчо бил много запален по алгоритми и бил чул, че един от алгоритмите които решавали подставената задача е алгоритъм на Прим, с използване на пирамида. Станчо обаче бил виждал пирамиди само на картичка от Египет и затова се обръща към вас за помощ. Помогнете му, като му напишете програма, която решава подставената задача.

Входни данни:

Входните данни са дадени в текстов файл с име islands.inp. На първия ред стоят две цели числа N и M, разделени с интервали, задаващи съответно броя островите и броя на възможните места където може да се построй мост (1 ≤ N ≤ 10 000). Следват М реда описващи всяко едно местата. Едно, подходящо за мост място се описва от 3 числа, разделени с интервал – начален и краен остров и дължината на моста. Островите са номерирани с числата от 1 до N.

Резултат:

Резултатът трябва да се запише в текстов файл с име islands.out. Файла има точно N-1 реда. На всеки от останалите ред трябва да има по две числа описващи всеки един от мостовете, с начален и краен остров съответно.

Примерен входен файл:

4 5

1 2 2

1 4 18

1 3 3

2 4 1

3 4 22

Примерен резултатен файл:

1 2

2 4

1 3

Задача 18. IslandsАgain – Острови – 15т.

Станчо бил много запален по алгоритми и бил чул, че един от алгоритмите които решавали подставената задача е алгоритъм на Крускал, с използване на непресичащи се множества (Disjoint sets). Помогнете му, като му напишете програма, която решава подставената задача.

Входни данни:

Резултат:

Примерен входен файл:

4 5

1 2 2

1 4 18

1 3 3

2 4 1

3 4 22

Примерен резултатен файл:

1 2

2 4

1 3

Задача 19. FastPoly – Бързата Поли – 15т.

След невероятният успех на статията „Алгоритми за бързо решаване на 2 x 2 = 4”, Станчо решил че има хляб в умноженията на разни неща... За това решил да напише статия за бързо умножение на полиноми. За целта му трябва програма която да умножава полиноми бързо (все пак върху нещо трябва да се пише статията). На вас се е паднала честта да помогнете на Станчо да стане известен като анонимността ви е гарантирана (не очаквайте да видите името си в статията).

Входни данни:

Входните данни са дадени в текстов файл с име fastpoly.inp. На първия ред стоят две числа – N и М (1 ≤ N ≤ 100000, 1 ≤ М ≤ 100000). На следващите два реда има съответно N и M цели числа разделени с интервал. Те задават кофицентите на двата полинома започващи от най-младшия. Коефицентите ще се събират в стандартен 32 битов тип, но резултатите може и да не се събират.

Резултат:

Резултатът трябва да се запише в текстов файл с име fastpoly.out. Файлът има един ред, на който се намират коефицентите на полинома получен като резултат от умножението на двата дадени полинома. Програмата ви трябва да е бърза и вярна, защото иначе ще провалите статията на нашият велик Станчо.

Примерен входен файл:

3 4

1 1 2

-1 -1 0 3

Примерен резултатен файл:

-1 -2 -3 1 3 6

Задача 20. RectUnion – Лице на обединение на правоъгълници – 15т.

Във ФМИ преподавателите силно намалели... Някои от тях излезли в творчески отпуск, други заминали за чужбина, трети препили с минерална вода, а четвърти просто изчезнали... Най много намалели преподавателите по ООП. Поради тази причина станчо трябвало да се захване с четенето на лекции по ООП за всички потоци и специалности. Станчо както знаем е новатор от класа и за това решил да наложи радикални промени в курса. Той бил почетен член на Организацията на Обединените Правоъгълници, и като такъв смятал че всичко в света може да се представи чрез краен брой правоъгълници чиито страни са успоредни на координатните оси. Ето например как изглежда Станчо:

Най тежката задача в това представяне е намиране на общата покрита площ от всички правоъгълници. За това на вас се пада честа да напишете програма която пресмята лицетето на обединението на дадени правоъгълници.

Входни данни:

Входните данни са дадени в текстов файл с име rectunion.inp. На първия ред стои едно число – N (2 ≤ N ≤ 1000). На следващите N реда има по едно описание на правоъгълник. То се състои от четири числа – X координата на горният ляв ъгъл, Y координата на горният ляв ъгъл, ширина и височина.

Резултат:

Резултатът трябва да се запише в текстов файл с име rectunion.out. Файлаът има един ред, на който е записано лицето на обединението на дадените правоъгълници.

Примерен входен файл:

-5 15 40 10

0 20 15 25

20 20 10 10

30 10 10 10

Примерен резултатен файл:

825

Задача 21. Christmas – Коледна елха – 15т.

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

Входни данни:

Входните данни са дадени в текстов файл с име christmas.inp. На първия ред стои едно число – N (2 ≤ N ≤ 100000). На следващите N-1 реда има описание на по едно ребро. То се състои от две числа – номерата на върховете които то свързва. Входът е валиден, т.е. задава истинско дърво в което няма цикли и т.н.

Резултат:

Резултатът трябва да се запише в текстов файл с име christmas.out. Файла има един ред, на който е записан минималният брой лампички, необходими на станчо за да освети цялата елха.

Примерен входен файл:

1 4

4 2

3 4

1 5

6 1

1 7

Примерен резултатен файл:

Задача 22. Hyperway - Хипермагистрали – 15т.

Един прекрасен зимен ден на Станчо бил поканен да посети конференция на любителите на краставички в отдалечен град. Тъй като Станчо обичал да кара личния си автомобил той решил да използва новите магистрали. Той вече бил намерил най-бързият маршрут. Въпреки това, като предвидлив шофьор, Станчо знаел, че може докато е на път да възникнат задръствания. Ето защо той решил да се подсигури като предварително проучи кой са K-те най-бързи пътища. Той знае, че затова има доста лесен алгоритъм, а самият той трябва да си приготви багажа, ето защо е оставил тази задача на студентите от курса по пранка.

Входни данни:

Входните данни се задават в текстов файл с име hyperway.inp. На първия ред на входния файл стоят три цели положителни числа N, M и K, разделени с интервал, които задават съответно броя на градовете, броя магистралите и от колко най-къси пътя се нуждае Станчо(1 ≤ N ≤ 100, 1 ≤ M ≤ N*(N-1)/2, 1 ≤ K ≤ 10). На вторият ред стоят две цели числа – градът на Станчо и градът на конференцията. Следващите M реда описват магистралите. Всеки от тези редове съдържа по три числа, разделени с интервали, които задават съответно двата града – краища на магистралата и времето за преминаването и (положително число).

Резултат:

Резултатът трябва да се запише в текстов файл с име hyperway.out. На всеки от Kте реда на файла трябва да се съдържа времето за преминаване на пътя, следвано от самия път (като списък от номера на градове). Всички числа на редовете трябва да са разделени с по един интервал.

Примерен входен файл:

12 16 3

1 4

1 2 17

1 4 4

1 9 3

1 12 9

2 6 20

2 4 1

3 6 4

3 7 9

4 6 1

4 7 11

4 8 3

5 9 8

7 8 5

8 12 2

9 11 6

10 12 5

Примерен резултатен файл:

4 1 4

14 1 12 8 4

18 1 2 4

Задача 23. Walks – Разходки – 15т.

Станчо е голям ценител на минералната вода. Един ден той установил, че в някои катедри пиенето на минерална вода е по-приятно от други. Освен това Станчо има нужда от разходка след всеки литър минерална вода. Коридорите на факултета, по които трябва да се разхожда Станчо, са еднопосочни. В случаите, когато са достатъчно широки се приема, че са разделени на две и всяка от двете половини е еднопосочна. След няколко месечно чудене, Станчо открил, че ако представи факултета като граф и намери неговите силно свързани компоненти, ще реши неговия основен проблем – до къде може да стигне с разходките, така че да може винаги да се върне обратно. Той знае, че тази задача може да се реши с алгоритъм на Таржан, но поради пристрастеността си към минералната вода отдавна е загубил способността си да реализира каквато и да е била програма.

Реализирайте този алгоритъм за Станчо.

Входни данни:

Входните данни са дадени в текстов файл с име walks.inp. На първия ред стоят две цели числа N и M, разделени с интервали, задаващи съответно броя върхове и броя ребра в графа (1 ≤ N ≤ 100 000, 1 ≤ M ≤ 20 000 000). Следват М реда описващи ребрата. Едно ребро се описва от 2 числа, разделени с интервал – начален връх, краен връх. Върховете са номерирани с числата от 1 до N.

Резултат:

Резултатът трябва да се запише в текстов файл с име walks.out. На първия ред трябва да стои броя на силно свързаните компоненти на графа - C. На всеки от останалите C реда трябва да бъдат изредени номерата на върховете участващи в съответната силно свързана компонента, разделени с интервал, редът завършва с 0.

Примерен входен файл:

8 12

1 2

2 3

3 1

4 3

5 4

1 5

3 5

3 6

6 7

7 8

8 7

7 6

Примерен резултатен файл:

1 2 3 4 5 0

6 0

7 8 0

Задача 24. Hyper – Верига ресторанти Хайпър – 15т.

При посещението си във ФМИЛандия Станчо забелязал, че страната е с голям потенциал за развиване на бизнес. Конкретно той бил заинтересован от това да открие верига ресторанти Хайпър по магистралата между двата най-големия града – Горно Нанадолнище и Долно Нанагорнище. Името на веригата ресторанти не е случайно – то е смесица между имената на една успешна верига ресторанти в родната страна на Станачо и любимият му филм Сайфър. След като избрал местата за построяване на заведенията покрай магистралата Станчо трябва да избере и в кои от тях да направи складове, за да снабдява ресторантите. Разбира се, Станчо иска всичко да е колкото се може по-оптимално и затова в случая иска сумата от разстоянията от всеки ресторант до най-близкия склад да е колкото се може по-малка.

За да е всичко прецизно Станчо направил следната спецификация, за да може да възложи проекта спокойна на някой друг. Дадени са N ресторанта, които са на разстояние d₁ < d₂ < d₃ < … < d_N от Горно Нанадолнище. Също така, е даден е броят K (K≤N) на складовете, които трябва да се построят в някои от ресторантите, като всеки ресторант ще се снабдява от най-близкия до него склад. Трябва да се минимизира сумата по i на |d_i – (позицията на склада обслужващ ресторант i)|. Реализирайте този проект за Станчо.

Входни данни:

Входните данни са дадени в текстов файл с име hyper.inp, който съдържа последователно няколко възможни разположения на ресторантите. Всяко разположения започва с един ред съдържащ две числа – N и К (1≤N≤1000, 1≤K≤200). Следват N реда, всеки съдържащ разстоянието d_i до поредния ресторант (разстоянията се задават в нарастващ ред). Входният файл завършва с ред съдържащ две нули разделени с интервал.

Резултат:

Резултатът трябва да се запише в текстов файл с име hypher.out. За всяко възможно разположение трябва да се изведе един ред във следния формата: “test case <No>: <Ans>”, където <No> е поредния номер на разположение, а <Ans> е търсената минимална сума.

Примерен входен файл:

3 1

6 3

0 0

Примерен резултатен файл:

test case 1: 20

test case 2: 8

Задача 25. AirGame – Игра поверме на полет – 15т.

Станчо лети от ФМИЛандия обратно към родната си страна. Понеже той лети с компанията Airance Станчо разполага с малък компютър пред себе си на който може да гледа филми или да играе игри. За съжаление, Станчо не е в настроение да гледа филм, така че ще му се наложи да поразмърда мозъка си и да поиграе на нещо, за да не скучае.

Играта която си избра Станчо се играе с правилен n-ъгълник по върховете на който са написани цели числа, а страните му са номерирани и върху всяка е написано знак за събиране или умножение. На всеки ход играчът избира страна която да се изтрие, а върховете инцидентни с тази страни се обединяват в един връх, в който се записва числото, което е резултата от операцията между числата във върховете преди изтриването на страната с операцията записана на страната. Целта е да се получи колкото се може по-малко число в края на играта, когато остане само един връх. На предпоследния ход ще има два върха, които се свързват от две страни – Станчо може да избера коя от тях да изтрие в последния си ход, а другата се игнорира.

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

Входни данни:

Входните данни са дадени в текстов файл с име airgame.inp, който съдържа последователно няколко описания на игри. Всяко описание започва с един ред съдържащ числото N (3≤N≤500). На следващия ред са записани N знака, всеки + или *, и N числа, като се редуват знак, число, знак число..., които съответстват на знака записана на първата страна, числото във върха инцидентен с първата и втората страна, знака на втората страна, числото във върха инцидентен с втората и третата страна и т.н.. Входният файл завършва с ред съдържащ нула.

Резултат:

Резултатът трябва да се запише в текстов файл с име airgame.out. За всяко описание на игра трябва да се изведе един ред във следния формата: “test case <No>: <Ans>”, където <No> е поредния номер на възможно разположение, а <Ans> е минималното число в края на играта.

Примерен входен файл:

+ 1 + 2 + 3

+ -1 * 4 * -2

Примерен резултатен файл:

test case 1: 6

test case 2: -12

Задача 26. SportGame – Спортна игра – 15т.

Станчо е голям спортен фен. След футболния провал през последния уикенд Станчо е решил да гледа само волейбол и някои подобни игри. Интересувайки се от въпроса на живота и други по-маловажни въпроси, Станчо се зачудил каква е вероятността неговия любим отбор да спечели в игра срещу друг отбор, ако разполага с някои достоверни предположения:

· играта се играе от два отбора А и Б

· първият отбор, който спечели K (К≤100) гейма, печели играта

· всеки гейм се състои от рундове, всеки от които се печели от един отбор, за което този отбор печели по една точка

· отборът който първи събере L(L≤100) точки в гейм, печели гейма

· ако отбор A сервира топката в някой рунд, то той има шанс Pa% да спечели рунда и (100-Pa)% да го загуби

· ако отбор Б сервира топката в някой рунд, то той има шанс Pb% да спечели рунда и (100-Pb)% да го загуби

· ако рунд не е първи в даден гейм, то сервира отборът който е спечелил последния рунд

· ако гейм не е първи в дадена игра, то в първия рунд на гейма сервира отбора, който не е сервирал в първия рунд на предишния гейм

· двата отбора имат равен шанс да сервират в първия рунд на първия гейм във всяка игра

По зададени стойности на Pa, Pb, K и L намерете каква е вероятността (изразена в проценти) отбор A да спечели играта.

Входни данни:

Входните данни са дадени в текстов файл с име sportgame.inp. Първият ред съдържа едно число – брой различни игри за които се търси каква е вероятността отбор А да спечели играта. Всеки следващ ред съдържа едно описание на игра – целите числа Pa, Pb, K и L, разделени с по един интервал.

Резултат:

Резултатът трябва да се запише в текстов файл с име sportgame.out. За всяка игра трябва да се изведе по един ред във следния формата: “test case <No>: <Ans>”, където <No> е поредния номер на игра, а <Ans> е търсената вероятност, закръглена до първата цифра след десетичната точка.

Примерен входен файл:

100 50 1 3

100 1 1 1

Примерен резултатен файл:

test case 1: 93.8

test case 2: 99.5

Задача 27. Maxpath – Максимален път в неориентиран граф – 20т.

Противно на задачата за намиране на минимален път в граф задачата за намиране на максимален прост път в граф няма толкова ефективно решение. Нашата задача е да намерим максималният прост път в неориентиран граф възможно най-ефективно. Тъй като може да има повече от 1 максимален път се иска да се намери лексикографски най-малкият (по номерата на върховете му). Да се оцени сложността на алгоритъма в средния и в най-лошия случай.

Входни данни:

Входните данни са дадени в текстов файл с име maxpath.inp. На първия ред стоят две цели числа N и M, разделени с интервали, задаващи съответно броя върхове и броя ребра в графа (1 ≤ N ≤ 100). Следват М реда описващи ребрата. Едно ребро се описва от 3 числа, разделени с интервал – начален връх, краен връх и тегло на реброто. Върховете са номерирани с числата от 1 до N. Възможно е да има по няколко ребра между двойка върхове.

Резултат:

Резултатът трябва да се запише в текстов файл с име maxpath.out. На първия ред трябва да стоят две числа C и L. C указва броят на върховете участващи в пътя а L теглото на пътя. На всеки от останалите C реда трябва да има по едно число указващо номер на връх от пътя.

Примерен входен файл:

8 12

1 2 4

3 2 8

3 1 20

4 5 2

4 6 2

4 8 3

4 7 8

8 7 2

8 6 12

6 7 6

6 5 3

5 7 15

Примерен резултатен файл:

5 38

Задача 28. Fastsort – Бързо сортиране – 20т.

След като катедрата на Станчо започнала да се занимава с алгоритми и след успешното анализиране и дори опит за реализация на алгоритъма за сортиране чрез вмъкване Станчо забелязал, че съществуват някои по-добри алгоритми за сортиране като в някои по-специални случаи имало и още по-добри. Тогава той изчезнал от света за 2 месеца и когато се върнал заявил, че е реализирал ултра мега бърз алгоритъм за сортиране и предизвикал цялата катедра, че и останалите (без тази по алгоритми разбира се) да се опитат да реализират по-бърз. Естествено никой не се осмелил да се пробва и всичко било страхотно докато един ден това не се дочуло от катедрата по алгоритми. За да не бъдат прекалено брутални към старият Станчо те решили да дадат на някой студент да напише по-бързо сортиране от СтанчоСорт. За нещастие обаче като човек с голямо влияние и авторитет тестването ще се извършва единствено върху тестове съставени от Станчо които на всичкото отгоре са тайни. За това се предполага че за много от тестовете са доста специфични – например цялата редица представлява цели числа (въпреки че във форматът са обявени числа с плаваща точка и двойна точност (double типът за популярните програмни езици). Дори се чува че някои от тестовете били само от едноцифрени други пък били почти сортирани или представлявали пермутация на числата от 0 до N-1.... Изобщо тази работа намирисвала. За щастие обаче е известно, че Станчо пише единствено на QBasic за DOS и при това кодът му е много неоптимизиран (все пак е работил по него едва 2 месеца). За това програмата която трябва да се напише има малко време и да анализира подадената последователност за да избере най-подходящият алгоритъм за сортиране. Последното условие, което Станчо поставил било да не се използват алгоритмите за сортиране от стандартните библиотеки като например STL тъй като те били прекалено бързи и били писани от киборзи дошли от бъдещето, за да направят зъл изкуствен интелект, който да превземе света. Така че без използване на сортиранията предлагани от стандартните библиотеки.

Входни данни:

Входните данни са дадени в текстов файл с име fastsort.inp. За да може да се прецени по-прецизно бързодействието той съдържа серия от последователности. Всяка последователност е зададена на 2 реда. На първият се има едно число N – броят на числата в дадената последователност. На следващият ред има N числа с десетична точка задаващи самата последователност. Файлът завършва с 0 за брой на елементите в последователност. Броят на последователностите не надвишава 50, а за всяка последователност броят елементи за сортиране N не надвишава 10 000 000.

Резултат:

Резултатът трябва да се запише в текстов файл с име fastsort.out. Той трябва да съдържа по един ред за всяка последователност – съответната и сортирана последователност. За да няма проблеми с точността на числото се иска числата да се изведат до последната ненулева цифра след десетичната точка (стандартното извеждане на числа с плаваща запетая).

Примерен входен файл:

1 3 2 4 5 3

1.0 2 1 2.00 1 1.00000 2 1 1

1.12 1.13 1.14 1.15 1.16 1

6 5 4 3 2 1 0

Примерен резултатен файл:

1 2 3 3 4 5

1 1 1 1 1 1 2 2 2

1 1.12 1.13 1.14 1.15 1.16

0 1 2 3 4 5 6

Задача 29. Insertsort – Сортиране чрез вмъкване – 20т.

За да бъде модерна катедрата на Станчо трябва често да актуализира направленията в които работи. Въпреки големите успехи в анализа на минералната вода темата вече доста се изчерпала и все по-рядко достигали до откритие. За това те решили да се насочат към друга област – компютърните алгоритми. Тъй като катедрата не е много навътре в алгоритмите те решили да започнат от нещо по-просто. По точно алгоритмите за сортиране. И тъй като и при тях има далеч нетривиални те избрали един сравнително прост алгоритъм – алгоритъмът за сортиране чрез вмъкване. Не след дълго те забелязали, че при проектирането и анализа на компютърни алгоритми често се споменава непозната за тях магическа дума. Това било точно думата “сложност”. Но такива сложно звучащи думи не могат да уплашат старо куче като нашият Станчо. Веднага се разровил из старата библиотека и прегледал голямо количество писания относно въпросният термин. Дори успял да разбере някои от тях. Оказало се, че сложността не е шега работа но все пак намерил връзка между нея и броят размени които извършва вълшебният алгоритъм. За това събрал катедрата и им заявил че трябва да се напише програма която по дадена последователност пресмята този брой. Понеже обаче този брой зависи от точната реализация Станчо уточнил задачата. За всеки елемент в сортираната последователност броят размени е точно броят на по-големите от него числа които стоят преди него. Тогава Станчо се замислил, че в някои науки това се наричат инверсии, но го заболяла главата и се отказал да си спомня за какво точно става дума. Все пак той бил хитър човек и се сетил, че този брой може да е доста голям (дори му се въртяло нещо като квадрат в главата, но решил, че главата му е кръгла и трудно ще се завърти такова ръбато нещо там). За това от вас се иска да напишете програма, която пресмята този брой значително по-бързо.

Входни данни:

Входните данни са дадени в текстов файл с име insertsort.inp. На първият ред от него има едно число N – броят на числата в дадената последователност (1 ≤ N ≤ 500 000). На следващият ред има точно N числа разделени с интервал – числата от последователността за сортиране.

Резултат:

Резултатът трябва да се запише в текстов файл с име insertsort.out. Той трябва да съдържа единствено число – броят размени които би извършило сортирането чрез вмъкване по дефинираният горе начин.

Примерен входен файл:

1 3 2 4 5 3

Примерен резултатен файл:

Задача 30. Castle – Замък с тунели – 20т.

Станчо много обичал да се разхожда из замъка на Софийски Университет. За съжаление обаче в момента катедрите били във война и се разпределяли територии. След последното псевдо-примирие всяка катедра започнала да контролира превзетите тунели. За щастие залите били обявени за неутрални територии. Всъщност замъкът на Софийски Университет представлява две множества. Множество от зали. И множество от тунели. Всеки тунел свързвал две зали. Тъй като катедрите ограничили движението на много от тунелите може да се счита, че всички тунели са еднопосочни. Тунелите, които трябвало да останат двупосочни били разделени на две с маркировка по средата и всички ги приемали за 2 различни тунела. След известно време катедрата на Станчо стигнали до извода, че всеки ден по техните тунели минавали хиляди хора и те съответно могат да припечелят от това. Въвели такса за преминаване по тунел, която се измервала в милилитри минерална вода – основната валутна единица на Софийски Университет. За нещастие и другите катедри се досетили същото и скоро на всички тунели в замъка били въведени такси за преминаване. Катедрите приложили най-различни подходи за изчисляване на таксите. Голяма пречка се оказал факта че таксите не можели да използват комплексни числа. Още по-голяма че трябвало да бъдат и цели. Някои използвали крайни изчислителни машини и изгубили много точност. Други пък искали да представят таксите в ред на Фурие... Общо взето всички отдавна били забравили какво е естествено число и поради това много от таксите се оказали отрицателни. Това означавало, че ако минеш по такъв тунел охраната ти дава известно количество минерална вода вместо да взема. Тогава Станчо се зачудил – дали не може да намери маршрут достижим от неговият кабинет (който е с номер 1 тъй като Станчо е най-важната личност в университета) който да е цикличен и обикаляйки по него Станчо да печели минерална вода. Тъй като това би бил земен рай за Станчо той не се интересува дали от този маршрут може да се върне в кабинета си – рано или късно ще го пренесат. За това вашата задача е да намерите такъв маршрут. Понеже Станчо лесно се отегчава той би искал маршрутът да е опростен – да не се минава през една и съща зала повече от веднъж за една обиколка на маршрута.

Входни данни:

Входните данни са дадени в текстов файл с име castle.inp. На първият ред има две числа N и M (1 ≤ N ≤ 500). N е броят на зали в замъка а M е броят тунели. Следват M реда всеки от които описва един тунел с 3 числа – начална зала, крайна зала и такса за преминаване. Залите са с номера от 1 до N като зала с номер 1 е кабинетът на Станчо.

Резултат:

Резултатът трябва да се запише в текстов файл с име castle.out. На първият ред трябва да стои K – броят зали на намерения цикличен маршрут. На всеки от следващите К реда трябва да има по едно число – съответният номер на зала. Маршрутът трябва да има отрицателна сума на таксите, да няма дадена зала повече от веднъж и да е достижим от зала номер 1. При повече от един възможни отговора изведете един кой да е от тях.

Примерен входен файл:

6 10

4 3 5

4 5 3

5 3 -2

2 6 4

3 2 -1

3 4 -2

1 2 3

1 3 -1

2 1 5

2 3 -1

Примерен резултатен файл:

Задача 31. Sequence – Редица със знаци – 20т.

Дадени са две цели положителни числа N и C. Разглеждаме равенството:

C = 1 ∆ 2 ∆ … ∆ N

Да се проектира и реализира ефективен алгоритъм, който проверява дали даденото равенство може да бъде удовлетворено, ако всеки от знаците ∆ бъде заменен или с "+", или с "-", или с "*". Пресмятането на получения числов израз се извършва отляво надясно, като операциите са с еднакъв приоритет.

Входни данни:

Входните данни се задават в текстов файл с име sequence.inp. На първия ред на входния файл стои едно число K – брой равенства, които програмата трябва да изследва (1 ≤ K ≤ 100). На всеки от следващите K реда има по две цели числа N и C, разделени с интервал (1 ≤ N ≤ 50, 1 ≤ C ≤ 30 000).

Резултат:

Резултатът трябва да се запише в текстов файл с име sequence.out. Файлът трябва да се състои от точно K реда. На всеки от тях трябва да има информация за поредното равенство, описано във входния файл. Ако има решение, то трябва да бъде описано във вида:

C = 1 ∆ 2 ∆ … ∆ N

където знаците ∆ за заменени със съответните аритметични операции, водещи до удовлетворяване на равенството. Ако няма решение на съответния ред трябва да стои фразата “No solution”.

Примерен входен файл:

19 5

177 4

912 11

Примерен резултатен файл:

19=1+2+3*4-5

No solution

912=1*2*3*4*5-6-7-8*9+10+11

Задача 32. Ultraway - Ултрамагистрали – 20т.

В държавата ФМИландия били построени нови магистрали. Те свързвали отделните градове(които естествено били номерирани от 1 до N) и се знаело точно за колко време може да се премине по тях от един град до друг. В общия случай по тях можело да се кара много бързо, често обаче по тях ставали катастрофи, които от своя страна предизвиквали задръствания и забавяли драстично скоростта на движение по тях и от там времето за преминаването от един град до друг се увеличавало драстично. За контролиране на трафика през градовете били използвани специални устройства. Така в зависимост дали за да се стигне до този град са били използвани четен или нечетен брой магистрали времето за преминаване през града може да бъде различно.

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

Входни данни:

Входните данни се задават в текстов файл с име ultraway.inp. На първия ред на входния файл стоят три цели положителни числа N, M и K, разделени с интервал, които задават съответно броя на градовете, броя магистралите и от колко най-къси пътя се нуждае Станчо(1 ≤ N ≤ 50, 1 ≤ M ≤ N*(N-1)/2, 1 ≤ K ≤ 10). На вторият ред стоят две цели числа – градът на Станчо и градът на конференцията. Следват N реда описващи времето за преминаване през съответния град. На всеки от тези редове стоят по две цели положителни числа – времето за преминаване, ако преди това са ползвани нечетен брой магистрали и времето, при четен брой магистрали. Следващите M реда описват магистралите. Всеки от тези редове съдържа по три числа, разделени с интервали, които задават съответно двата града – краища на магистралата и времето за преминаването и (положително число).

Резултат:

Резултатът трябва да се запише в текстов файл с име ultraway.out. На всеки от Kте реда на файла трябва да се съдържа времето за преминаване на пътя, следвано от самия път (като списък от номера на градове). Всички числа на редовете трябва да са разделени с по един интервал.

Примерен входен файл:

4 5 3

1 4

1 1

11 1

1 11

1 21

1 2 3

1 3 5

2 3 2

2 4 4

3 4 8

Примерен резултатен файл:

14 1 3 2 4

35 1 3 4

36 1 2 3 4

Задача 33. MaxFlow –– Неизползваните тръби – 20т.

След няколко месечно анализиране на строителните планове на университета Станчо открил, че съществува цяла неизползвана мрежа от тръби. През гениалната му глава бързо минала идеята да снабди кабинета си с минерална вода през тази мрежа. Всяко съединение между тръбите обаче има максимален капацитет, т.е. възможно е капацитетът на връзката да е по-малък от сумата на входящите тръби или сумата на изходящите. Станчо знае капацитета на всяка една от тръбите, както и капацитетите на съединенията. Тъй като Станчо е голям почитател на минералната вода той желае да се снабди с колкото се може повече от любимата напитка. Тъй като не е много добре с алгоритмите Станчо се обръща за помощ към вас. Напишете програма, която да намира възможно най-голямото количество от ценната течност към кабинета на Станчо. По стар обичай мрежата е представена като ориентиран граф, където всяка една тръба е ребро, а две тръби се свързват във връх. Върховете са номерирани с числата от 1 до броя им. Станчо знае, че входящото и изходящото количество минерална вода трябва да бъде едно и също за всеки връх различен от хранилището и кабинета му и че не трябва да надвишава капацитета на съответния връх. Разбира се капацитета на тръбите не може да се превишава, защото това би довело до течове и целия план би пропаднал.

Входни данни:

Входните данни се задават в текстов файл с име maxflow.inp. На първия ред на входния файл стои целите числа N и M, разделени с интервал, които задават броя на върховете и броя на ребрата на графа (2 ≤ N ≤ 500). Следващите N реда съдържат капацитетите на всеки един връх, започвайки от първия. Следващите M реда съдържат информация за всяко едно от ребрата I J K, където I и J са съответно началния и крайния връх на реброто, а K е капацитетът на реброто. На последния ред на входния файл стоят числата W и S, които указват съответно, номера на хранилището с минерална вода и кабинета на Станчо.

Резултат:

Резултатът трябва да се запише в текстов файл с име maxflow.out, на първия ред на който стоят максималното количество минерална вода, което Станчо може да транспортира до кабинета си. На следващия ред стои броя на ребрата R, които участват в търсеното решение. На следващите R реда са описани всички ребра, по които Станчо ще пренася минерална вода, заедно с количествата. Например I J K би означавало, че Станчо ще пренесе K литра от връх I до връх J.

Примерен входен файл:

4 4