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

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

Версия 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т.

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

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

1 2 1

2 3 2

1 3 4

3 4 2

1 4

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

1 2 1

2 4 1

Задача 34. Networks – Несигурните мрежи – 20т.

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

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

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

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

Резултат:

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

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

4 4

1 2

2 3

1 3

3 4

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

Задача 35. Stanchium – Оптмизиране на процесорни операции – 20т.

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

Друга интересна характеристика на Станчиум е, че последователността от операции трябва да се раздели на по една, две или три последователни операции. Всяка разделение трябва да се окомплектова в група. Всяка група има три позиции, като всяка позиция може да побера една операция, а някои позиции могат да останат празни. Всяка операция се категоризира в един от десет предварително задени типа (целочислени операции, операции с реални числа и др.), индексирани с първите десет букви от английската азбука (от ‘А’ до ‘J’). Само операции от определен тип се разрешава да бъдат окомплетовани в група. Модел на група наричаме едно възможно окомплектоване на операции в група. Моделът може също да задава позиция на стоп маркер в групата – това трябва да е в средата и може да има най-много един стоп в група. Също така, стоп се позволява между всеки две последователни групи. Когато се окомплектоват операциите в групи, трябва да се използват само зададените модели на групи.

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

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

Входните данни са дадени в текстов файл с име stanchium.inp. Всеки тестов пример (последователност от операции, които трябва да се окомплектоват) започва с ред съдържащ две числа M (1≤M≤1500) и N (1≤N≤100 000) – брой модели на групи и брой инструкции да се окомплектоват в групи. Всеки от следващите М реда съдържа 3 големи латински букви (без интервали между тях), интервал и число. Буквите описват типовите операции, които могат да се окомплектоват в този модел група, а числото, което може да е 0, 1 или 2, задава след коя позиция може да се сложи стоп – 0 означава че не може да има стоп в този модел на група. Следващите N реда съдържат по една голяма латинска буква C_i (‘A’≤C_i≤’J’) и число D_i (0≤D_i<i) разделени с интервал. Буквата задава модела на поредната операция от последователността за окомплектоване, а числото – номера на предишна операция от която зависи настоящата, ако числото е по-голямо от 0 или независимост от всички предишни операции, ако числото е 0. За всеки тип операция който трябва да се окомплектова има поне един модел на група, в който може да се окомплектова такава операция.

Резултат:

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

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

1 2

ABC 1

A 0

B 1

1 2

ABC 2

A 0

B 1

4 9

ABB 0

BAD 1

AAB 0

ABB 2

B 0

B 1

A 1

B 4

D 0

A 0

B 3

B 0

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

test case 1: 1 1

test case 2: 2 1

test case 3: 4 3

Задача 36. Party – Парти на катедрата – 25т.

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

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

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

Резултат:

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

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

6 8 4

1 2

1 3

2 3

5 3

4 3

3 6

2 5

2 6

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

Задача 37. Meeting – Среща между катедрите – 25т.

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

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

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

Резултат:

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

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

5 4

abz

abc

amp

pma

stz

mnz

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

2 4

5 3

Задача 38. Science – Научна дейност – 25т.

След последната среща между катедрите вражеската катедра обвинила Станчо, че неговата катедра няма абсолютно никаква целенасоченост и работи хаотично. Тогава Станчо решил да покаже на другите катедри че това далеч не е така и неговата катедра работи целенасочено в определена област. За съжаление не могъл лесно да определи каква точно е тази област и за това разровил архивите на катедрата и намерил всички научни открития. За всяко научно откритие той определил 3 стойности: D_i, T_i и V_i. D_iпоказва дискретността на съответното откритие – положително число означава, че то е от дискретните науки, а отрицателно, че е от непрекъснатите. T_iпоказва теоретичността на съответното откритие – положително число означава, че е теоретично, а отрицателно, че е приложно насочено. V_iпоказва колко е велико съответното откритие. Очевидно (поне за Станчо) за група открития S общата специфичност се определя по формулата:

Помогнете на Станчо да открие групата с най-голяма специфичност.

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

Входните данни са дадени в текстов файл с име science.inp. На първият ред от него стои едно число N указващо броя открития на катедрата (1 ≤ N ≤ 200 000). На следващите N реда има по 3 числа - D_i, T_i и V_i за съответното откритие.

Резултат:

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

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

1 1 5

-1 1 1

-3 -3 4

