Пранка-проекти-2008

от Съзтезателно програмиране

Съдържание 1 Разпределение на проектите 2 Изисквания 3 Задачи 3.1 Задачи от 10т. 3.1.1 Cocktail – Коктейл на катедрата – 10т. 3.1.2 Perm – Пермутации – 10т. 3.1.3 Family – Родословно дърво – 10т. 3.1.4 Teams – Два отбора – 10т. 3.1.5 Power – Повдигане на степен – 10т. 3.1.6 Exam – На изпит – 10т. 3.1.7 Multigame – Мултиигра – 10т. 3.1.8 Hospitals – Болници – 10т. 3.1.9 Domat – Домати - 10т. 3.1.10 LexSort – Лексикографско сортиране – 10т. 3.1.11 Luggage - Багаж – 10т. 3.1.12 Game21 – Игра 21 – 10т. 3.1.13 Flags – Знамена – 10т. 3.1.14 Min4 – Най-близки 4 върха в граф – 10т. 3.2 Задачи от 15т. 3.2.1 Suffix – Строене на Suffix Array – 15т. 3.2.2 Tour – Обиколка на забележителности – 15т. 3.2.3 Cover – Покрития – 15т. 3.2.4 Deheap - Дейкстра с пирамида – 15т. 3.2.5 Islands – Острови – 15т. 3.2.6 IslandsАgain – Острови – 15т. 3.2.7 FastPoly – Бързата Поли – 15т. 3.2.8 Christmas – Коледна елха – 15т. 3.2.9 Walks – Разходки – 15т. 3.2.10 AirGame – Игра по време на полет – 15т. 3.2.11 SportGame – Спортна игра – 15т. 3.2.12 Dual - Най-къс път по два критерия - 15т. 3.2.13 Insertsort – Сортиране чрез вмъкване – 15т. 3.2.14 Sequence – Редица със знаци – 15т. 3.2.15 Garbage - Събиране на боклука - 15т. 3.3 Задачи от 20т. 3.3.1 RectUnion – Лице на обединение на правоъгълници – 20т. 3.3.2 Hyperway - Хипермагистрали – 20т. 3.3.3 Hyper – Верига ресторанти Хайпър – 20т. 3.3.4 Maxpath – Максимален път в неориентиран граф – 20т. 3.3.5 Fastsort – Бързо сортиране – 20т. 3.3.6 Castle – Замък с тунели – 20т. 3.3.7 MaxFlow – Неизползваните тръби – 20т. 3.3.8 Networks – Несигурните мрежи – 20т. 3.3.9 Stanchium – Оптмизиране на процесорни операции – 20т. 3.3.10 Routing - Рутиране в мрежа - 20т. 3.3.11 Fractions - Скоби на дроби - 20т. 3.3.12 Party – Парти на катедрата – 20т. 3.3.13 Meeting – Среща между катедрите – 20т. 3.3.14 Maxsum – Максимална сума – 20т. 3.3.15 Derivation - Проверка за вярност - 20т. 3.4 Задачи от 25т. 3.4.1 Ultraway - Ултрамагистрали – 25т. 3.4.2 Science – Научна дейност – 25т. 3.4.3 AllCycles – Всички цикли в граф – 25т. 3.4.4 Chess1 – Опростен шах 1 (мат с цар и два офицера срещу цар) – 25т. 3.4.5 Chess2 – Опростен шах 2 (цар и топ срещу цар и кон) – 25т. 3.4.6 MinSet - Минимално по брой елементи доминиращо множество – 25т. 3.4.7 Words - Безкрайни думи - 25т. 3.4.8 Rooks – Задачата за топовете – 25т. 3.4.9 Expressions - Изрази - 25 т. 3.4.10 Certificates - Сертификати - 25 т. 3.5 Трудни задачи 3.5.1 Quasirooks – Задачата за квазитоповете – 30т. 3.5.2 Reverse – Играта ``Reverse – 30т. 3.5.3 Mincut – Минимален разрез на поток – 30т. 3.5.4 MinCostFlow – Неизползваните тръби – 30т. 3.5.5 Transportation – Транспорт на минерална вода – 30т. 3.5.6 Net – Окабеляване – 30т. 3.5.7 Section - Сечение - 30 т. 3.5.8 GraphCount – Броене на планарни графи – 35т. 3.5.9 Planar – Визуализация на планарен граф в равнината – 35т. 3.5.10 Automorphism – Автоморфизъм – 35т. 3.5.11 CutGlass – Стъклорезница – 35т. 3.5.12 Acquaintances - Познанства – 50т. 3.5.13 Prime – Прости числа – 50т. 3.5.14 Functions – Функции – 100т.

