Задача Street
У місті Нью-Петрики побудували нову вулицю. Будинки поставили в одну лінію, а не в дві – не змогли дійти згоди про ширину проїжджої частини… Перший будинок мав 1 поверх, другий – 2 і т.д., тобто в кожному наступному будинку поверхів на один більше, ніж в попередньому. Для покращення зовнішнього вигляду фасади будинків вирішили пофарбувати – кожен поверх в свій колір. Але, як водиться, фарбу купили лише 2-х кольорів – білу і червону. Мер вирішив, що 2 білі поверхи в одному будинку може бути підряд, а ось 2 червоні – ні. Зрозуміло, що будь який будинок можна розфарбувати (кожен поверх в свій колір) не одним способом. Програмісту Хакерову доручили порахувати кількість способів фарбування для кожного з достатньо великої кількості будинків вулиці. Його програма вивела на принтер послідовно кількість способів для кожного будинку від першого до останнього без пропусків (помилився з форматом Виведення, таке в нього вже було на першому турі NetOI). Вийшов чималий рядок цифр. Допоможіть Хакерову знайти N-ту цифру в цьому рядку (зрозуміло, що цифра з номером N є в роздруківці).
Технічні умови. Програма Street читає з клавіатури єдине число N (1 ≤ N ≤ 10000000) – номер цифри в послідовності і виводить на екран єдине число – шукану величину.
Приклади
|
Введення 3 Виведення 5 |
Введення 14 Виведення 9 |
Задача 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 читає з клавіатури координати Намцога, кількість терористів, їх координати, кількість будинків, координати лівих нижніх кутів кожного будинку. Всі числа розділено пропусками. Програма виводить на екран єдине число, яке підполковник мусить сказати Маршалу.
|
Приклад
Введення |
 |
Задача NewTower
Підрахувати, яку мінімальну кількість перекладань потрібно зробити, щоб з пірамідки з n<=30) дисками двох кольорів (жовтого та синього) скласти за правилами «Ханойських веж» пірамідки одного кольору. Є 4 стержні: початковий, жовтий, синій і смугастий. На початковому можуть одночасно бути диски двох кольорів, на смугастому будь-якого кольору, але одного, на синьому і жовтому стержнях тільки диски свого кольору. За одне перекладання переноситься один диск з одного стержня на інший і не можна класти більший диск на менший.
Технічні умови. Програма NewTower читає з клавіатури кількість дисків n, потім n чисел 0 або 1 (0 – жовтий диск, 1 синій). Всі числа розділено пропуском. Диски нумеруються, починаючи з верхнього (найменшого). Програма виводить на екран шукану кількість перекладань.
Приклад
Введення
5 1 0 1 0 0
Виведення
10
Г.Кравець, Д.Нейтер, Г.Непомнящий, Ю.Пасіхов, І.Порубльов