XIX обласна олімпіада з інформатики. (Хмельницька область).
І тур. 4 січня 2005 року.


Задача 1. “Про мікроби”.

Відомо, що в одному кубічному метрі повітря приміщення класу до початку занять міститься 2600 мікробів. З одного мікроба через кожні 30 хвилин при t = +30˚C утворюється два. При t = +20˚C розподіл мікробів сповільнюється у 2 рази, а при t = +10˚C – у 20 разів. Об’єм класу S м3, у класі перебувають m учнів. Потрібно обчислити кількість мікробів, що припадають на одного учня через k годин після початку занять (1≤ k≤ 7) при температурі t (t може мати значення 10, 20, 30).

Технічні вимоги: Із клавіатури вводяться (стандартний вхідний потік) S, m, k, t як чотири числа, що розділені пропуском. На екран виводиться (стандартний вихідний потік) єдине число – кількість бактерій, що припадають на одного учня.

Приклади вхідних та вихідних даних:
Вхідні дані:
120 10 4 30
120 15 2 20
100 20 5 10
Вихідні дані:
7987200
105300
21930


Задача 2. “Найменше число”

Записати найменше число, сума цифр якого дорівнює заданому числу N (0 Вхідні дані: з стандартного вхідного потоку вводиться єдине число N.
Вихідні дані: вивести у стандартний вихідний потік найменше число,
сума цифр якого дорівнює N.

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

Приклад 2:
Вхідний потік
10
Вихідний потік
19


Задача 3. “Дід Мороз у замку”

Стародавній замок має форму квадрата і містить NxN кімнат. У кожній кімнаті розставлені скриньки з золотими монетами. Дід Мороз знаходиться у верхній лівій кімнаті і мріє, зібравши якомога більше монет, добратися до правої нижньої кімнати, де його чекає чарівна Снігурочка. З кожної кімнати він може перейти до сусідньої внизу або сусідньої праворуч. Дід Мороз також хоче запам’ятати маршрут, який він пройде. Допоможіть Діду Морозу.

Формат вхідних даних: В першому рядку файла SANTA.CLS знаходиться одне число N (1<=N<=30). В кожному i-му з наступних N рядків знаходиться N чисел, що визначають кількість монет у кімнаті (i,j).

Приклад введення:
5
7 1 4 9 3
3 8 4 2 1
8 1 6 7 7
2 7 4 4 5
4 5 2 6 5

Формат вихідних даних: Ваша програма повинна виводити у перший рядок файла SNOW.MDN одне ціле число – кількість монет, яку вдалося зібрати Діду Морозу. У другому рядку – маршрут – номери кімнат, у яких побував Дід Мороз, починаючи з кімнати (1,1), і закінчуючи (N,N).

Приклад виведення:
52
(1,1) (2,1) (2,2) (2,3) (3,3) (3,4) (3,5) (4,5) (5,5)


XIX обласна олімпіада з інформатики. (Хмельницька область).
ІІ тур. 5 січня 2005 року.


Задача 4. "Дід Мороз і комп'ютерні хулігани"

На поштову скриньку Діда Мороза надходять замовлення на подарунки у вигляді текстового файлу. Поштова програма працює так, що вихідний текст спочатку кодується, а потім пересилається паралельно з оригіналом. На комп'ютері Діда Мороза програма розкодовує файл та порівнює з оригіналом. Як завжди, комп'ютерні хулігани, перед Новим роком хочуть заявити про себе, "запустивши" в мережу новий комп'ютерний вірус. З усієї кількості надісланих листів непошкодженими дійшли лише два листи-оригінали та закодовані листи з замовленнями.
Допоможіть Діду Морозу розкодувати та прочитати решту листів.

Технічні умови:
У файлі SURPRISE.ORI знаходиться оригінал листа, у файлі SURPRISE.KOD закодований текст.
Ваша програма повинна прочитати дані з файлу SURPRISE.KOD і вивести оригінал листа у файл SURPRISE.ORI


Задача 5. “Вивернута пам’ять”

Після аварії в гіперпросторовому стрибку зореліт "ФАЭТОН" став дзеркально відбитим – ліве помінялося з правим. Серце у всіх астронавтів стало праворуч, а назва корабля перетворилась в "НОТЄАФ". Також «вивернутою» виявилась і пам’ять комп’ютера, що керує рухом корабля. Для виконання наступного гіперпросторового стрибка потрібно виправити двійкове представлення програми в пам’яті комп’ютера. Для цього необхідно поміняти місцями біти в 16-бітних словах (виконати дзеркальне відображення): 0-й біт повинен стати 15-м, 1 – 14, 2 – 13 і т.д.

Приклад відображення: 0110001011101101 ® 1011011101000110

Формат вхідних даних: У першому рядку файла FAETON.DAT записане одне ціле число N (0
Формат вихідних даних: У вихідний файл NOTEAF.REZ записати N рядків, по одному числу в рядку – десяткове представлення слів програми після дзеркального відображення.

Приклад файла FAETON.DAT:
3
1
0
32767

Приклад файла NOTEAF.REZ:
32768
0
65534


Задача 6.“Найвіддаленіші міста”

В країні Олімпії є N міст. Деякі міста з’єднані дорогами, які мають певну довжину і по яких можна рухатись в обидва боки. Особливість країни полягає у тому, що з довільного міста можна проїхати у будь-яке інше. Крім того між будь-якими двома містами існує єдиний шлях, який не проходить двічі через одне місто. Мандрівники здавна хотіли взнати, між якими двома містами Олімпії найбільша відстань.

Формат вхідних даних: В першому рядку файлу cities.dat знаходиться число N (2<=N<=1000). В наступних рядках по три числа - i, j, s. 1<=i<=n, 1<=j<=n, 1<=s<=1000. (Довжина прямої дороги між містами i та j дорівнює s).

Формат вихідних даних: В файл cities.sol потрібно вивести відстань між двома найвіддаленішими одне від одного містами.

Приклад вхідних і вихідних даних.
cities.dat
5
1 2 10
3 2 2
2 4 5
3 5 2

cities.sol
15