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

Третій тур
24.11.2008 - 05.12.2008

Тур проводять:
Стукалова Ірина Володимирівна, вчитель інформатики колегіуму м. Хмельницького
Мельник Валентин Іванович, вчитель інформатики ліцею інформаційних технологій м.Олександрія Кіровоградської області

Увага!
Під час залікових турів розв'язки дозволяється надсилати тільки один раз за вказаними адресами. 
Розв'язки надсилати одним листом за двома адресами irina78@rel.com.ua та mvi_7@rambler.ru до 24:00 05.12.2008 включно.
Копію: zoi2008@i.ua
Тема листа: ZOI_2008_3
Питання щодо умов задач t3z1 та t3z2 можна надсилати на адресу irina78@rel.com.ua до 04.12.2008 включно.
Питання щодо умов задач t3z3 та t3z4 можна надсилати на адресу mvi_7@rambler.ru до 04.12.2008 включно.
На перевірку задач буде відведено час більший за час роботи авторських розв'язків.
======================================================================================================

Задача t3z1. Знову шифровка (20 балів)
 Відомий метод шифрування квадратом: деяке повідомлення вписується у квадрат по рядках. При цьому пропуски замінюються знаком ‘*’, а якщо в останньому рядку квадрата залишилися вільні клітинки, вони заповнюються крапками (‘.’). Після цього, прочитавши вміст квадрата стовпець за стовпцем, отримують зашифрований текст.
 Ваша задача полягає у тому, щоб зашифрувати вхідне повідомлення.

Вхідні дані:
 У файлі Z1.dat міститься повідомлення, довжиною не більше 5000 символів. При зчитуванні символи переведення рядка необхідно ігнорувати.

Вихідні дані: У файл Z1.sol вивести зашифроване повідомлення.

Приклад:
Z1.dat:
Attack at dawn or we are done for

Проміжне подання у вигляді квадрата:

A t t a c k
* a t * d a
w n * o r *
w e * a r e
* d o n e *
f o r . . .

Z1.sol:
A*ww*ftanedott**ora*oan.cdrre.ka*e*.
======================================================================================================

Задача t3z2. Видалення коментарів (20 балів)
 Дано текст деякої Паскаль-програми. Ваша задача полягає у тому, щоб видалити з неї всі коментарі та порожні рядки. Як відомо, коментар у паскаль-програмі – це текст, який записаний у фігурних дужках – {},  або у круглих дужках з зірочкою – (*  *). Довжина рядка програми не може перевищувати 128 символів. Коментар може займати як частину рядка, так і декілька рядків програми. Вкладені коментарі в тексті відсутні.

Вхідні дані:
У файлі Z2.dat міститься текст програми з коментарями.

Вихідні дані:
У файл Z2.sol записати текст програми без коментарів. Порожні рядки у файл не записувати.

Приклад:
Z2.dat:
var
i:integer;{index }
a:array[1..10] of real; (*massiv*)
begin {rozvjazok
zadachi} for i:=1 to 10 do a[i]:=i;
{vyvid massiva} for i:=1 to 10 do
writeln(a[i]);
(*vse*)
end.

Z2.sol:
var
i:integer;
a:array[1..10] of real;
begin 
 for i:=1 to 10 do a[i]:=i;
 for i:=1 to 10 do
writeln(a[i]);
end.
======================================================================================================

Задача t3z3. Рядок (25 балів)

Ім’я вхідного файлу:
string.in
Ім’я вихідного файлу:
string.out
 Дано слово, Вам необхідно в ньому переставити місцями два символи, які знаходяться на різних позиціях в цьому слові, так щоб в результаті отримати слово, лексикографічно найменше з усіх можливих. 
 Формат вхідних даних: у єдиному рядку вхідного файлу записане слово, яке складається з маленьких літер латинського алфавіту. Гарантується, що його довжина не буде перевищувати 100000 і не буде меншою за 2 символи.
 Формат вихідних даних: у єдиному рядку вихідного файлу повинно знаходитись рівно два числа – позиції символів у даному слові, що треба переставити між собою. Якщо існує декілька варіантів відповіді – виведіть ту в якій менше перше число, якщо таких більше однієї, то ту в якій менше друге число.
    Приклад файлів вхідних і вихідних даних:

string.in
adbsab

string.out  
2 5
======================================================================================================

Задача t3z4. Tour De France (35 балів)
Ім’я вхідного файлу:
tour.in
Ім’я вихідного файлу:
tour.out
 На цей раз Вам доведеться допомогти організаторам всесвітньо відомих велоперегонів Tour De France виготовити трасу, по якій буде проходити змагання. Організатори перегонів надали вам карту. На ній відмічено N пунктів і M одно-направлених доріг, які з’єднують ці пункти. Слід зауважити, що транспортна система в Європі передбачає, що між будь-якою парою пунктів буде існувати як мінімум одна дорога (про її направленість не повідомляється). Траса повинна починатися з будь-якого пункту і має бути прокладена через всі N пунктів, а також має слідувати N-1 дорогами (які з’єднують відповідні N пунктів).
 Формат вхідних даних: у першому рядку вхідного файлу записано два числа N (1<=N<=100) та M (1<=M<=10000). В наступних M рядках записано по два числа ai та bi (1<=ai,bi<=N), що задають дорогу, яка виходить з пункту ai й слідує до пункту bi. Номери пунктів – натуральні числа, що не перевищують N. Причому, можуть існувати дороги, які виходять і входять в один і той самий пункт, а також два пункти, можуть бути з’єднані більше ніж однією дорогою. Однак, гарантується, що для будь-яких двох різних пунктів з номерами i та j існує дорога, яка виходить з пункту i і слідує до пункту j, або ж навпаки – виходить з пункту j та слідує до пункту i.
 Формат вихідних даних: у випадку існування такої траси у єдиному рядку вихідного файлу має бути записано N чисел – номери пунктів, по яким буде проходити траса, в порядку її слідування, відокремлених рівно одним пробілом. Якщо існує декілька варіантів прокладки траси – виведіть будь-яку. Якщо варіантів прокладання траси не існує, то в єдиному рядку вихідного файлу виведіть рядок “NO SOLUTION”, без лапок.
 Приклади вхідних та вихідних даних:
tour.in
4 6
1 2
2 3
1 4
4 3
4 2
1 3

tour.out
1 4 2 3
======================================================================================================

Приклад листа третього туру учасника з кодом 333.
Кому: irina78@rel.com.ua, mvi_7@rambler.ru
Копія: zoi2008@i.ua
Тема: ZOI_2008_3
Зміст листа: 
Прошу перевірити розв'язки задач третього туру.
Учасник з кодом 333. (Не можна підписувати листи прізвищами)
Вкладка: файли U333T3Z1.PAS, U333T3Z2.PAS, U333T3Z3.PAS, U333T3Z4.PAS