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

Перший тур
27.10.2008 - 07.11.2008

Тур проводять:
Сіренький Ігор Олексійович, вчитель Полонської гімназії
Печений Олександр Михайлович, студент 5 курсу факультету кібернетики Київського Національного Університету ім.Т.Г.Шевченка
Увага!
Під час залікових турів розв'язки дозволяється надсилати тільки один раз за вказаними адресами. 
Розв'язки надсилати одним листом за двома адресами pechenyi@mail.ru та sirenky@pl.km.ua до 24:00 07.11.2008 включно.
Копію: zoi2008@i.ua
Тема листа: ZOI_2008_1
Питання щодо умов задач t1z1 та t1z2 можна надсилати на адресу sirenky@pl.km.ua до 06.11.2008 включно.
Питання щодо умов задач t1z3 та t1z4 можна надсилати на адресу pechenyi@mail.ru до 06.11.2008 включно.
На перевірку задач буде відведено час більший за час роботи авторських розв'язків.
======================================================================================================
Школяр Вася Пупкін довгий час вивчав паліндроми – рядки, які з обох кінців читаються однаково. На контрольній викладач дав йому чотири задачі

Задача t1z1. "Числа-паліндроми" (15 балів)
Назвемо число паліндромом, якщо його десятковий запис читається однаково зліва-направо і справа-наліво. Скільки з введених чисел є паліндромами?
Вхідні дані: в стандартному вхідному потоці записані числа в десятковій системі числення, кожне в новому рядку. Всі числа додатні і не перевищують 2 000 000 000.
Вихідні дані: в перший рядок стандартного вихідного потоку вивести шукану кількість чисел-паліндромів.
Приклад вхідних і вихідних даних:
Стандартний вхідний потік:
12
321
1
212
222
213
Стандартний вихідний потік:
3

Задача t1z2. "Двійкові паліндроми" (25 балів)
З клавіатури вводиться число n (в десятковій системі числення). Вивести з інтервалу [n, 2*n] всі числа (в двійковій системі числення), двійковий запис яких являється паліндромом. 
Вхідні дані: з клавіатури вводиться єдине число n (0<n<50000).
Вихідні дані: вивести на екран двійкові записи чисел-паліндромів із заданого інтервалу, кожне число в новому рядку.
Приклад вхідних і вихідних даних:
Стандартний вхідний потік:
3
Стандартний вихідний потік:
11
101
Пояснення: при n=3 інтервал [3; 6] містить 4 числа (3; 4; 5; 6), двійкові записи яких відповідно (11; 100; 101; 110).

Задача t1z3. "Паліндроми - I" (30 балів)
Задано рядок, який складається з малих латинських літер. Дозволяється видаляти з рядка певні літери. Скількома різними способами можна при цьому отримати паліндром?
Вхідні дані: заданий рядок знаходиться в файлі palindrome1.dat, довжина його не перевищує 30 символів
Вихідні дані: в перший рядок файлу palindrome1.sol треба вивести шукану кількість способів отримання паліндрому
Приклад вхідних і вихідних даних:
palindrome1.dat
aab
palindrome1.sol 
4
Пояснення: паліндром можна отримати, видаливши символи: 1) 1 і 2; 2) 1 і 3; 3) 2 і 3; 4) 3

Задача t1z4. "Паліндроми - IІ" (30 балів)
Задано рядок, який складається з малих латинських літер. Потрібно розбити його на мінімальну можливу кількість паліндромів.
Вхідні дані: заданий рядок знаходиться в файлі palindrome2.dat, довжина не перевищує 2000 символів
Вихідні дані: в перший рядок файлу palindrome2.sol треба вивести мінімальну кількість паліндромів, на які можна розбити рядок
Приклад вхідних і вихідних даних:
palindrome2.dat
abbacbb
palindrome2.sol 
3
Пояснення: abbacbb=abba+c+bb
=======================================================================================================
Приклад листа першого туру учасника з кодом 005.
Кому: pechenyi@mail.ru, sirenky@pl.km.ua 
Копія: zoi2008@i.ua
Тема: ZOI_2008_1
Зміст листа: 
Прошу перевірити розв'язки задач першого туру.
Учасник вищої ліги з кодом 005. (Не можна підписувати листи прізвищами)
Вкладка: файли U005T1Z1.PAS, U005T1Z2.PAS, U005T1Z3.PAS, U005T1Z4.PAS