Разпределение на проектите

По-долу са изброени възможните теми за проекти. За да ограничим преписването до минимум пък и за да се подсигурим че няма всички да пишете един и същ проект прилагаме следното правило: разделихме проектите на 5 групи по трудност като задачите от първата дават най-малко точки, а тези от последната - най-много. На всеки от вас на произволен принцип разпределяме 3 задачи от първа, 3 задачи от втора, 2 задачи от трета и две задачи от четвърта трудност. Всеки от вас трябва да напише ТОЧНО ЕДИН проект като за тема избере една разпределените си теми или проект от най-високата(пета) трудност. Последнте могат да се считат за разпределени на всички. Разпределнието на проектите може да се открие в moodle-a и е направено по имената използвани за записването в moodle.

Изисквания

Проекта трябва да е написан на C++ или JAVA. И да изпълнява следните изисквания:

• да се компилира
• да решава възможно най-точно поставената задача
• да бъде написан четливо
  • Сорс кодът трябва да е лесен за разбиране и проследяване как работи.
  • Да се именуват променливите и подпрограмите с подходящи имена.
  • Да се слагат коментари на местата с тежка логика.
  • Кодът да се подравнява (форматира) по подходящ начин.
  • Сложните подпрограми да се разделят на няколко по-прости.
• Използването на нетривиални алгоритми и структури от стандартните библиотеки се позволява само за задачи над 25 точки, включително.
• Да генерира винаги еднакъв изход при еднакви входни данни (ако се използва генератор на псевдослучайни числа, трябва да се внимава да се генерират винаги еднакви редици от числа).
• Да използва не повече от 96MB оперативна памет.

Задачи

Задачи от 10т.

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

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

Входни данни

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

Резултат

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

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

aabbab
ab

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

7

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
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

Family – Родословно дърво – 10т.

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

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

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

Резултат:

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

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

4
0
4 1 0
1 0
3 0

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

2 4 3 1

Teams – Два отбора – 10т.

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

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

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

Резултат:

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

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

5
2 3 0
3 1 0
1 2 4 5 0
3 0
3 0

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

3
1 4 5

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

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

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

Входните данни са дадени в текстов файл с име 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

Exam – На изпит – 10т.

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

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

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

Резултат:

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

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

4
110 10 120
70 40 150
95 15 400
60 10 160

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

15

Multigame – Мултиигра – 10т.

Вероятно вече знаете играта, в която всеки от двамата играчи взема от 1 до 3 пула от купчина. Губи този които вземе последния пул. Нека обобщим играта. Да предположим че играчите не могат да вземат не 1, 2 или 3 пула, а k1, k2, .. km пула. Задачата е да се определи кой печели при оптимална игра на двамата играчи, при условие, че играч 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

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

2

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

Domat – Домати - 10т.

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

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

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

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

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

Резултат:

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

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

5 6
0
2
3
4
5
1 2 3
2 3 2
3 4 1
1 4 6
5 3 8
4 5 4
1 5

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

19
1 4 5

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

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

6

Luggage - Багаж – 10т.

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

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

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

Резултат:

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

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

10 4
5 10
4 7
6 14
8 20

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

21
2 3

Game21 – Игра 21 – 10т.

