Форум Поща Карта на сайта Търсене Връзки Контакти
Начало Студенти Състезания Конкурс по програмиране    English
Факултет по математика и информатика - Конкурс по програмиране
ФМИ обявява конкурс по програмиране

ПРАВИЛА:

Право на участие имат всички студенти от Пловдивски университет. Конкурсът ще се проведе в три кръга. Всеки кръг се дават по две задачи, като трудноста им във всеки следващ кръг се увеличава. Срокът за решаването на задачите е както следва:

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

 

 

Актуално
Още новини
Архив на новините
© 2009 ФМИ