ФМИ обявява конкурс по програмиране
ПРАВИЛА:
Право на участие имат всички студенти от Пловдивски университет. Конкурсът ще се проведе в три кръга. Всеки кръг се дават по две задачи, като трудноста им във всеки следващ кръг се увеличава. Срокът за решаването на задачите е както следва:
1 кръг: 10 април
2 кръг: 18 април
3 кръг: 26 април
Обявяването на резултатите и награждаването на първенците ще стане на 28 април. От тях ще бъдат сформирани отборите по програмиране, които ще защитават честта на ФМИ в олимпиади и състезания.
Допустими езици за програмиране са Pascal, Java u C++ (позволени са и визуални среди за програмиране, но програмата трябва да е конзолна). Решенията трябва да включват:
* по един изпълним файл за всяка от решените задачи (тези файлове ще бъдат тествани)
* програмния текст, като при компилирането му не трябва да има разлика с изпълнимия файл
* текстов файл съдържащ трите имена, фак. номер и специалност на студента-участник.
* по желание описание на използвания алгоритъм - също в текстов файл (не се оценява)
Препоръчителни среди за програмиране:
C++ : http://www.microsoft.com/express/vc/
Java6 + NetBeans (IDE) : http://java.sun.com/javase/downloads/netbeans.html
Паскал: http://www.freepascal.org/download.var
Всички решения, както и въпроси по задачите изпращайте на адрес nvalchanov@gmail.com.
Първи кръг (25 точки)
Първа задача. Вирус е нападнал текстови файлове и прави следните повреди: когато стигне до положително число, записва след числото още една нула, а ако срещне паричен знак „лв.” след число, го заменя със знак за $ преди него. Да се състави програма, с която:
а) се въвежда на един ред текст, състоящ се от не повече от 200 символа.
б) се правят същите повреди върху въведеният текст както от описания по-горе вирус и на екрана се извежда повреденият текст.
ПРИМЕР:
Вход: Изход:
Донев 800 лв. за два месеца Донев $8000 за два месеца
Втора задача. Популярната игра “Бици и крави” има следните правила. Играят двама играчи символично означени с А и В. Всеки от тях, без знанието на другия си избира едно четирицифрено число, като в играта не участват числата започващи с 0. Целта на играта е с най-малко ходове единия играч да познае числото на другия. Един ход от играта се състои от въпрос, зададен от единия играч и съответен отговор на другия играч. При следващия ход играчите разменят ролите си. Всеки въпрос е задаване на число к от указания по горе вид, а съответния отговор е m “крави” и n “бици”, като m показва броя на познатите цифри в намисленото число, които не са на позициите си, а n показва броя на познатите цифри в намисленото число, които са на позициите си. Ако за познаване на числото 7209 намислено от играча А, В зададе числото 1290 отговорът на А е 2 “крави” и 1 “бик”. Да се състави програма, с която се реализира играта “Бици и крави”, като играч А е компютърът, а В е човек застанал зад клавиатурата.
Втори кръг (40 точки)
Първа задача. Дадена е редицата 1, 2, 3, 4, 5, 6, 7, 8, 9, .... N. Между всеки два елемента от редицата можете да поставите + или -.
Съставете програма, която изчислява минималната дължина на редица, с която можете да изразите дадено число M.
На входа програмата трябва да приема числото M (1 <= M <= 100 000).
На изхода трябва да извежда цяло число представляващо броя на елементите на намерената редица.
Вход: Изход:
11 5
Втора задача. Иван обича да пие бира, но е изправен пред проблем. Срещу него в редица са наредени N на брой бирени бутилки от M на брой различни марки. Поради физически ограничения Иван не може да се справи с цялото количество на веднъж. За целта той е решил да намери най-късата подредица от бутилки, която съдържа поне по една от всички M марки, за да може да опита поне по една от всички бири.
Помогнете на Иван като съставите програма, която на входа приема N на брой реда (100000 <= N <= 4000000000). Всеки ред идентифицира поредната бутилка бира. Реда съдържа типа на бирата - цяло число M (1 <= M <= 10000). Четенето на входни данни приключва при прочитане на -1.
На изхода програмата трябва да извежда позицията на първата и последната бутилка бира от намерената подредица.
Вход: Изход:
1 6
2 16
3
4
4
1
2
3
4
5
6
7
5
8
9
10
-1
Трети кръг (60 точки)
Първа задача. Селищата на един планински район, номерирани с целите числа от 1 до N, са свързани с пътища така, че от всяко селище до всяко друго селище има единствен път. Пътните отсечки свързващи отделните селища са с почти една и съща дължина, а като се има предвид и недоброто им качество, спокойно можем да приемем, че всяка от тях се преминава за едно и също време. По проект финансиран от Европейската общност са отпуснати средства за нова пожарна команда в района и сега трябва да се избере селището, където да се построи пожарната. Естествено е мястото да се избере така, че до най-отдалеченото от него селище да се достига за колкото може по-малко време. Напишете програма, която намира оптималното място за построяването на пожарната.
Входните данни ще бъдат зададени на стандартния вход. На първия ред ще бъде зададен броят N на селищата (5£N£10000) в района. На всеки от следващите N – 1 реда ще бъдат зададени, разделени с един интервал, два номера на селища, които са свързани с пътна отсечка. Никое от селищата не е свързано с пътни отсечки с повече от 100 други селища.
На стандартния изход програмата трябва да изведе дължината на пътя от избраното за построяване на пожарната команда селище до най-отдалеченото от него.
Пример Вход 6 1 6 2 3 4 6 3 5 5 6 | Изход 2 |
Втора задача. Град има N кръстовища, номерирани с числата от 1 до N (N<1000)) и М улици (М<2000), като всяка улица свързва две кръстовища. За всяко кръстовище е известна надморската му височина, (цяло число в интервала [100,200]), а за всяка улица - дължината й (цяло число в интервала [10,1000]). Пороен дъжд се изсипал над града, като на всяка улица паднало количество вода, равно на дължината й. Ако единият край на улица е по-ниско разположен от другия - всичката вода от улицата се оттича към по-ниско разположения. Ако двата края са на една и съща височина, тогава водата от улицата се оттича по равно към двата края. Ако от едно кръстовище тръгват улици към кръстовища, разположени на по-малка височина от него, тогава водата достигнала до това кръстовище се оттича към по-ниско разположените, като се разпределя по равно между всички улици, отиващи към по-ниски кръстовища. Ако всички улици от едно кръстовище водят към кръстовища с надморска височина по-голяма или равна на неговата, тогава водата достигнала това кръстовище се оттича в градската канализация.
Напишете програма, която по зададени N и М и съответните височини и дължини, намира номерата на кръстовищата, от които водата отива в канализацията и за всяко такова кръстовище - количеството вода, която се е оттекла в канализацията от него. Входът и изходът на програмата е реализиран по следния начин.
Вход:
В първия ред на входния файл FLOW.INP са зададени числата N и М, разделени с
един интервал. Следват N реда, във всеки от които е зададена надморската височина на едно кръстовище, в нарастващ ред на номерата им. Всеки от последните М реда описва по една улица и съдържа номерата на двата и края и дължината й, разделени с по един интервал.
Изход:
Изходният файл FLOW.OUT трябва да съдържа за всяко кръстовище, от което вода се е оттичала в канализацията по един ред с две числа - номерът на кръстовището и количеството на водата (закръглено до четвъртата цифра след десетичната точка). Номерата на кръстовищата да са подредени в нарастващ ред
Пример:
FLOW.INP
5 7
130
110
150
110
180
1 2 50
1 3 50
2 3 70
2 4 30
2 5 60
3 5 40
4 5 20
FLOW.OUT
2 285.0000
4 35.0000