XVII обласна олімпіада з інформатики (Хмельницька обл.)
		1 лютого 2003 року
		1 тур (теоретичний)

1. Перестановка. (20 балів)
Таблицею інверсій заданої перестановки чисел від 1 до N є масив, 
K-й елемент якого рівний кількості елементів більших за K, 
що стоять у перестановці зліва від K.
Так для перестановки  3 1 5 2 4 таблицею інверсій буде: 1 2 0 1 0
Потрібно побудувати алгоритм і реалізувати його у вигляді 
програми PERM.PAS (BAS чи CPP), що прочитає вхідні дані з 
файла PERM.DAT, за даною таблицею інверсій відновить 
перестановку та виведе її у файл PERM.SOL
У першому рядку файлу PERM.DAT записано число N. 
У другому - N чисел (таблиця інверсій), розділених пропуском. 
(1<=N<=100)
У файл PERM.SOL необхідно записати шукану перестановку.
Приклад:
PERM.DAT
5
1 2 0 1 0

PERM.SOL
3 1 5 2 4

2. І знову Фібоначчі… (40 балів)
Перше та друге числа Фібоначчі дорівнюють 1. 
Кожне наступне - це є сума двох попередніх. 
Отже, початок ряду Фібоначчі виглядає таким чином:
1 1 2 3 5 8 13 21 34 55 89 144 …
Необхідно побудувати алгоритм і реалізувати його 
у вигляді програми FIB.PAS (BAS чи CPP), що 
знаходитиме найбільший спільний дільник N-го 
та M-го чисел Фібоначчі(1<=N, M<=1000).
У файлі FIB.DAT записано лише два числа N і M.
У файл FIB.SOL потрібно вивести шуканий спільний дільник.
Приклади:
FIB.DAT
12 18
7 10
20 10

FIB.SOL
8
1
55

3. Трикутники. (10 балів)
У текстовому файлі TRIANGLE.DAT через пропуск записані 
10 різних натуральних чисел (кожне з яких не перевищує 5000). 
Потрібно побудувати алгоритм і реалізувати його у вигляді 
програми TRIANGLE.PAS (BAS чи CPP), що прочитає дані з файла 
TRIANGLE.DAT, підрахує кількість різносторонніх трикутників, 
довжинами сторін яких служать дані числа та результат 
виведе у файл TRIANGLE.SOL. 
Приклад:
TRIANGLE.DAT
1 3 5 9 15 25 45 75 125 500
TRIANGLE.SOL
0

		2 лютого 2003 року
		2 тур (практичний)

1. Кодування. (15 балів)
Хакер Вася шифрує свої повідомлення друзям наступним чином. 
Для кожного байту файлу він міняє місцями біти з 
номерами 0-1, 2-3, 4-5, 6-7. Так байт, значення якого 87, 
перетвориться на байт зі значенням 171. У файлі CODE.DAT 
записано закодоване таким чином повідомлення. (Розмір файлу 
CODE.DAT не більше 1024 байт). У файл CODE.SOL необхідно 
записати розкодоване повідомлення. Ваша програма повинна 
мати назву CODE.PAS (BAS чи CPP).
Приклад:
CODE.DAT
ABCDEFGH
CODE.SOL
ВБГИКЙЛД
Примітка: CODE.SOL це файл з 8 байт, що мають значення: 
130	129	131	136	138	137	139	132

2.	Лабіринт. (50 балів)
Маленький Паскаль заблукав у магічній печері, і ніяк не 
може знайти з неї вихід. Але маючи план печери-лабіринту 
та знаючи своє місцезнаходження, він вирішив написати на 
свому кишеньковому комп'ютері програму, що визначить 
найменший час, за який він може дістатися виходу. План має 
вигляд квадрату розміром NxN (3<=N<=50), що розбитий на 
клітинки 1х1. На плані лабіринту є такі умовні позначення: 
"0" - вільна клітинка
"-1" - стіна
"-2" - клітинка де знаходиться Паскаль
"-3" - клітинка вихід
"A" - 1<=A<=10 вхід до магічного телепорту з номером A
"B" - 101<=B<=110 вихід з магічного телепорту з номером (B-100)
На кожному кроці хлопчина може переміститися на будь-яку сусідню 
по вертикалі чи горизонталі клітинку, що не є стіною. Якщо 
Паскаль потрапляє на клітинку, що містить вхід до телепорту, 
то він може (якщо захоче) переміститися до відповідного 
виходу (переміщення у телепорті відбувається миттєво, всі 
інші переміщення займають рівно одну хвилину). Для кожного 
магічного телепорту обов'язково існує вихід.
У першому рядку файлу MAZE.DAT знаходиться число N. 
У наступних N рядках - план лабіринту.
У файл MAZE.SOL необхідно записати єдине чило - час (у хвилинах), 
за який Паскаль дістанеться виходу з лабіринту. Ваша програма 
повинна мати назву MAZE.PAS (BAS чи CPP).
Приклад:
MAZE.DAT
5
0 0 0 0 0
0 7 0 -1 0
0 0 0 -1 -3
-2 0 0 -1 0
0 0 0 107 0

MAZE.SOL
6

3. Японський календар. (20 балів)
У давньояпонському календарі був прийнятий 60-літній цикл, 
що складався з 12-літніх підциклів. Підцикли позначалися 
назвами кольорів: зелений, червоний, жовтий, білий, чорний. 
Всередині кожного підциклу роки мали назви тварин: пацюка, 
корови, тигра, зайця, дракона, змії, коня, вівці, мавпи, 
курки, собаки і свині. 1984 рік - рік зеленого пацюка - був 
роком початку чергового циклу. Напишіть програму CALENDAR.PAS 
(BAS чи CPP), що забезпечить введення деякого року з файлу 
CALENDAR.DAT та виведення його назви за давньояпонським 
календарем у файл CALENDAR.SOL

CALENDAR.DAT
2003

CALENDAR.SOL
Рік чорної вівці

Примітка. При отриманні затруднень з виведенням у файл 
CALENDAR.SOL літер кирилиці допускається запис українських 
слів латинськими літерами. Наприклад, замість фрази 
"Рік зеленого пацюка" можна записати "Rik zelenogo pacyuka".

4. "Симетричні простачки". (15 балів)
 
Число називається простим, якщо воно має лише два дільники: 
1 і саме число. 
Назвемо число "симетричним", якщо його десятковий запис 
читається однаково зліва направо і cправа наліво (151, 2002, …).
У файл SYMETR.* (де * означає розширення дозволеної мови 
програмування PAS для Pascal, CPP для С++, BAS для Basic) 
запишіть програму, яка підрахує кількість простих 
"симетричних" чисел у вказаному діапазоні [n, m], 
де 10 < n < m <100 000 000.

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

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

Вхідні дані
10 100
20000 345678
10 100000000

Вихідні дані
1
67
777

Кінець умов