Задача Kingdom

В казковому королевстві N міст. Деякі пари міст з’єднано дорогами, причому одну і ту саму пару міст можуть з’єднувати кілька доріг. Зовні міст дороги не перетинаються. По кожній дорозі можна їхати в будь-якому напрямку. Допоможіть королю визначити, скільки ще доріг потрібно побудувати в королевстві, щоб Його Величність зміг зробити подорож по всіх дорогах, не проїжджаючи двічі по жодній з них. Звичайно (див приклад нижче), він має бажання відвідати кожне місто. Подорож короля повинна починатись і закінчуватись в одному і тому самому місті.

Технічні умови. Ви вводите з клавіатури кількість міст у королевстві N (1<=N<=100) і кількість пар міст К (1<=K<=10000). Потім в К групах по 3 числа ви вводите номери міст і кількості доріг, що їх з'єднують (всі числа не перевищують 100). Всі числа розділені пропуском. Ви виводите на екран мінімально можливу кількість доріг.

Приклад.

Введення> 7 6 1 2 1 1 3 1 4 1 3 4 2 5 3 4 3 5 6 2
Виведення> 3

Задача Road

Знайти кількість покриттів прямокутника 2*n фігурами у вигляді дощечок, кожна з яких представляє собою або квадрат зі стороною 1, або два квадрати (2*1), або “кутик” з трьох квадратів

Фігури повинні заповнювати прямокутник без проміжків.

Технічні умови. Ви вводите з клавіатури число n (1<=n<=1000). Ви виводите на екран кількість можливих покриттів.

Приклад.

Введення> 2
Виведення> 11

Задача Number

Дано натуральне число N. Знайти таке найменше натуральне К, що K! закінчується рівно на N нулів. Якщо такого К не існує, з’ясуйте, яке мінімальне натуральне число треба додати до N (або відняти від N), щоб відповідь існувала.

Технічні умови. Програма читає з клавіатури число N. Програма виводить на екран одне число – шукану величину.

Приклади.

Введення> 1
Виведення> 5

Введення> 11
Виведення> 1

Задача Tank

Танк повинен виїхати з бази, перетнути спочатку пустелю, а потім болото і прибути на пост. Перешкод на шляху немає, танк може рухатись у будь-якому напрямку. Максимальна швидкість танка по пустелі і болоту різна. Відомо, що пряма, яка з’єднує базу і пост, проходить через обидві території. Визначіть шлях, по якому танк якнайшвидше прибуде на пост.

Технічні умови. Програма зчитує з клавіатури 6 чисел через пропуск – максимальну скорость танка в пустелі V1(м/с), максимальну швидкість танка по болоту V2 (м/с), координати Х1 і Y1 бази, X2 и Y2 поста. Відомо, что вісь Ox розділяє пустелю і болото (пустеля – вгорі), Y1>0 , Y2<0. Всі числа дійсні. Ви виводите на екран два дійних числа - абсцису точки перетину межі територій і час (с), який витратив танк на перехід від бази до посту. Обидва числа виводити з точністю не менше 5 знаків після коми.

Приклади.

Введення>  1 1 5 3 5 –2
Виведення> 5.00000 5.00000

Введення> 3 5 20 10 8 –9
Виведення> 15.74651 5.99728

Задача NastySum

Одного разу розумний Мишко, герой дитячих казок, гуляючи лісом, з необережності потрапив у пастку браконьєрів. Злі браконьєри посадили Мишка у велику та міцну клітку з вельми захищеним кодовим замком. Залишивши його в лісі, браконьєри поїхали в місто за вантажівкою, щоб вивезти клітку з нашим героєм. Поки браконьєри відсутні, Мишко намагається розгадати код на замку. Він побудував строгу математичну теорію, з якої слідує, що для того, щоб відкрити замок, йому треба обов’язково обчислити P-ю цифру десяткового розкладу дробної частини суми S_N ,

Наприклад, якщо N = 2 и Р = 3, то

відповідно шукана цифра 8

Технічні умови. Ви вводите з клавіатури число 1<=Z<=10 (1<=N_i<=10⁸ , 1<=P_i<=10⁴), далі йдуть Z пар чисел (N_i, P_i) через пропуск. Ви виводите на екран Z чисел через пропуск, кожне з яких буде відповіддю для відповідної пари (N_i, P_i), тобто P_i-а цифра десяткового розкладу дробової частини суми S_Ni

Приклади.

Введення> 1 2 3
Виведення> 8

Введення>  3  2  1  2  2  2  3
Виведення> 2 0 8