-1 0 2

5 -3 4

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

Задача 39. AllCycles – Всички цикли в граф – 25т.

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

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

Графът е описан в текстов файл с име allcycles.inp. На първия ред стоят две цели числа N и M, разделени с интервали, задаващи съответно броя върхове и броя ребра в графа. На всеки от следващите M реда има описание на едно ребро от графа – 2 числа, разделени с интервал, задаващи съответно начален връх и краен връх на реброто.

Резултат:

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

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

11 13

1 2

1 4

2 3

2 4

3 4

3 5

5 6

6 7

6 8

7 8

9 10

9 11

10 11

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

Задача 40. Chess1 – Опростен шах 1 (мат с цар и два офицера срещу цар) – 25т.

Да се проектира и реализира алгоритъм, който играе опростен шах и винаги побеждава след минимален брой ходове. При опростен шах се играе на стандартна шахматна дъска и правилата на играта са същите като при шаха, но на дъската има ограничен брой фигури. В нашия случай има един бял цар, и два бели офицера (на позиции с различни цветове) и един черен цар. Началната позиция е валидна съгласно правилата на играта шах. Компютърът играе с белите фигури и започва първи. Целта е компютърът да матира потребителския цар за минимален брой ходове.

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

Входните данни се задават в текстов файл с име chess1.inp, който съдържа четири реда. На първия ред е записана позицията на белия цар, на втория и третия ред са записани позициите на двата офицера, а на четвъртия ред е записана позицията на черния цар. Всяка позиция се записва по стандартното за шаха означение – чрез главна латинска буква (от A до H), последвана от цифра (от 1 до 8) без разделител между тях.

Резултат:

Резултатът е интерактивна игра, при която компютърът започва пръв и след всеки свой ход дава възможност на потребителя да играе своя ход, а след това играе оптимално. В крайна сметка компютърът трябва да матира потребителя за минимален брой ходове.

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

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

Задача 41. Chess2 – Опростен шах 2 (цар и топ срещу цар и кон) – 25т.

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

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

Входните данни се задават в текстов файл с име chess2.inp, който съдържа четири реда. На първия ред е записана позицията на белия цар, на втория ред е записана позицията на белия топ, на третия ред е записана позицията на черния цар, а на четвъртия ред е записана позицията на черния кон. Всяка позиция се записва по стандартното за шаха означение – чрез главна латинска буква (от A до H), последвана от цифра (от 1 до 8) без разделител между тях.

Резултат:

Резултатът е интерактивна игра, при която компютърът започва пръв и след всеки свой ход дава възможност на потребителя да играе своя ход, а след това играе оптимално. В крайна сметка компютърът трябва да победи, ако е възможно или да постигне поне реми, ако победа не е възможна при оптимална игра на черните.

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

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

Задача 42. Maxsum – Максимална сума – 25т.

Даден е двумерен масив NxN от цели числа. Да се напише програма която намира подправоъгълника на двумерния масив с най-голяма сума на елементите. Подправоъгълник наричаме всеки подмасив с размери 1x1 или по-голям, намиращ се в дадения масив.

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

Входните данни са дадени в текстов файл с име maxsum.inp. Първия ред от него съдържа числото N (N <= 8 000) размерността на масива. Следват N² естествени числа в интервала [-127, 127] разделени с бели полета (white-space) Тези N² числа представляват масива (всички числа от първия ред от ляво на дясно, всички числа от втория ред от ляво на дясно, ...)

Резултат:

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

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

-3 1

1 4

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

Задача 43. MinSet - Минимално по брой елементи доминиращо множество – 25т.

Даден е ориентиран граф. Да се намери минималното по брой елементи доминиращо множество. Трябва да се реализират възможни оптимизации. Пълното изчерпване не е решение.

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

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

Резултат:

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

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

5 3

1 2

1 3

4 5

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

1 4

Задача 44. Rooks – Задачата за топовете – 30т.

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

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

Входните данни са дадени в текстов файл с име rooks.inp. На първият ред от него стои едно число N указващо размера на таблицата (1 ≤ N ≤ 500). На следващите N реда има по N числа описващи всяка позиция с по едно цяло неотрицателно число. Ако числото е 0 то на съответното квадратче има краставичка. В противен случай на него има чаша със съответното количество минерална вода.

Резултат:

