Заочна олімпіада з інформатики.
	Хмельницька область 2003 - 2004
	
		Тур 3 
	15.12.2003 - 25.12.2003
				

Умови проведення туру:
1. Розв'язки надсилаються за адресою kobold@binet.com.ua.
2. Копія розв'язку надсилається за адресою tur3@oiuv.infocom.khmelnitskiy.ua.
3. В темі листа слід вказати: ZOI_2003.
4. Розв'язки задач приймаються до 23:59 25.12.2003 включно.
5. Розв'язок кожної задачі можна надсилати до 3-х разів за тур.
   Зараховано буде останній надісланий розв'язок.
6. Запитання по умовах задач надсилайте за адресою kobold@binet.com.ua
   без обмежень по часу.
7. Розв'язок задачі надсилається у вигляді одного файлу з текстом програми.
8. Приймаються розв'язки на мовах програмування Turbo Pascal 7.0 (DOS),
   Borland C++ 3.1 (DOS).
9. Файл з розв'язком задачі повинен мати назву UnnnTxZy.rrr,
   де nnn - код учасника туру, x - номер туру, y - номер задачі,
   rrr - розширення PAS для розв'язків на мові Pascal
   або CPP для розв'язків на мові C++.
10. Інші умови дивіться в положенні про заочну олімпіаду.

Якщо в умові задачі не зазначено інше, то діють наступні
вимоги до оформлення розв'язків:
1. Файл з розв'язком задачі не повинен перевищувати
   за розміром 8k.
2. Час на проходження будь-якого тесту не повинен
   перевищувати 3 сек на Celeron III 566 MHz
   (за умови, що вхідний та вихідний потоки
    перенаправлені в файл).
3. Вхідні дані читаються з стандартного потоку вводу
   (input в Pascal, cin в C++).
4. Вихідні дані виводяться в стандартний потік виводу
   (output в Pascal, cout в C++).


Задача 1. Стрічка Фібоначі (20 балів)
	
Визначимо ряд стрічок Фібоначі наступним чином.
S[1] = "a", S[2] = "b", S[i] = S[i-2] + S[i-1],
де операція "+" означає "склеювання" двох стрічок
в одну.

Необхідно визначити, яка літера буде n-ою літерою
стрічки S[45]. 1<=n<=1134903170.

Вхідні дані:
Вхідний потік містить в першій стрічці єдине число -
значення n.

Вихідні дані:
У вихідний потік слід помістити одну літеру, що
знаходиться в позиції n в стрічці S[45].

Приклад:
Вхідний потік:  701408733
Вихідний потік: b


Задача 2. Перетин трикутників (30 балів)

Визначіть, чи перетинаються два трикутники A і B, задані
координатами своїх вершин (Ax1;Ay1), (Ax2;Ay2), (Ax3;Ay3)
та (Bx1;By1), (Bx2;By2), (Bx3;By3) відповідно. Всі
координати - цілі числа в діапазоні від -10000 до +10000.
Вершини трикутників та їх сторони гарантовано не
співпадають.

Примітка: рахується, що трикутники перетинаються, якщо на
площині існує така точка, що знаходиться всередині обох
трикутників.

Вхідні дані:
В першій стрічці вхідного потоку міститься 6 цілих чисел
розділених пропусками - координати першого трикутника:
Ax1 Ay1 Ax2 Ay2 Ax3 Ay3.
В другій стрічці вхідного потоку міститься ще 6 чисел -
координати другого трикутника:
Bx1 By1 Bx2 By2 Bx3 By3.

Вихідні дані:
У вихідний потік слід вивести символ "+", якщо трикутники
перетинаються, або символ "-", якщо ні.

Приклад:
Вхідний потік:
0 2 0 6 4 2
1 0 5 0 1 4
Вихідний потік:
+


Задача 3. Гігантоманія (50 балів)

Розкладіть на прості множники число n! (n-факторіал),
2<=n<=100000.

Примітка: факторіалом числа n є число, що дорівнює добутку
всіх цілих чисел від 1 до n включно. Наприклад 5!=1*2*3*4*5.

Вхідні дані:
Вхідний потік містить в першій стрічці єдине число -
значення n.

Вихідні дані:
Виведіть в одну стрічку вихідного потоку степені
простих множників у вигляді
=<множник>^<степінь>*<множник>^<степінь>*...
Множники у вихідному потоці повинні слідувати в порядку
зростання.

Приклад:
Вхідний потік:  10
Вихідний потік: =2^8*3^4*5^2*7^1

Примітка:
дозволений час на проходження тесту для задачі 3 - 5 сек.


КІНЕЦЬ ФАЙЛУ