Задача Street
В городе Нью-Петрики построили новую улицу. Дома поставили в одну линию, а не в две – не смогли прийти к согласию о ширине проезжей части. Первый дом имел 1 этаж, второй – 2 и т.д., то есть в каждом следующем доме этажей на один больше, чем в предыдущем. Для улучшения внешнего вида фасады домов решили покрасить – каждый этаж в свой цвет. Но как водится, краску купили лишь 2-х цветов – белую и красную. Мэр решил, что 2 белых этажа в одном доме могут быть подряд, а вот 2 красных – нет. Понятно, что любой из домов можно раскрасить (каждый этаж в свой цвет) не единственным способом. Программисту Хакерову поручили посчитать количество способов окрашивания для каждого из достаточно большого количества домов улицы. Его программа вывела на принтер последовательно количество способов для каждого дома от первого до последнего без пропусков (ошибся с форматом выведения, такое у него уже было на первом туре NеtOI). Вышла достаточно большая строка цифр. Помогите Хакерову найти 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 года планируется включить новый вид спорта «кросcгроуп». Команда состоит из 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 (n<=30) дисками двух цветов (желтого и синего), составить по правилам «Ханойских башен» пирамидки одного цвета. Есть 4 стержня: начальный, желтый, синий и полосатый. На начальном могут одновременно быть диски двух цветов, на полосатом любого цвета, но одного, на синем и желтом стержнях только диски своего цвета. За одно перекладывание переносится один диск с одного стержня на другой и нельзя класть больший диск на меньший.
Технические условия. Программа NewTower читает с клавиатуры количество дисков n, потом n чисел 0 или 1 (0 – желтый диск, 1 - синий). Все числа разделены пробелом. Диски нумеруются, начиная с верхнего (наименьшего). Программа Выводит на экран искомое количество перекладываний.
Пример
Ввод
5 1 0 1 0 0
Вывод
10