Резултатът трябва да се запише в текстов файл с име rooks.out. Ако задачата няма решение съдържа единствен ред с числото -1. В противен случай N реда с по две числа – номерът на ред и стълб, където е поставен топ. Позициите трябва да се изведат сортирани по ред. Ако има няколко решения да се изведе кое да е от тях.

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

0 5 1 0 0

5 0 0 2 0

1 1 0 0 2

1 1 3 3 2

0 0 1 2 2

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

1 2

2 1

3 5

4 3

5 4

Задача 45. Quasirooks – Задачата за квазитоповете – 30т.

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

Имаме квадратна таблица N на N. Върху някои от позициите има краставички (минералната вода била отдавна изпита). Един квазитоп представлява фигура от 2 части – глава и тяло. Главата на квазитопа може да се разположи на ред R колона C, така че R е различно от C и тогава тялото на квазитопа трябва да бъде на ред C и колона R. И двете позиции трябва да бъдат свободни (да няма краставичка на тях). Понеже според Станчо топът е доста силна фигура то квазитопа е още по-силна и бие 2^та реда и 2те колони които заема. Така задачата е да се разположат максимален брой квазитопове така, че никои два от тях да не се бият.

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

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

Резултат:

Резултатът трябва да се запише в текстов файл с име quasirooks.out. Ако задачата няма решение съдържа единствен ред с числото -1. В противен случай на първият ред стои числото K – броят на квазитоповете поставени на дъската. Следват K реда с по две числа – номерът на ред и стълб, където е поставена главата на квазитопа. Позициите трябва да се изведат сортирани по ред. Ако има няколко решения да се изведе кое да е от тях.

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

0 0 1 1 0 0

0 1 1 1 1 1

1 1 0 1 1 0

0 1 1 0 1 0

1 0 0 1 1 0

1 1 0 0 0 0

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

1 2

5 6

Задача 46. GraphCount – Броене на планарни графи – 30т.

Както вече споменахме Станчо много обичал комбинаториката. Един ден той имал странен сън. 3 кръвожадни крави го гонели защото бил оставил полянката пред факултета без трева.... Почти се бил измъкнал, когато го пресрещнал Големият Лош Граф. Графът го сграбчил с големите си върхове и го оплел с дългите си ребра. Казал му, че ще го пусне и ще го спаси от кравите само ако напише програма, която да брои уникалните (не изоморфни един на друг) планарни графи с даден брой върхове и ребра. Пуснал го да се събуди, но му казал, че иска програмата до крайния срок за предаване на проекти по ПрАнКА. За това Станчо поискал помощ от нас.

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

Входните данни са зададени в текстов файл с име graphcount.inp. На единствения ред от него стоят 2 числа N и M указващи съответно броя върхове и броя ребра в графите (1 ≤ N ≤ 10, 1 ≤ М ≤ 50).

Резултат:

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

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

4 5

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

Задача 47. Reverse – Играта “Reverse” – 30т.

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

Понеже Станчо вече бил забравил и правилата на играта, той се разровил из Интернет и намерил 2 сайта по темата: http://takegame.com/online/reversi/ и http://www.gamesite2000.com/reversirules.htm.

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

Входните данни са дадени в текстов файл с име reverse.inp. На първият ред от него стои едно число, указващо с кои пулове играе Станчо, т.е. кои пулове са на ход. 1 означава, че белите са на ход, а 2 означава, че черните са на ход. Следват 8 реда с 8 числа, разделени с интервал. Всяко от тях има стойност 0, 1 или 2 и съответства на една позиция от дъската, като 0 означава, че позицията е свободна, 1 означава бял пул, а 2 означава черен пул.

Резултат:

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

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

0 0 0 0 0 0 0 0

0 0 0 1 2 0 0 0

0 0 0 2 1 0 0 0

0 0 0 0 0 0 0 0

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

0 0 0 0 0 0 0 0

0 0 0 1 1 1 0 0

0 0 0 2 1 0 0 0

0 0 0 0 0 0 0 0

Задача 48. Mincut – Минимален разрез на поток – 30т.

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

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

Графът е описан в текстов файл с име mincut.inp. На първия ред стоят две цели числа N и M, разделени с интервали, задаващи съответно броя върхове и броя ребра в графа (1 £ N £ 500). На всеки от следващите M реда има описание на едно ребро от графа. Едно ребро се описва от 3 числа, разделени с интервал – начален връх, краен връх и капацитет на реброто. На последния ред във входния файл стоят две числа S и T, разделени с интервал, които задават номерата на източника и консуматора, между които се търси максимален поток и минимален разрез.

