+=====+ Задачі 1-го туру Вiдкритої Всеукраїнської iнтернет-
+=UKR=+ олiмпiади з iнформатики NetOI-2006  
+=====+         (13.10.06-28.10.06)
+========================================================
Шановні  учасники  олiмпiади! Вiтаємо  Вас з початком 1-го
туру! 

Ви маєте можливiсть багаторазово перевiрити свої розв'язки
на тестах з умов задач  перед вiдправкою в системi он-лайн
перевiрки (не плутайте з вiдправкою через веб-форму!)
Розв'язки задач слiд надiслати  до  0 годин    28    жовтня 
2006 р. листом, ЩО ОФОРМЛЕНО ЗА ПРАВИЛАМИ, або надiслати їх
через  веб-форму. 

ЗА ПРАВИЛАМИ РОЗВ'ЯЗОК МОЖЛИВО НАДIСЛАТИ НА ПЕРЕВIРКУ 1 РАЗ.

Правила російською мовою  можна  замовити листом за адресою
olymp@olymp.vinnica.ua з командою send_rules  в ТIЛI листа,
(send_urules - українською), на лист з командою send_round1
ви отримаєте в вiдповiдь цей текст
Графiк он-лайн консультацiй:  16.10.06 та  17.10.06 з 19-00 
до 19-30 
Умови задач дивіться  також на 
http://www.olymp.vinnica.ua/i2006/tour1_u.shtml
Журі олімпіади
=============================================================
Задача Failure
     Дві залізниці перетинаються під прямим кутом.  Початок  координат
розташовано  в  точці їх  перетину,  а  координатні  осі співпадають з 
рейками. Для запобігання аварій на перехресті чергує диспетчер, але як 
часто буває, він заснув на робочому місці.  У той час два поїзди мчали 
назустріч  один одному  по різних коліях. Відомі швидкості поїздів, їх 
довжини та початкові координати "голів" поїздів,  при цьому  початкові 
координати додатні.
Визначте, чи трапиться катастрофа.
     Технічні умови: програма читає з клавіатури кількість контрольних 
прикладів Т (не більше 10).  Далі - Т  груп  по 8 дійсних чисел:  V1 - 
швидкість першого поїзда, V2- швидкість другого  поїзда,  L1 - довжина 
першого поїзда,  L2  -  довжина  другого  поїзда,  X1, Y1 - координати 
"голови" першого поїзда, X2, Y2 - координати "голови"  другого поїзда. 
Усі числа не перевищують 5000, вводяться в  один  рядок через пропуск.
Програма  виводить  на  екран  для  кожного  тесту 1,  якщо  трапилась
трагедія, і - 0, якщо  все минулось добре. Усі числа виводяться в один 
рядок без пропусків між ними,  а також  на  початку та  в кінці рядка. 
Якщо "голова" одного поїзда чиркне "хвіст" іншого, то вважати,  що всі 
відбулись легким переляком, а тому вивести 0.
Приклад
Введення
2 100.0 1.0 2.0 2.0 2.0 0.0 0.0 100.0 20.0 20.0 5.0 5.0
0.0 3.0 4.0 0.0 
Виведення
01

Задача Pool
  Стіл для нашої гри має прямокутну форму з пружними бортами і  лузами 
по кутках.  На  столі  знаходяться дві  кульки з вбудованими датчиками 
пройденого шляху. Відлік шляху починається з  моменту удару по одній з 
кульок  києм  і  закінчується після зіткнення з іншою кулькою, але при 
обов'язковому дотику першою кулькою хоча б одного з двох бортів. Суддя 
ставить  кульки на початкові точки, а учасники по черзі роблять удари.
Перемагає  той, чия кулька пройде меншу відстань до зіткнення з другою 
кулькою. Написати  програму, яка обчислює мінімально можливу відстань, 
пройдену першою кулькою.
  Технічні умови: Програма зчитує з клавіатури 2 додатніх числа XMax і 
