Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Завдання 2 туру
Розв'язки слід подати на перевірку до 0 годин 29 серпня 2009 р.

Задача CORSIAR

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

        Введення-виведення

        Спочатку ви вводите з клавіатури одне число - кількість контрольних прикладів К (1<=K<=100), а тоді К разів читаєте з клавіатури кількість скарбів N(3<=N<=20) та N пар дійсних чисел - координати чергового скарбу (перше число - абсциса, друге - ордината).
        Ви виводите на екран послідовність з K символів 0 чи 1. Якщо обхід був за годинниковою стрілкою-йому відповідає 1, якщо проти - 0.

Приклад
Введення> 3
Введення> 3 0 0.2 1.2 1.2 2.7 0.8
Введення> 4 4 4 8 4 8 8 4 8
Введення> 3 10 10 10.6 15 5 15
Виведення< 100

Задача PAVEMENT

        У дорожних майстрів є плитки 1х1 та 1х2. Скількома способами можна покрити такими плитками стежку 2хN ? Плитки 1х2 на заводі зробили так, що їх можливо класти лише широкою стороною вздовж стежки.

                        
                        

    

         

        Введення-виведення
        Ви вводите з клавіатури одне число N(1<=N<=1000).
        Ви виводите на екран шукану кількість покриттів.

Приклад
Введення> 5
Виведення< 64

Задача TABLE

        Нехай N - деяке натуральне число. Розглянемо таблицю А[1:N], яка містить цілі числа з діапазону [-32768..32767], серед яких немає двох однакових. Знайти місце в таблиці, де знаходиться K-е число за спаданням (тобто таке, що рівно К-1 чисел у таблиці більші за нього).

        Введення-виведення
        Ви вводите з клавіатури число N(1<=N<=20000), далі - N елементів таблиці, через пропуск, а тоді - число К(1<=K<=N).
        Ви виводите на екран одне число - місце знаходження К-го за спаданням елемента таблиці.

Приклад
Введення> 7
Введення> 9 5 1 2 8 6 3
Введення> 2
Виведення< 5

Задача FLIGHT

        Акробат стрибає на батуті, весь час піднімаючись на одну й ту ж висоту Н метрів. Тренер ввімкнув секундомір в момент початку чергового підйому. Допоможіть тренеру розрахувати, на якій висоті буде акробат в момент, коли секундомір покаже T секунд та куди (вгору чи вниз) акробат буде рухатись в цей момент. Необхідно врахувати, що час його знаходження на батуті Т1 секунд, а час "зависання" в верхній точці (вправні акробати вміють це робити) T2 секунд. Прогинанням батута та опором повітря знехтувати. Прискорення вільного падіння 10 м/с2.

        Введення-виведення

        Ви вводите з клавіатури 4 дійсних числа H(0<=H<=2000), T(1<=T<=1000), T1(0<=T1<=5), T2(0<=T2<=5)
Ви виводите на екран висоту , на якій знаходиться акробат, 1, якщо він при цьому рухається вгору, 2 - якщо вниз та 0, якщо в цей час акробат нерухомий.

Приклад
Введення> 700.0 30 2 1
Виведення< 339.0492 1

Задача VIRUS

        В комп'ютері фірми Megasoft завівся страшенний вірус. Головний програміст фірми Гілл Бейтс запідозрив, що цей вірус переставляє якимось чином слова в тексті. Щоб написати антивірус, він надрукував вхідний текст повідомлення, а потім заражений. Обидва тексти вмістились кожен в одному рядку, містять тільки англійські літери та пропуски. Допоможіть визначити, як потрібно переставити слова в тексті, щоб його вилікувати.

        Введення-виведення
        Ви вводите з клавіатури два рядки - вхідний і заражений(довжина кожного рядка не перевищуе 255 символів).
        Ви виводите на екран порядок, в якому треба переставити слова. Якщо це неможливо, надрукувати 0.

Приклади

Введення> megasoft is a best corporation
Введення> is corporation best megasoft a
Виведення< 2 5 4 1 3


Введення> megasoft is a best corporation
Введення> is corporation megasoft a good
Виведення< 0


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"