Есенeн турнир по информатика, Шумен, 24 ноември 2001 г.

 

Тема за 11 – 12 клас

 

Задача 1. FENCE

 

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

 

Напишете програма fence.exe, която по зададено разположение на кулите намира дължината на оградата.

 

Входният файл fence.inp има толкова на брой реда, колкото са кулите – не повече от 1 000. Във всеки ред са записани координатите на центъра и радиусът на основата на дадена кула – цели или реални с най-много две цифри след десетичната точка числа.

 

Изходният файл fence.out има само един ред и едно число в него: дължината на оградата – реално число с две цифри след десетичната точка.

 

 

Пример:

 

fence.inp                                                         fence.out

 

10 10 10                                                          142.83

50 10 10

 

Време за работа на програмата: 3 сек.

 


Есенeн турнир по информатика, Шумен, 24 ноември 2001 г.

 

Тема за 11 – 12 клас

 

Задача 2. НЕБОСТЪРГАЧ

 

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

Помогнете на фирмата, като напишете програма BUILD.EXE, която да определи максималния възможен брой етажи на небостъргач, чиято основа е правоъгълник с размери W на H (2 <= W, H <= 11), имайки предвид, че в никои два етажа разположението на стаите не трябва да е еднакво.


Вход: Във файла BUILD.INP на един ред са записани размерите W и H на етажите на небостъргача.

Изход: Във файла BUILD.OUT изведете максималната височина на небостъргача с размерите W и H на етажите.

 

Примери:

BUILD.INP

BUILD.OUT

2 4

5

2 3

3

1 3

0

2 11

144

2 2

2

 

 

 

Време за работа 1 сек.


Есенно състезание по информатика, Шумен, 24 ноември 2001 г.

 

Тема за 11 – 12 клас

 

Задача 3. ROUTES

 

В една държава има N града (1 < N < 170), номерирани с различни цели числа от 1 до N. Между някои двойки от тези градове е построен по един пряк път. Системата от пътища е свързана, т.е. възможно е да се премине от всеки един град до всеки друг. При ремонтни работи, когато се налага да се затвори някой пряк път между два града, може да се окаже, че системата от пътища става несвързана, т.е. не е възможно да се премине между някоя двойка градове. Напишете програма ROUTES.EXE, която намира всички двойки градове, такива че при затваряне на прекия път между тях,  системата от пътища става несвързана.

 

Входните данни се четат от файла ROUTES.INP. В първия ред на файла е записано числото N. Следват N на брой реда, като i-тият от тях съдържа броя на градовете до които от i-тия град има пряк път и номерата на тези градове, разделени с по една шпация.

 

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

 

Пример:

 

ROUTES.INP

 

3

1 2

2 1 3

1 2

 

ROUTES.OUT

 

1 2

2 3

 

Време за работа на програмата 1 сек. (200 MHz, 16 MB RAM)

ОБРАТНО