Задача Street

У місті Нью-Петрики побудували нову вулицю. Будинки поставили в одну лінію, а не в дві – не змогли дійти згоди про ширину проїжджої частини… Перший будинок мав 1 поверх, другий – 2 і т.д., тобто в кожному наступному будинку поверхів на один більше, ніж в попередньому. Для покращення зовнішнього вигляду фасади будинків  вирішили пофарбувати – кожен поверх в свій колір. Але, як водиться, фарбу купили лише 2-х кольорів – білу і червону. Мер вирішив, що 2 білі поверхи в одному будинку може бути підряд,  а ось 2 червоні – ні. Зрозуміло, що будь який будинок можна розфарбувати (кожен поверх в свій колір) не одним способом. Програмісту Хакерову доручили порахувати кількість способів фарбування для кожного з достатньо великої кількості будинків вулиці. Його програма вивела на принтер послідовно кількість способів для кожного будинку від першого до останнього без пропусків (помилився з форматом Виведення, таке в нього вже було на першому турі  NetOI). Вийшов чималий рядок цифр. Допоможіть Хакерову знайти N-ту цифру в цьому рядку (зрозуміло, що цифра з номером N є в роздруківці).
Технічні умови.  Програма  Street читає з клавіатури єдине число N (1 ≤ N ≤ 10000000) – номер цифри в послідовності і виводить на екран єдине число – шукану величину.
Приклади

Задача MiniLine

 Будинок  нової вулиці в місті Нью-Петрики  мав вигляд паралелепіпеда, одна з вершин якого співпадає з початком декартової системи координат і ребра якого паралельні осям координат. Мер міста  (як зрозуміло з попередньої задачі – естет), вирішив прикрасити вже розфарбований червоно-білий будинок  синьою  лінією, яку наказав провести по ребрах будинку між двома заданими ним точками. Лінію між  точками на ребрах будинку будівельники з метою економії бюджетних коштів на фарбу провели мінімально можливої довжини. Знайдіть довжину цієї лінії.

Технічні умови. Програма MiniLine читає з клавіатури 9 цілих чисел, розділених пропусками. Перші три числа – координати  вершини паралелепіпеда, протилежної до початку координат, далі – координати початку і кінця лінії. Всі числа не більші 10000. Програма виводить на екран єдине число – шукану величину.
Приклад
Введення  5 6 7 5 2 0 0 0 4
Виведення 11

Задача  CrossGroup 

У програму Олімпійських ігор 2020 року планується включити новий вид спорту «кросгроуп». Команда складається з N спортсменів  і капітана, в їх розпорядженні є екіпаж спеціальної конструкції, в який може сісти капітан і не більше 4 спортсменів. Команди стартують одночасно. Перемагає та, яка найшвидше в повному складі добереться до фінішу. 

Який найменший час може показати команда, що бере участь у змаганнях, якщо кількість членів команди N (не включаючи водія-капітана),  (1 £ N £ 30), швидкість екіпажу стала і дорівнює V км/год, кожен член команди може як завгодно довго бігти з фіксованою швидкістю U км/год, а довжина дистанції Z км. Зрозуміло, що треновані спортсмени час на посадку/висадку з екіпажу та його розворот для руху в протилежному напрямку не втрачають.

Технічні умови.  Програма  CrossGroup читає з клавіатури  цілі числа N, V, U і Z, розділені пропусками (всі, крім N,  додатні, не більші 100). Програма виводить  єдине число – шукану величину  з точністю до 0,001.
Введення
8 30 5 15
Виведення
1.056

Задача Liquidation

Місто Аседо має форму прямокутника 20*20 точок. Усі будинки міста є одиничним квадратами. Координати кутів будинків – цілі числа. Місто захопила банда  агресивних  терористів,  кожного з яких ВЕЛИКА РАДА СПРАВЕДЛИВОСТІ  (ВРС) давно засудила до смертної кари (не гуманно, але…). Терористи розсіялися по одному і зайняли точки з цілими координатами, а  в одній з таких точок  начальник відділу боротьби з тероризмом підполковник Намцог  затаївся в засідці. Героїчний детектив почав стрільбу по бандитах, та ще й таку, що вони й зрушити з місця не могли з переляку. Табельний пістолет Намцога може стріляти лише по прямій, але куля, на жаль, не летить далі, якщо влучає в стіну чи кут будинку. Якщо  куля влучає в терориста, той, звичайно, гине, а куля продовжує свій смертоносний політ…Коли наш доблесний підполковник розстріляв всіх можливих терористів, він по мобільному телефону доповів Маршалу ВРС, що операцію завершено. Маршал незадоволено запитав: «А скільки терористів вижило?» Допоможіть Намцогу чесно відповісти Маршалу ВРС.
Технічні умови. Програма  Liquidation читає з клавіатури координати Намцога, кількість терористів, їх координати, кількість будинків, координати лівих нижніх кутів кожного будинку. Всі числа розділено пропусками. Програма виводить на екран єдине число, яке підполковник мусить сказати Маршалу.

Приклад Введення 2  2  9  0  3  1  1  2  5  3  5  4  0  4  5  5  0  5  2  5  5  2  2  3  3  1 Виведення 7

Задача NewTower
 

Підрахувати, яку мінімальну кількість перекладань потрібно зробити, щоб з пірамідки з n<=30) дисками двох кольорів (жовтого та синього) скласти за правилами «Ханойських веж» пірамідки одного кольору. Є 4 стержні: початковий, жовтий, синій і смугастий. На початковому можуть одночасно бути диски двох кольорів, на смугастому будь-якого кольору, але одного, на синьому і жовтому стержнях тільки диски свого кольору. За одне перекладання переноситься один диск з одного стержня на інший і не можна класти більший диск на менший.
Технічні умови. Програма NewTower читає з клавіатури кількість дисків n, потім n чисел 0 або 1 (0 – жовтий диск, 1 синій). Всі числа розділено пропуском. Диски нумеруються, починаючи з верхнього (найменшого). Програма виводить на екран шукану кількість перекладань.
Приклад
Введення
5 1 0 1 0 0
Виведення
10