Заочна олімпіада з інформатики.
	   Хмельницька область 
	     2002-2003 н.р.

                 Тур 2

         2.12.2002 - 12.12.2002

Розв'язки приймаються за адресою letava@cm.km.ua до 24.00 12.12.2002.
Копія листа направляється на адресу  tur2@oiuv.infocom.khmelnitskiy.ua

Тема листа: TUR2 

На перевірку задач буде відведено час в 2 рази більший за час роботи
авторських розв'язків.


T2Z1 (25 балів)

Задача 1. "Подорож" м'ячика по сходинках.

На вершині драбинки, що складається з N сходинок, знаходиться м'ячик, 
який починає котитися, підскакуючи, донизу. М'ячик під час своєї
 "подорожі" може скочити на наступну сходинку,  через одну або 
через дві сходинки. (Тобто, якщо м'ячик знаходиться на 10 сходинці, 
то він може переміститися на 9-у, 8-у і 7-у сходинки).
Визначити число всіх можливих маршрутів "подорожі" м'ячика на землю.

Технічні умови.
У файлі BALL.DAT міститься єдине число  0<N<31.
У вихідному файлі BALL.SOL міститься одне число - кількість маршрутів.


T2Z2 (35 балів)

Задача 2. Майданчик під стадіон.

Жителі невеликого провінційного містечка Healthcity, що розміщено
не вельми далеко від кінця світу любили дві речі: спорт і природу.
Вирішивши одного разу побудувати стадіон вони були шоковані - навколо 
містечка знаходилося безліч дерев, які вони, по зрозумілих причинах, 
не могли нищити. Пошук придатного для будівництва майданчика 
затягнувся і мер звернувся до аерокосмічного агентсва за планом 
місцевості з відмітками місць, де ростуть дерева. План було отримано. 
Він був розбитий на квадрати розмірності N, які могли мати такий 
вигляд:

 0  0 -1 -1  0 -1 
 0 -1 -1 -1  1  2
-1 -1  0 -1  3  4
-1  0  4  4 -1 -1
-1 -1  6  4 -1 -1
 0  0 -1  0  0 -1

Від'ємними одиничками позначені місця знаходження дерев, а додатні 
числа вказують вказують на вільні від дерев місця та середню висоту 
ділянки відносно найнижчої точки на  карті. Ваша задача: допомогти
жителям міста  Healthcity поліпшити здоров'я і зберегти природу, 
тобто скласти програму вибору найбільшого майданчика для майбутнього 
стадіону. Ділянка повинна мати прямокутну форму (квадрат є частковим 
випадком прямокутника). З двох рівних по площі ділянок слід вибрату 
ту, затрати праці по підготовці якої будать мінімальними.

Наприклад, для нашого плану рівні площі мають дві ділянки: 
(2,5) і (4,3). Координати задають верхні ліві кути. Площі однакові 
(4 од), але другий варіант кращий, оскільки зайві тільки 2 одиниці 
грунту (координата 5,3), а в першому випадку для виходу на цей 
рівень ми повинні перемістити 1 од. з (3,5) в (2,5). 
І хоча тепер перша рівнина (2,2,2,4) дорівнює по об'єму 
робіт другій (4,4,6,4) - друга більш економічно вигідна тому, 
що тут не здійснювалися попередні переміщення.

Приклади порівняння рівнин:
(2,2,2,3) краще, ніж (2,2,2,1) - одиницю грунту краще вивести як 
завезти;
(1,2,3,4) дорівнює (5,6,7,8) - в такому випадку виводити першу 
знайдену при обході з верхнього лівого кута карти.

Технічні умови:
Вхідний текстовий файл STADION.DAT у першому рядку містить число 
0<N<101.
У наступних N рядках міститься по N цілих чисел через пропуск.
Вихідний файл STADION.SOL у першому рядку містить два цілих числа 
розділених пропуском - координати лівого верхнього кута прямокутньої 
ділянки; 
другий рядок містить одне ціле число - площу ділянки; третій одне 
ціле число - кількість одиниць грунту для переміщення.
Для нашого прикладу вихідний файл повинен містити:
4 3
4
2


T2Z3 (40 балів)

Задача 3. НЕП

У деякій фірмі, не обтяженій засобами виробництва, для випуску 
N видів готової продукції  працює дві бригади. Для j-го виробу 
першій бригаді необхідний час а[j], потім час b[j] потрібен 2-й 
бригаді для упаковки виробу. 
В якій послідовності необхідно виготовляти вироби, щоб загальний 
час для виготовлення і упаковки всієї продукції був мінімальним. 
Всі види продукції обробляються бригадами в одній послідовності.

Технічні умови:
Вхідний файл NEP.DAT у першому рядку містить одне число  
0<N<31 - кількість видів продукції. Другий - N цілих чисел - 
часові затрати першої бригади для випуску кожного виду продукції. 
Третій рядок - N цілих чисел - часові затрати 
другої бригади для упаковки кожного виду продукції.
Наприклад:
5
4 4 30 6 2
5 1 4 30 3

Вихідний файл NEP.SOL у пешому рядку містить N цілих чисел - 
оптимальний порядок випуску видів продукції,
другий - одне ціле число - загальний час виготовлення всіх видів 
продукції.
Наприклад:
5 1 4 3 2
47
 
Увага! Правильно оформляйте розв'язки.

Файли з розв’язками повинні мати назви у відповідності 
до маски: 
UNNNTXZY.RRR,  де 
NNN - реєстраційний номер учасника, 
X - номер туру, 
Y - номер задачі в турі, 
RRR - розширення дозволеної мови програмування. 
Наприклад, U005T0Z2.PAS - розуміється, як розв'язок 
учасника номер 005 задачі № 2  нульового (тренувального) 
туру на мові PASCAL.