ЗИМНИ МАТЕМАТИЧЕСКИ ПРАЗНИЦИ, БУРГАС

29 януари 2005

ТЕМА ЗА  ГРУПА А (12 КЛАС)

 

Задача A1. РАЗСТОЯНИЯ

 

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

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

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

 

Входните данни се четат от стандартния вход. Първият ред съдържа три цели числа, разделени с по един интервал – броя на сензорите N(4 ≤ N≤ 1000), номера на сензора където се намира оръдието и номера на другия сензор фиксиран от Иван. Можете да приемете, че сензорите са номерирани с числата от 1 до N. Следващите редове до края на файла описват известните разстояния между двойките сензори, без повторения. Всеки такъв ред съдържа три числа, разделени с интервал – номерата на двата сензора и разстоянието между тях, с точност до осмия знак след десетичната запетая. Всички разстояния ще са по-малки от 15 000 и никои три сензора няма да лежат на една права.

Резултатът трябва да бъде изведен на стандартния изход и трябва да се състои от Nреда, всеки съдържащ по едно дробно число, закръглено до втория знак след десетичната запетая – разстоянието от оръдието до сензора със съответния номер (първият ред съответства на сензор номер 1, вторият – на номер 2 и т.н.)

 

 

                                 

 

ПРИМЕР 1                                                                                ПРИМЕР 2

 

Вход                                        Изход                                      Вход                                        Изход

4 1 2                                         0.00                                          4 3 4                                         2.24

1 2 1.41421356                          1.41                                          1 2 1.00000000                          1.41

1 3 1.41421356                          1.41                                          2 3 1.41421356                          0.00

2 3 2.00000000                          2.00                                          2 4 1.41421356                          2.00

2 4 1.41421356                                                                          3 4 2.00000000

4 3 1.41421356                                                                          4 1 2.23606798

                                                                                                1 3 2.23606798

 


 

ЗИМНИ МАТЕМАТИЧЕСКИ ПРАЗНИЦИ, БУРГАС

29 януари 2005

ТЕМА ЗА  ГРУПА А (12 КЛАС)

 

Задача A2. ВИРУС

 

Пешо Хакера работи за небезизвестната компания Banda Software. Веднъж в Bandaполучили e-mail от разтревожен клиент, в чиято система се бил настанил вирус. Вирусът очевидно бил нов, защото не се разпознавал от популярния антивирусен пакетBanda Antivirus Pro Aluminum, въпреки че последният бил въоръжен с най-съвременните вирусни дефиниции. От Bandaвъзложили задачата по локализирането на вируса на Пешо, който след внимателен анализ на изпратените от клиента заразени файлове, открил следното:

1.    Всяка от изпратените програми била заразена

2.    Вирусът заразявал програмите като замествал част от кода им (последователност с дължина равна на дължината на вируса) със своя собствен. Заместването ставало на случайно място;

3.    Вирусът не заразявал вече заразени програми повторно;

4.    Вирусът не променял кода си (не мутирал);

5.    Дьлжината на кода на вируса била не повече от 1/2 и не по-малко от 1/10 от дължината на кода на най-късата програма изпратена от клиента

Въпреки, че е добър анализатор, Пешо не се справя добре с програмирането, затова оставя тази работа на вас. Вашата задача е да напишете програма VIRUS.EXEкоято по зададени заразени програми вьзстановява кода на вируса.

 

Не пьрвия ред на стандартния вход е записано едно число N(2 £ N £ 20) – броят на заразените програми. Следват Nреда, всеки описващ по една програма. Кодът на всяка програма се представя като низ съставен от цифрите 0-9 и главните латински букви A-F без никакви разделители. Дължините на всяка от програмите не надминава 50,000 символа.

 

На единственият ред на стандартния изход програмата трябва да изведе кода на вируса в същия вид, в който се среща във входните данни. Измежду всички низове – „кандидати” за вирус, истинският е този с най-голяма дьлжина. Входните данни гарантират наличието на решение (вирус), при това еднозначно, т.е. съществува единствен кандидат с най-голяма дльжина.

 

ПРИМЕР

Вход

3

1111111111517561111111111

01234517566789ABCDEF

010101010105175610100101010101

 

Изход

51756

ЗИМНИ МАТЕМАТИЧЕСКИ ПРАЗНИЦИ, БУРГАС

29 януари 2005

ТЕМА ЗА  ГРУПА А (12 КЛАС)

 

 

Задача A3. ПРЕГРАДА

 

Дадени са N дъски с правоъгълна форма, номерирани с числата от 1 до N(N<2000). Дъските са с еднаква ширина, но с различна височина, като K-тата дъска е високаK дециметра. Подреждаме N-тедъски една до друга, така че да образуваме преграда. В зависимост от начина на подреждането се образуват участъци с последователно намаляващи дължини на дъските. Тези участъците обикновенно са повече от един, но може и цялата преграда да образува само един участък. Възможно е някои участъци  да се състоят само от една дъска. Например, ако подредим 9 дъски, така че височините им да образуват последователността 6, 4, 2, 5, 3, 9, 7, 2, 1, 8, имаме 4 такива участъка 6, 4, 2;  5, 3;  9, 7, 2, 1 и 8. Колко от всичките възможни наредби на дъските ще образуват преграда, съдържаща точно P участъка (0 < P < N + 1). Напишете програмаHEDGE.EXE,  която решава тази задача.

 

Програмата трябва да прочете от стандартния вход стойностите на Nи P, разделени с един интервал и да изведе на стандартния изход търсения брой прегради по модул 1020847 (т.е. остатъка на търсения брой при деление на 1020847). В 50% от тестовете N < 20.

 

ПРИМЕР 1                                            ПРИМЕР 2

 

Вход                                                    Вход

4 3                                                        20 2

 

Изход                                                  Изход

11                                                         27708