Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Завдання 3-го туру (02.02.03-16.02.03)

Задача MOONROVER

        У свiй час ЛУНОХОД, робот-вiзок, доволi довго повзав по мiсячнiй поверхнi. Як вiдомо, Мiсяць покритий кратерами. ЛУНОХОД може рухатись або мiж ними, або по їх краю. Визначити довжину найкоротшого шляху МIСЯЦЕХОДА мiж двома точками на мiсячнiй поверхнi мiж кратерами. Кратери представляють собою правильнi кола.

Введення-виведення.

        Ви вводите з клавiатури кiлькiсть кратерiв К (0<=К<=15), а потiм К разiв по 3 дiйсних числа - координати центра i радiус вiдповiдного кратера, а далi ще 4 дiйсних числа - координати початку i кiнця маршруту МIСЯЦЕХОДА. Всi числа вводяться через пробiл.
        Ви виводите 1 дiйсне число - мiнiмальну довжину маршруту.

Приклад

Введення> 2 2 1 1 6 2 2 0 1 10 2
Виведення < 1.07669487495015E+0001

Задача CONSTRUCTION

        Будiвельники встановлювали колону у виглядi прямокутного паралелепiпеда {(x,y,z)|0<=x<=A,0<=y<=B, 0<=z<=C}. Для полегшення роботи їм необхiдно натягнути по поверхнi колони мотузку мiнiмальної довжини вiд точки з координатами (x1, y1, z1) до точки з координатами (x2, y2, z2). Мотузка може проходити по будь-якiй точцi поверхнi колони. Допоможiть будiвельникам знайти квадрат довжини необхiдної для цiєї мети мотузки.

Введення-виведення.

        Ви вводите з клавiатури у зазначеному порядку 9 цiлих чисел через пробiл: А B C x1 y1 z1 x2 y2 z2 (кожне з чисел A,B,C не перевищує 100).
        Ви виводите на екран єдине число - квадрат довжини мотузки.

Приклад

Введення> 3 4 4 1 2 4 3 2 1
Виведення < 25

Задача ROSEN

        Концерн ROSEN випустив N шоколадок, присвоївши їм номери вiд 1 до N, для новорiчних подарункiв дiтям, по двi шоколадки кожному. Написати програму, що розподiляє цi шоколадки мiж максимально можливою кiлькiстю дiтей так, щоб сума номерiв шоколадок у кожної дитини виражалась простим числом.

Введення-виведення.

        Ви вводите з клавiатури одне число N (N<=500000). Ви виводите на екран список знайдених пар, числа роздiленi пробiлами.

Приклад

Введення> 7
Виведення < 1 6
Виведення < 7 4
Виведення < 5 2

Задача POLICY

        Парламент деякої країни складається з представникiв 3-х партiй (A,B,C), якi знаходяться на рiзних полiтичних платформах. Майже кожна пропозицiя не набирала потрiбного числа голосiв. Ну, хiба що хтось умовить представника iншої партiї,який сидить поруч. Спiкер,досвiдчений полiтик, запрошував на засiдання тимчасових комiсiй N депутатiв з рiзних партiй в будь-якому спiввiдношеннi, розсаджував їх, як хотiв, тому що давно пiдрахував "коефiцiєнти деструкцiї"(КД) присутностi та розмiщення депутатiв, а зал засiдань мав 1 ряд крiсел, розташованих злiва направо. Наприклад, якщо поруч сидять "АВ", то КД=1, "САСА"- КД=100, тодi розмiщення "САСАСАВА" дає КД=201. Кого запрошував спiкер на комiсiю i як усаджував запрошених, бажаючи отримати мiнiмальний КД?

Введення-виведення.

        Ви вводите з клавiатури кiлькiсть депутатiв N (3<=N<=100), далi - кiлькiсть "ланцюжкiв" пiдряд сидячих депутатiв К з вiдомим КД(1<=К<=50), кожний "ланцюжок" складається не бiльше нiж з 6 пiдряд сидячих депутатiв. Далi в кожному з К рядкiв записаний "ланцюжок", а через пробiл-його КД. Ви виводите на екран знайдений КД та одне з можливих розмiщень депутатiв.

Приклад

Введення> 8
Введення> 9
Введення> С 10
Введення> А 10
Введення> В 30
Введення> АВ 50
Введення> СА 1
Введення> СС 10
Введення> АА 11
Введення> САС 2
Введення> АСА 3
Виведення < 98
Виведення < АСАСАСАС

Задача SUM

        Розглядаються всi розбиття натурального числа N на суму К невiд'ємних доданкiв (1<=N<=32, 2<=K<=32). Суми, що вiдрiзняються тiльки порядком доданкiв, вважаємо рiзними. Впорядкуємо всi розбиття по незростанню доданкiв i пронумеруємо їх. Наприклад, при N=4, К=3 маємо
Номер Доданки
1-й 2-й 3-й
1 4 0 0
2 3 1 0
3 3 0 1
4 2 2 0
5 2 1 1
6 2 0 2
7 1 3 0
8 1 2 1
9 1 1 2
10 1 0 3
11 0 4 0
12 0 3 1
13 0 2 2
14 0 1 3
15 0 0 4
Напишiть програму, яка знаходить розбиття за номером або номер за розбиттям.

Введення-виведення.

        Ви вводите з клавiатури 0, якщо необхiдно знайти розбиття за номером, i 1, якщо номер за розбиттям. В першому випадку ви вводите кiлькiсть доданкiв, суму та номер розбиття. У другому випадку ви вводите кiлькiсть доданкiв i потiм розбиття. Всi числа роздiленi пробiлами.
        Ви виводите на екран розбиття або номер.

Приклади

Введення> 0 3 4 9
Виведення < 1 1 2

Введення> 1 3 1 2 1
Виведення < 8


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"