Резултат:

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

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

10 14

1 2 2

1 3 3

1 4 5

2 5 3

3 5 4

3 8 2

4 8 1

5 6 1

5 7 1

6 10 3

7 10 4

8 7 3

8 9 2

9 10 1

1 10

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

5 4

3 8

4 8

5 6

5 7

Задача 49. Planar – Визуализация на планарен граф в равнината – 30т.

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

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

Графът е описан в текстов файл с име planar.inp. На първия ред стоят две цели числа N и M, разделени с интервали, задаващи съответно броя върхове и броя ребра в графа (1 £ N £ 500). На всеки от следващите M реда има описание на едно ребро от графа – 2 числа, разделени с интервал, задаващи съответно начален връх и краен връх на реброто.

Резултат:

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

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

6 12

1 2

1 3

1 5

1 6

2 3

2 4

2 6

3 4

3 5

4 5

4 6

5 6

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

Задача 50. MinCostFlow –– Неизползваните тръби – 30т.

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

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

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

Резултат:

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

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

4 4

1 2 1 10 13

2 3 2 20 17

1 3 4 40 15

3 4 2 10 16

1 4

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

2 90

1 2 1

2 4 1

1 3 1

3 4 2

Задача 51. Transportation –– Транспорт на минерална вода – 30т.

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

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

Входните данни се задават в текстов файл с име transport.inp. На първия ред на входния файл стоят целите числа M и N, разделени с интервал, които задават броя на фабриките и броя на катедрите (2 ≤ M, N ≤ 500). Следващия ред съдържа M цели положителни числа – капацитетите на всяка една от фабриките. Следващия ред съдържа N цели положителни числа – необходимите количества минерална вода на всяка една от катедрите. На следващите M реда са транспортните разходи за всяка една от фабриките, до всяка една от катедрите N цели положителни числа разделени с интервал. Ако дадена катедра не желае да закупува минерална вода от дадена фабрика то на мястото на транспортните разходи стои числото -1. По стай обичай фабриките и катедрите са номерирани с числата от 1 до M и N съответно.

Резултат:

Резултатът трябва да се запише в текстов файл с име transport.out, на първия ред на който стои минималната възможна цена за която Станчо може да достави желаните количества минерална вода. На следващите M реда са транспортираните количества минерална вода от всяка една от фабриките, до всяка една от катедрите - N цели неотрицателни числа разделени с интервал. Ако от дадена фабрика до дадена катедра не се транспортира минерална вода, то в изходния файл се поставя 0 на съответната позиция.

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

3 2

1 2 2

2 3

1 3

2 3

-1 3

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

1 0

1 1

0 2

Задача 52. Net –– Окабеляване – 30т.

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

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

Входните данни се задават в текстов файл с име net.inp. Първия ред на входния файл се състои от цялото число N, указващо дължината на кабела във всяка една ролка. На всички редове до края на файла има по две цели числа указващи съответно броя на необходимите парчета кабел и дължината им.

Резултат:

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

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

2 5

2 3

1 4

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

5 5

3 3 4

Задача 53. Automorphism –– Автоморфизъм – 30т.

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

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

Входните данни се задават в текстов файл с име аutomorphism.inp. На първия ред на входния файл стоят целите числа N и M указващи съответно броя на върховете и броя на ребрата на графа. Следващите M реда съдържат по две числа описващи всяко едно от ребрата на графа. Върховете са номерирани с числата от 1 до N.

Резултат:

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

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

5 10

1 2

2 3

3 4

4 1

1 3

2 4

5 1

2 5

5 3

5 4

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

120

Задача 54. Acquaintances –– Познанства – 50т.

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

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

Резултат:

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

Задача 55. Prime –– Прости числа – 75т.

Станчо е голям теоретик. Той забелязал, че в някои случаи, когато p е просто и 2^p-1 също е просто. Той дори нарекъл простите числа от вида 2^p-1Станчови прости, когато p също е просто. Изобщо много простотия се насъбрала на главата на Станчо в последно време. Той написал програма, която да смята всички Станчови прости, но той не е добър програмист, поне не колкото студентите по Пранка, той се нуждае от малко помощ. Напишете програма, която намира 43тото поредно Станчово просто число.

Резултат:

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

Задача 56. Functions –– Функции – 100т.

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

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