Увага!
Під час залікових турів розв'язки дозволяється надсилати тільки один раз за вказаними адресами.

Вища ліга

Розв'язки надсилати за адресою pechenyi@mail.ru до 09.11.2006 включно.
Копію: tur1@oiuv.infocom.khmelnitskiy.ua
Тема листа: ZOI_2006

Питання щодо умов задач можна надсилати на адресу pechenyi@mail.ru до 09.11.2006 включно.
На перевірку задач буде відведено час більший за час роботи авторських розв'язків.

Задача 1. "Поліндроми" (25 балів)

   Для економії пам'яті в новому комп'ютері числа замінюються на близькі за значенням числа-поліндроми, і як результат запам'ятовується лише перша половина отриманого поліндрома. Вам потрібно написати програму для описаного комп'ютера, яка швидко по заданому числу знаходить найменший поліндром, який більший або рівний цьому числу.

Вхідні дані. в першому рядку файлу number.dat записане єдине натуральне число, кількість цифр якого не перевищує 1000.

Вихідні дані. в перший рядок файлу number.sol виведіть шуканий поліндром.

Приклад вхідних і вихідних даних:
number.dat
1711
number.sol
1771

Задача 2. "Інверсія" (35 балів)

    Школяр Вася Пупкін виписав на аркуші паперу всі перестановки перших N натуральних чисел і вирішив підрахувати, в скількох виписаних перестановках число інверсій дорівнює K. Напишіть програму, яка допоможе йому це зробити.
    Примітка. В перестановці a[1], a[2], ..., a[n] перших n натуральних чисел a[k] і a[m] утворюють інверсію, якщо a[k]>a[m] і k<m.

Вхідні дані. в єдиному рядку файлу inverse.dat знаходяться числа N, K (1<=N<=18, 0<=K<=1000).

Вихідні дані. в файл inverse.sol потрібно вивести кількість перестановок, в яких рівно K інверсій.

Приклад вхідних і вихідних даних:
inverse.dat
4 2
inverse.sol
5

Задача 3. "Переслідування злочинця" (40 балів)

    В країні Програмія є N міст. Деякі пари міст з'єднані двосторонньою дорогою. За даними поліції з міста з номером A у місто з номером B вирушив небезпечний злочинець. Для затримання цього злочинця поліція вирішила перекрити шляхи до міста B. Але через обмежений бюджет і значні витрати на перекриття дороги вони намагаються, щоб кількість перекритих доріг була мінімальною і при цьому з міста A до міста B було неможливо добратись.

Вхідні дані: в першому рядку файлу chase.dat записані через пробіл числа N, K, A, B (2<=N<=50, 1<=A, B<=N). В наступних K рядках знаходяться по два числа - пари міст, між якими існує дорога.
Вихідні дані: в файл chase.sol потрібно вивести одне число - мінімальну кількість доріг, які потрібно перекрити, щоб в результаті не було вільного шляху від A до В.

Приклад вхідних і вихідних даних:
chase.dat
5 6 2 5
1 2
1 5
2 3
2 4
3 4
4 5
chase.sol
2

Примітка.
Приклад листа першого туру учасника вищої ліги з кодом 005.

Кому: pechenyi@mail.ru
Копія: tur1@oiuv.infocom.khmelnitskiy.ua
Тема: ZOI_2006
Зміст листа:
Прошу перевірити розв'язки задач першого туру.
Учасник вищої ліги з кодом 005. (Не можна підписувати листи прізвищами)
Вкладка: файли U005T1Z1.PAS, U005T1Z2.PAS, U005T1Z3.PAS                                 на початок

=================================================================================

Перша ліга

Розв'язки надсилати за адресою irina78@rel.com.ua до 09.11.2006 включно.
Копію: tur1@oiuv.infocom.khmelnitskiy.ua
Тема листа: ZOI_2006

Питання щодо умов задач можна надсилати на адресу irina78@rel.com.ua до 09.11.2006 включно.

Задача 1. "Анаграми"

   У вхідному файлі Z1.dat міститься рядок довжиною не більше 255 символів, у якому через один або декілька пропусків слідують слова. Знайти всі групи анаграм (Анаграма - це слово, яке утворюється з іншого слова перестановкою його букв) у цьому рядку та вивести у файл Z1.sol кожну групу з нового рядка. Всі слова повинні йти через пропуск у порядку, у якому вони зустрічаються в рядку.
   Однакові слова виводити не можна.

Приклад вхідних і вихідних даних:
Z1.dat
123 321 1234 12345 123456 231 132 3241 123457 123
Z1.sol
123 321 231 132
1234 3241

Задача 2. "Грядки"

   Садова ділянка, що має прямокутну форму та розділена на квадратні клітинки зі стороною 1 метр, має ширину n і довжину m метрів. На цій ділянці скопані грядки прямокутної форми. Ніякі дві грядки не перетинаються й не торкаються одна одної ні вертикальною, ні горизонтальною сторонами клітинок (торкання грядок кутами клітинок допускається).
   Підрахуйте кількість грядок на садовій ділянці.
   Задані обмеження:
   Розміри ділянки задовольняють умовам: 1<=n, m<=100.

Вхідні й вихідні дані:
   У першому рядку вихідного файлу Z2.dat задані два числа: n та m, розділені одним або декількома пропусками.
   Далі слідують n рядків по m символів. Символ «1» позначає територію грядки. Символ «0» відповідає нескопаній території. Інших значень у вхідному файлі немає.
   Вивести у вихідний файл Z2.sol кількість грядок на садовій ділянці.

Приклад вхідних і вихідних даних:
Z2.dat
5 6
010000
001110
001110
000000
111100
Z2.sol
3

Задача 3. "Автоморфні числа"

   Складіть програму знаходження всіх автоморфних чисел на відрізку [m, n]. Автоморфним називається число, що дорівнює останнім цифрам свого квадрату. Наприклад: 5*5=25, 6*6=36, 25*25=625.
   У файлі Z3.dat містяться числа m і n (1<=m, n<=40000), розділені одним або декількома пропусками.
   У файл Z3.sol запишіть через пропуск всі автоморфні числа, що належать вказаному відрізку.

Приклад вхідних і вихідних даних:
Z3.dat
3 50
Z3.sol
5 6 25

Примітка.

Кому: irina78@rel.com.ua
Копія: tur1@oiuv.infocom.khmelnitskiy.ua
Тема: ZOI_2006
Зміст листа:
Прошу перевірити розв'язки задач першого туру.
Учасник першої ліги з кодом 505. (Не можна підписувати листи прізвищами)
Вкладка: файли U505T1Z1.PAS, U505T1Z2.PAS, U505T1Z3.PAS                                 на початок