Игрална дъска се състои от 21 полета и има следната форма:

          X X X
        X X X X X
        X X X X X
        X X X X X
          X X X

Всяко поле (означено на фигурата с "X") може или да съдържа стойност или 0 или 1. Върху дъската можем да прилагаме 3 вида операции:

• инвертиране на 9 полета разположени във формата на квадрат с размери 3 x 3;
• инвертиране на 5 полета разположени във формата на кръстче;
• инвертиране на всичките 21 полета.

Инвертиране наричаме промяна на стойността на дадено поле, при която 0 става 1, а 1 става 0. Да се проектира и реализира алгоритъм, който по зададена целева дъска (описана като последователност 21 числа, ред по ред отляво надясно) намира минималния брой операции от 3-те посочени вида, чрез които от дъска, запълнена цялата с 0 се достига до зададената целева дъска. Например дъската (3) може да се получи от началната дъска (0) с 3 на брой преобразувания съгласно описаните по-горе правила:

  0 0 0                 0 0 0                 1 0 0                 0 1 1
0 0 0 0 0   опер. 1   0 0 1 1 1   опер. 2   1 1 0 1 1   опер. 3   0 0 1 0 0
0 0 0 0 0  -------->  0 0 1 1 1  -------->  0 1 1 1 1  -------->  1 0 0 0 0
0 0 0 0 0             0 0 1 1 1             0 0 1 1 1             1 1 0 0 0
  0 0 0                 0 0 0                 0 0 0                 1 1 1
   (0)                   (1)                   (2)                   (3)

Да се оцени сложността на предложения алгоритъм в средния и в най-лошия случай.

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

Входните данни се задават в текстов файл с име game21.inp. На първия ред на входния файл стои едно число K – брой дъски, които програмата трябва да оцени за най-малко колко хода могат да се получат (1 ≤ K ≤ 500). На всеки от следващите K реда има по 21 числа, разделени с интервал, всяко от които е или 0 или 1.

Резултат:

Резултатът трябва да се запише в текстов файл с име game21.out. Файлът трябва да се състои от точно K реда. На всеки ред трябва да има по едно цяло число – минимален брой ходове за получаване на съответната дъска или -1 ако съответната дъска не може да се получи от началната.

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

2
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 1 1 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1

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

-1
3

Flags – Знамена – 10т.

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

1. Ивици с един и същи цвят не могат да заемат съседни позиции.
2. Зелената ивица винаги трябва да бъде подставяна между бяла и червена или червена и бяла ивица.

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

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

Входните данни са дадени в текстов файл с име flags.inp. Той съдържа само числото N – броя на ивиците, 1 <= n <= 45.

Резултат:

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

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

3

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

4

Пример:

Всички допустими конфигурации с 3 ивици: Картинка:Flags.PNG

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

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

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

18
2 4 6 8

Задачи от 15т.

Suffix – Строене на Suffix Array – 15т.

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

Нека е даден символен низ с N символа. Тъй като в книгата реализациите са били на чисто C ще приемаме позициите в низа са числата от 0 до N-1 а на позиция N стои специален символ с код 0, който не се среща никъде преди нея. Тогава suffix или наставка на низа от позиция i разбираме последователността от позиция i до позиция N включително (този низ пак има специален символ с код накрая и за това дължината му е N-i+1). Тогава suffix array представлява масив съдържащ всички N+1 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 скоростта много пада от факта, че сравнението на два низа може да изисква време пропорционално на дължината на по-късия тъй като може да имат много дълги съвпадащи начални части (префикси). Сравнението обаче може да се ускори с помощта на следния факт: ако символите на позиция i и позиция j са равни то отношението на suffix-ите от позиции i и j е същото като отношението на suffix-ите от позиции i+1 и j+1. Тогава, ако започнем от нарастващ масив (наредени числата от 0 до N) и приложим обърнато сортиране чрез вмъкване (вмъкваме към края на масива отляво на дясно вместо към началото) като във всеки момент помним за сортираната вече част от масива всеки suffix на коя позиция се намира то ще построим целият suffix array.

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

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

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

