Заочна олімпіада з інформатики Хмельницька область 2008 - 2009 Третій тур 08.12.2008 - 19.12.2008 Тур проводять: Зубик Віталій Віталійович, вчитель інформатики Летавського НВК Чемеровецького району Кухар Андрій Володимирович, викладач Хмельницького національного університету Увага! Під час залікових турів розв'язки дозволяється надсилати тільки один раз за вказаними адресами.  Розв'язки надсилати одним листом за двома адресами school.sbs@gmail.com та kobold@binet.com.ua до 24:00 19.12.2008 включно. Копію: zoi2008@i.ua Тема листа: ZOI_2008_4 Питання щодо умов задач t4z1 та t4z2 можна надсилати на адресу school.sbs@gmail.com до 18.12.2008 включно. Питання щодо умов задач t4z3 та t4z4 можна надсилати на адресу kobold@binet.com.ua до 18.12.2008 включно. На перевірку задач буде відведено час більший за час роботи авторських розв'язків. ====================================================================================================== Задача t4z1 (20 балів) Відомо, що число Сміта – це таке складене число, сума цифр якого дорівнює сумі цифр усіх його простих співмножників. Так, прикладом числа Сміта може служити 202, оскільки 2+0+2=4, і 2+1+0+1=4 (202=2*101). Знайдіть кількість чисел Сміта на проміжку [N,M], де 0 14 -> 17 -> 50 ====================================================================================================== Задача t4z3. Запросто (20 балів) Дано n чисел, 3<=n<=1000, -1000<=xi<=10000. Знайти серед них два таких числа xa та xb, що їх сума дорівнює сумі всіх інших чисел, що залишилися. Вхідні дані: В першому рядку вхідного потоку міститься одне число n. В другому рядку вхідного потоку міститься n чисел xi, розділених пропуском. Вихідні дані: В перший рядок вихідного потоку вивести два числа xa та xb розділених одним або більше пропусками. Якщо неможливо знайти таких два числа — вивести числа 0 та 0. Приклад вхідних даних 1: 5 -5 2 5 3 5 Приклад вихідних даних 1: 2 3 Приклад вхідних даних 2: 4 2 6 -4 1 Приклад вихідних даних 2: 0 0 Час роботи програми не повинен перевищувати 5 сек на Intel Core 2 Duo E2180. ====================================================================================================== Задача t4z4. Стек-анаграма (40 балів) Уявімо собі автомат для перетворення слів. На вхід автомата надходить слово. Автомат керується за допомогою двох команд: Push та Pop. Команда Push бере наступну літеру вхідного слова і розміщує її в стеку. Команда Pop бере літеру з вершини стека і дописує її до результату. В результаті на виході автомата утворюється нове слово, яке можливо відрізняється від вхідного порядком літер, в залежності від застосованої послідовності команд Push та Pop. Наприклад: Вхідне слово: eric. Позначимо команду Push літерою i, а команду Pop літерою o. В результаті виконання послідовності команд i i o i o i o o на виході утвориться слово rice. Очевидно для того, щоб обробити слово з n літер необхідно виконати n команд Push та n команд Pop. В результаті на виході утвориться нове слово з n літер. Назвемо пару слів стек-анаграмою, якщо друге слово можна отримати шляхом перетворення першого на вищеописаному автоматі. Завдання: написати програму, що визначає, чи є задана пара слів стек-анаграмою. Якщо є, програма повинна знайти будь-яку послідовність команд, що перетворюють перше слово на друге. Вхідні дані: В першому рядку вхідного потоку міститься перше слово. Слово складається лише з маленьких латинських літер. Довжина слова не перевищує 10 літер (та не менше однієї літери). В другому рядку вхідного потоку міститься друге слово. Друге слово теж складається лише з маленьких латинських літер. Довжина другого слова дорівнює довжині першого. Вихідні дані: Якщо дані слова є стек-анаграмою, в перший рядок вихідного потоку вивести послідовність команд, що перетворюють перше слово на друге. Команду Push позначити латинською літерою i, команду Pop позначити латинською літерою o. Команди розділити одним або більше пропусками. Якщо дані слова не є стек-анаграмою, в перший рядок вихідного потоку вивести одну латинську літеру x. Приклад вхідних даних 1: mada adam Приклад вихідних даних 1: i i i i o o o o Приклад вхідних даних 2: long nice Приклад вихідних даних 2: x Час роботи програми не повинен перевищувати 5 сек на Intel Core 2 Duo E2180. ====================================================================================================== Приклад листа четвертого туру учасника з кодом 999 Кому: school.sbs@gmail.com, kobold@binet.com.ua Копія: zoi2008@i.ua Тема: ZOI_2008_4 Зміст листа:  Прошу перевірити розв'язки задач четвертого туру. Учасник з кодом 999. (Не можна підписувати листи прізвищами) Вкладка: файли U999T4Z1.PAS, U999T4Z2.PAS, U999T4Z3.PAS, U999T4Z4.PAS