YMax (кожне не перевищує 1000) - координати кутка  стола  (протилежний 
по діагоналі кут знаходиться в початку координат), і ще 2 пари дійсних 
чисел - X1,Y1,X2,Y2 - відповідно  координати  першої та другої кульок. 
Програма виводить на екран, не округлюючи, одне дійсне число -  шукану 
величину.
Приклад
Введення
10.0 10.0 4.0 8.0 8.0 4.0
Виведення
8.94427190999159Е+000

Задача Area
     У  деякій столиці деякої держави була фірма  "Еліт-Околиця",  яка 
займалась  продажем  земельних  ділянок за містом. і все було б добре, 
якби ця фірма була чесна. Але шахраї, мало того, що забрали всі  гроші 
та втекли за  кордон,  при продажу вказували неправильні межі ділянок. 
Ділянки завжди мали форму прямокутника  з паралельними  осям координат 
сторонами. Серед потерпілих були  Петро П. і  Юлія Т.  і вирішили вони
дізнатись, чи не взяли з них одночасно гроші за одну  й ту  ж землю. А 
якщо частина землі чи границі ділянок  є  спільними,  з'ясувати  форму 
спільної  частини  (відрізок, точка, прямокутник, не співпадають). Але 
оскільки Юля  багато  часу  витрачає на заплетення своєї коси, а Петро 
погано вчився в школі, то цю задачу вони пропонують вирішити Вам.
     Технічні умови: Програма читає з клавіатури кількість контрольних 
прикладів Т (не більше 100). Далі читає Т груп вершин по 4 в кожній  - 
координати  протилежних  вершин  ділянок,   проданих   Юлі  та   Петру 
(-1000<Хі, Уі<1000).  Усі  числа вводяться одним рядком через пропуски. 
Ваша програма повинна  вивести  на екран (в один рядок, без пропусків) 
для кожної пари ділянок:
  0 - не мають спільних точок;
  1 - дотикаються в одній точці;
  2- перетинаються по відрізку;
  3 - накладаються прямокутником.
Приклад
Введення
2 0 0 2 2 2 2 4 0 0 0 1 1 1 2 2 3
Виведення
20

Задача SuperNet
    Для організації роботи нашого центру дистанційної освіти всі школи 
міста довелось з'єднати проводовими  каналами  зв'язку  попарно,  а  в 
кожній школі всі проводи, що йдуть  до  неї,  з'єднати  в вузол. Канал 
фізично  є  провідником  з  опором  R, причому  ця  величина  однакова 
для всіх прокладених ліній  (не варто обговорювати доцільність  -  так 
вирішили фахівці). При підключенні кожної школи,  починаючи з третьої,
зв'язківці вимірювали опір між кожною парою шкіл,підключених до мережі 
на даному етапі, використовуючи дуже точний цифровий омметр. Коли  всі 
школи  були  підключені,  вони  порахували,  скільки  разів результати 
вимірювання виявились цілим числом. Хай це зробить і ваша програма.
  Технічні умови: Програма читає з клавіатури ціле  число R - опір між 
кожною парою шкіл (1<=R<=10000), далі-натуральне число N (3<=N<=10000) 
- кількість шкіл.  Усі  числа  вводяться  одним  рядком через пропуск. 
Програма виводить на екран  одне  ціле число - кількість цілочисельних 
вимірювань.
Приклад
Введення
8 10
Виведення
34

Задача Dictionary
 У тарабарській мові N символів - перші N латинських букв. Тарабарські 
слова містять всі літери,  причому  кожна  буква зустрічається в слові 
один раз.  Головний  тарабарський  філолог склав  словник, у якому всі 
можливі слова містяться в алфавітному порядку. Допоможіть йому  знайти 
слово за його номером.
   Технічні умови: Ви вводите з клавіатури кількість букв N (2<=N<=12) 