Резултат:

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

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

alabala

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

7 6 2 4 0 3 5 1

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
8
20
30
8
2
3
5
6
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
4
5
6

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 1 0
1 0 1

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

YES
2
3 2 1
2 1 3

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

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

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

Входните данни се задават в текстов файл с име 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

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

3
5
0
1
3
2
4

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

IslandsАgain – Острови – 15т.

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

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

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

Входните данни са дадени в текстов файл с име 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

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

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

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

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

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

Резултат:

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

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

7
1 4
4 2
3 4
1 5
6 1
1 7

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

2

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

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

3
1 2 3 4 5 0
6 0
7 8 0

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

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

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

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

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

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

Резултат:

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

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

3
+ 1 + 2 + 3
3
+ -1 * 4 * -2
0

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

test case 1: 6
test case 2: -12

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> е търсената вероятност, закръглена до първата цифра след десетичната точка.

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

2
100 50 1 3
100 1 1 1

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

test case 1: 93.8
test case 2: 99.5

Dual - Най-къс път по два критерия - 15т.

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

За Станчо изминатото разстояние не е важно – него много повече го притеснява да преминава през по-малко на брой кръстовища. Друго много съществено нещо за Станчо е общото количество изпита минерална вода да е максимално. За всяка пътека в зависимост от това дали е сенчеста и колко е дълга е зададено едно число – количеството минерална вода, което Станчо трябва да изпие докато преминава през нея. Оптимален път за Станчо е такъв, при който първо се преминава през минимален брой кръстовища, а ако има много такива пътища – такъв, по който да се изпие максимално количество минерална вода.

Входни данни

Входните данни се четат от dual.inp. Първият ред от него има две числа N и M - броят на върховете и ребрата (N≤100000, M≤1000000). Вторият ред съдържа две числа – върхът, в който се намира Станчо в началото и върхът, до който иска да достигне. Върхове са номерирани с числа между 1 и N. Следват M реда, всеки от които описва ребро и съдържа 3 числа - двата върха, които реброто свързва и количеството минерална вода, която трябва да се изпие по този път. Ребрата са неориентирани.

Резултат

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

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

4 4
1 3
1 2 7
3 2 1
1 4 5
3 4 4

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

1 4 3

Insertsort – Сортиране чрез вмъкване – 15т.

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

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

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

Резултат:

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

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

6
1 3 2 4 5 3

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

3

Sequence – Редица със знаци – 15т.

Дадени са две цели положителни числа 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”.

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

3
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

Garbage - Събиране на боклука - 15т.

Управлението на паметта не е работа за всеки. Затова някои в езици програмистите го оставят на системата. Програмистът само създава обекти, а виртуалната машина сама решава какво и кога да изтрие. Понякога обаче и програмистът може да помогне на виртуалната машина, особено ако му притрябва памет. Да допуснем, че виртуалната машина изтрива паметта за тези обекти, до които не може да се достигне от някакъв основен глобален обект – root. Да се напише програма, която съветва програмиста кой обект да изтрие ръчно, за да може виртуалната машина да освободи най-много памет след това. Кореновият обект не може да бъде изтриван.

Входни данни

Входните данни са дадени в текстов файл с име memory.inp. Фалът съдържа всички връзки между обектите в паметта. На първият ред от него се намират естествените числа N и M – броят на връзките между обекти (0-100) и най-големият адрес на обект(2-50). Следват N реда с връзки от вида

<номер> интервал <номер>

Където <номер> са естествени числа – адреси на обекти и редът „0 2” означава, че обекта с адрес 0 съдържа указател към обекта с адрес 2. Кореновият обект (root) е с адрес 0.

Резултат

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

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

7 5
0 1
0 2
1 4
1 5
2 3
2 4
4 5

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

2

Задачи от 20т.

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

Във ФМИ преподавателите силно намалели... Някои от тях