і номер слова k (1<=k<=N!). Ви виводите на екран тарабарське слово.
Приклад:
Введення
4 5
Виведення
adbc

+=====+ Задачи 1-го тура открытой Всеукраинской интернет-
+=RUS=+ олимпиады по информатике NetOI-2006  
+=====+         (13.10.06-28.10.06)
+=========================================================
Уважаемые участники олимпиады! Поздравляем  Вас  с началом 
1-го тура! 

Вы можете многократно проверить свои решения на тестах  из 
условий задач перед отправкой в системе  он-лайн  проверки 
(не путайте с отправкой через веб-форму!)
Решения задач следует отослать до 0 часов 18 октября 2006 г. 
письмом,  ОФОРМЛЕНЫМ  ПО  ПРАВИЛАМ, либо отослать их через  
веб-форму. 

ПО ПРАВИЛАМ РЕШЕНИЕ МОЖНО ОТСЫЛАТЬ НА ПРОВЕРКУ 1 РАЗ.

Правила на русском языке  можно  заказать письмом по адресу
olymp@olymp.vinnica.ua с командой send_rules  в ТЕЛЕ письма,
(send_urules - на украинском), на письмо с командой 
send_round1 вы получите в ответ этот текст.
График он-лайн консультаций: 16.10.06   и  17.10.06 с  19-00 
до 19-30 
Условия задач смотрите также на 
http://www.olymp.vinnica.ua/i2006/tour1.shtml

Жюри олимпиады
============================================================
Задача Failure

Две железнодорожные  ветки  пересекаются под  прямым   углом.  Начало 
координат расположено в точке  их  пересечения,  а  оси  совпадают  с 
рельсами.Во избежание аварий на перекрестке дежурит диспетчер, но как
часто бывает, он  заснул  на  рабочем месте. Тем временем два  поезда  
мчались в сторoну  перекрестка  по   разным веткам.  Известны скорости 
поездов,  их длины и  начальные координаты  <голов>  поездов,при этом 
начальные координаты положительные.
Определите,произойдет ли катастрофа.
  Технические условия:  Программа  читает    с  клавиатуры количество 
контрольных  примеров   Т  (не   более  10).  Далее - Т групп   по  8 
действительных чисел:  V1 - скорость  первого  поезда, V2  - скорость 
второго поезда, L1 - длина первого поезда,L2 - длина второго поезда,
X1, Y1 -  координаты  <головы>  первого поезда, X2,  Y2  - координаты  
"головы" второго.Все числа не превышают 5000,вводятся  в одной строке
через пробелы. Программа  выводит   на  экран  для  каждого теста  1, 
если произошла  трагедия,  0, если  все  обошлось хорошо.  Все  числа 
выводятся в одну строку без пробелов между ними, а также  в  начале и 
конце строки.  Если  <голова>  одного поезда  чиркает <хвост> другого, 
то считать, что все отделались легким испугом, а потому вывести 0. 
Пример:

Ввод
2 100.0 1.0 2.0 2.0 2.0 0.0 0.0 100.0 20.0 20.0 5.0 5.0 0.0 3.0 4.0 0.0
Вывод
01   

Задача POOL

Стол  для  нашей  игры  представляет  собой  прямоугольник с  упругими
бортами и  лузами  по углам. На столе находятся 2  шара со встроенными 
датчиками пройденного пути.  Отсчет  пути  начинается с  момента удара 
по одному из шаров кием и  заканчивается  после столкновения со вторым  
шаром, правда, при  обязательном касании  первым шаром хотя бы  одного 
из бортов. Судья ставит шары на исходные точки, а участники по очереди 
совершают удары.Побеждает тот, чей шар пройдет меньшее  расстояние  до 
столкновения со вторым шаром.  Напишите программу, которая  рассчитает 
минимально возможное расстояние, пройденное первым  шаром. 
Технические условия:Программа считывает с клавиатуры два положительных 
действительных числа  XMax и YMax(каждое не превышает 1000)-координаты 
угла  стола   (противоположный   по  диагонали  угол  лежит  в  начале 
координат), и еще 2  пары  действительных  чисел  -   X1, Y1, X2, Y2 -
соответственно координаты первого и второго шаров.Программа выводит на 
экран,не округляя, одно действительное число  -  искомую величину.  
Пример:

Ввод 
10.0  10.0   4.0  8.0  8.0  4.0  

Вывод 
8.94427190999159Е+000


Задача  Area

В некоторой столице некоторого государства была фирма  <Элит-Окраина>,
которая занималась продажей земельных участков за городом.  И все было
бы хорошо, если бы эта фирма была честная. Но мошенники мало  того,что
забрали все деньги и смылись за границу, они  при   продаже  указывали 
неверные границы участков. Участки всегда  имели  форму прямоугольника
с параллельными  осям  координат  сторонами.  Среди потерпевших   были
Петя П.и Юлия Т. И решили они узнать,не содрали  ли с них одновременно
деньги за одну и ту же землю, а  если часть земли или границы участков 
окажутся общими-узнать форму общей части (отрезок,точка,прямоугольник, 
не совпадают). Но  поскольку  Юля  много  времени тратит на заплетание 
своей косички,  а  Петя  плохо  учился  в  школе, то  эту  задачу  они 
предлагают решить Вам. 

Технические условия:
       Программа читает с клавиатуры количество контрольных примеров Т
(не более 100)   Далее   читает   Т  групп по 4 целых числа в каждой - 
координаты противоположных  вершин участков,  проданных  Юле  и  Пете. 
(-1000< Xi,Yj < 1000 ).Все числа вводятся одной строкой через пробелы.
Ваша  программа  должна  вывести  на  экран  (все в одну  строчку, без
 пробелов) для каждой пары участков:
   0 - не имеют общих точек;
   1 - касаются в 1 точке;
   2 - пересекаются по отрезку;
   3 - накладываются прямоугольником;
Пример:        
Ввод
2  0  0  2  2  2  2  4  0  0  0  1  1  1  2  2  3 
Вывод
20  

Задача  SuperNet

Для организации работы нашего  центра  дистанционного  образования все 
школы города пришлось соединить   проводными  каналами  связи попарно,
а в  каждой  школе все ведущие к  ней  каналы соединить в общей точке.
Канал физически представляет собой  провод с сопротивлением R,  причем 
эта величина одинакова для всех проложенных линий (не стоит  обсуждать
целесообразность - так  решили специалисты).  При  подключении  каждой 
школы, начиная с третьей, связисты измеряли сопротивление между каждой
парой школ,подключенных к сети на данном этапе, используя особо точный
цифровой омметр.Когда все школы были подключены, они посчитали,сколько
раз результаты измерений  оказались  целым числом. Пусть это сделает и 
ваша программа.     
Технические условия: Программа  читает  с  клавиатуры целое  число R - 
сопротивление провода между каждой парой  школ (1<=R<=10000), далее  - 
натуральное число N (3<=N<=10000) - количество школ.Все числа вводятся
одной строкой через пробел.Программа выводит на экран одно целое число
- количество целочисленных измерений.  


Пример:
ВВОД
8 10

ВЫВОД 
34
 
Задача Dictionary

В тарабарском языке N символов - первые N латинских букв.  Тарабарские 
слова содержат все буквы, причем каждая буква встречается в слове один 
раз. Главный тарабарский филолог составил словарь, включив в  него все 
возможные  слова  в  алфавитном  порядке.  Помогите ему найти слово по 
номеру.
 
Технические условия:
Вы вводите  с  клавиатуры количество букв N (2<=N<=12) и номер слова k
(1<=k<=N!). Вы выводите на экран тарабарское слово.
 
Пример:
Ввод
4 5 
Вывод
adbc
                        ==============================================
                        А. Ботезату, Г.Кравец, Г.Непомнящий, Ю.Пасихов  

