Информатика

Имеется стопка оладий. Необходимо сделать из них правильную стопку: каждая оладья должна быть не больше всех оладий, находящихся под нею. Все оладьи круглые, поэтому размер оладьи определяется ее диаметром.

Сортировка стопки осуществляется серией “переворотов” оладий. Переворот заключается в том, что вы помещаете лопатку между двумя оладьями и переворачиваете всю стопку, оказавшуюся на лопатке, то есть меняете порядок следования оладий над лопаткой на обратный.

Стопка определяется заданием диаметра каждой оладьи в стопке в порядке следования (сверху вниз). Переворачивание определяется количеством оладий, которое переворачивается. Например, из стопки 7 3 9 1 5 переворачиванием трех оладий получится стопка 9 3 7 1 5.

Вам дана стопка оладий, выведите последовательность переворачиваний (то есть количество оладий, которое нужно переворачивать за один раз), сортирующую данную стопку.

Входные данные
Первая строка входных данных содержит натуральное число N (1 ≤ N ≤ 1000)  – количество оладий в стопке. Далее идет N натуральных чисел, не превосходящих 10⁹  – размеры оладий в стопке (сверху вниз). 

Выходные данные
Ваша программа должна вывести последовательность натуральных чисел, не превосходящих N, соответствующую количеству оладий, которое необходимо переворачивать для правильной сортировки стопки.

Знаменитый театральный критик переезжает в Нью-Йорк. Как известно, все театры в Нью-Йорке размещены на Бродвее, поэтому критик тоже, несомненно, поселится на Бродвее, чтобы быть как можно ближе ко всем театрам. Определите номер дома, в котором должен поселиться критик, чтобы суммарное расстояние от его дома до всех театров было бы минимально. Бродвей представляет собой прямую улицу, на котором подряд, на равном расстоянии друг от друга размещены дома, нумерация которых начинается с 1. В одном доме может находиться несколько театров, критик может поселиться в любом доме, даже если в этом доме находится театр.

Входные данные
Первая строка входных данных содержит одно число N (1 ≤ N ≤10⁵)  – количество театров на Бродвее. Далее идет N натуральных чисел, не превосходящих 10⁹  – номера домов, в которых размещены театры.

Выходные данные
Выведите единственное число  – номер дома, в котором должен поселиться критик.

Примеры

№	Входные данные	Выходные данные
1	2 1 10	5
2	3 1 3 5	3

На конференции работников народного образования с докладами об очередном улучшении финансирования школ желает выступить N министров правительства. Но поскольку министры, как правило, очень заняты, то каждый из министров назначил время, когда он хочет выступить с докладом. Естественно, министры не смогли распределить время между собой, поэтому заявленные ими времена пересекаются. Перед вами стоит задача выбрать из всех поданных заявок несколько непересекающихся, при этом максимизировать число выбранных заявок.

Входные данные
Первая строка входных данных содержит натуральное число N ≤ 10000. Далее идет N строк, каждая из которых содержит два целых числа S_i и T_i, 0 ≤ S_i < T_i ≤ 10⁹. Каждая строка соответствует одной заявке с номером i (1 ≤ i ≤ N), S_i является временем начала заявки, T_i  – временем ее окончания.

Программа должна найти подмножество множества {1, 2, ..., n}, содержащее наибольшее число элементов, такое, что для любых двух элементов i и j из найденного подмножества верно одно из двух неравенств: T_i ≤ S_j или T_j ≤ S_i. Указанные неравенства означают, что заявки с номерами i и j не пересекаются, то есть одна из них заканчивается не позднее, чем начинается другая. При этом время окончания одной удовлетворенной заявки может совпадать со временем начала другой заявки (один министр на трибуне меняется на другого министра). 

Выходные данные
Программа должна вывести номера удовлетворенных заявок в произвольном порядке, разделяя их пробелами. Заявки нумеруются, начиная с 1.

Примеры

№	Входные данные	Выходные данные
1	5 15 25 20 30 10 20 30 40 25 35	3 2 4

Вася написал на длинной полоске бумаги большое число и решил похвастаться своему старшему брату Пете этим достижением. Но только он вышел из комнаты, чтобы позвать брата, как его сестра Катя вбежала в комнату и разрезала полоску бумаги на несколько частей. В результате на каждой части оказалось одна или несколько идущих подряд цифр. Теперь Вася не может вспомнить, какое именно число он написал. Только помнит, что оно было очень большое. Чтобы утешить младшего брата, Петя решил выяснить, какое максимальное число могло быть написано на полоске бумаги перед разрезанием. Помогите ему!

Входные данные
Входные данные представляют собой одну или более строк, каждая из которых содержит последовательность цифр. Количество строк во входном файле не превышает 100, каждая строка содержит от 1 до 100 цифр. Гарантируется, что хотя бы в одной строке первая цифра отлична от нуля.

Выходные данные
Выведите одну строку  – максимальное число, которое могло быть написано на полоске перед разрезанием.

Отсортируйте данный массив. Используйте быструю сортировку.

Входные данные
Первая строка входных данных содержит количество элементов в массиве N, N ≤ 10⁵. Далее идет N целых чисел, не превосходящих по абсолютной величине 10⁹. 

Выходные данные
Выведите эти числа в порядке неубывания.

Преобразуйте дробь.

Входные данные
Дана запись двоичной дроби, как в задаче "Binary periodical fraction to decimal", но в целых числах точки может не быть. Необходимо представить ее в виде несократимой рациональной дроби n/m.

Выходные данные
Программа должна вывести значения n и m .

Дано рациональное число. Запишите его в виде двоичной периодической дроби.

Входные данные
На вход программа получает два натуральных числа n и m, каждое из которых не превосходит 1000.

Выходные данные
Программа должна вывести значение n/m, записанное в виде двоичной периодической дроби, при этом длина непериодической дробной части и длина периода должны быть минимально возможными. Если данное число является конечной двоичной дробью, периодическую часть выводить не надо.

Преобразуйте двоичное число.

Входные данные
Дана запись целого двоичного числа или двоичной периодической дроби, которая включает в себя:

1. Необязательную целую часть.
2. Необязательный символ точки, отделяющий целую часть от дробной. 

3. Необязательную дробную непериодическую часть. 

4. Необязательную периодическую дробную часть, записываемую в круглых скобках.

Выходные данные
Необходимо определить значение этой дроби, сохранить его в переменной типа double и вывести на экран с точностью не менее 12 знаков. Общая длина входной строки не превосходит 30 символов.

Переведите десятичное число в двоичную систему.

Входные данные
Дано действительное неотрицательное число, не превосходящее 100, записанное в десятичном виде. Целые числа при этом могут не содержать точку.

Выходные данные
Необходимо представить число в виде двоичной дроби с фиксированной точкой и вывести это представление. Ответ должен отличаться от правильного не более, чем на 2 − 32 , то есть необходимо вывести не менее 32 двоичных цифр после точки.

Переведите число из двоичной системы счисления в десятичную.

Входные данные
Дано число, представленное в виде двоичной дроби: запись длиной не более 30 символов, содержащая цифры 0 и 1 и, возможно, одну точку.

Выходные данные
Необходимо вывести данное число в виде десятичной дроби (тип переменной double с точностью не менее 12 знаков).

Новый интернет-провайдер предоставляет услугу доступа в интернет с посекундной тарификацией. Для подключения нужно купить карточку, позволяющую пользоваться интернетом определенное количество секунд. При этом компания продает карточки стоимостью 1, 2, 4, …, 2³⁰ рублей на a₀, a₁, a₂, …, a₃₀ секунд соответственно.

Родители разрешили Пете пользоваться интернетом M секунд Определите, за какую наименьшую сумму он сможет купить карточки, которые позволят ему пользоваться интернетом не менее M секунд. Естественно, что Петя может купить как карточки различного достоинства, так и несколько карточек одного достоинства.

Входные данные
В первой строке содержится единственное натуральное число M (1 ≤ M ≤ 109). Во второй строке задаются натуральные числа a₀, a₁, …, a₃₀, не превосходящие 10⁹.

Выходные данные
Выведите единственное число – наименьшую сумму денег, которую Пете придется потратить.

Ввести в символьной форме два многочлена от x с целыми коэффициентами и вывести их произведение в порядке убывания степеней - также в символьной форме.

Ограничения: степень исходных многочленов не более 10, коэффициенты исходных многочленов по модулю не более 10⁴.

Входные данные
В двух строках находятся многочлены.

Выходные данные
В единственной строке выводится многочлен.

На базаре есть ряд из N мест, где продаются семечки подсолнечника. Потенциальные покупатели идут вдоль ряда, затем в некоторый момент останавливаются и покупают семечки. Качество семечек от места к месту различается незначительно, так что разницы только в цене семечек и положении места.

Перед тем как выйти на рынок в качестве ещё одного продавца семечек, Вы провели исследование рынка, чтобы найти зависимость числа покупателей от двух названных факторов. Исследование показывает, что большинство покупателей следуют одному и тому же шаблону. Они проходят мимо нескольких мест, замечая и запоминая цены, а затем после обхода K мест, возвращаются к месту с наименьшей замеченной ценой, совершают там покупку, затем покидают базар. Если есть несколько мест с одинаковой ценой, покупатель выбирает ближайшее.

Предположим, что есть пять мест с ценами 37, 34, 34, 35, 33. Если покупатель с K = 4 идёт слева направо, он видит семечки по ценам 37, 34, 34, 35. В этот момент он решает, что видел достаточно, возвращается к третьему месту и покупает семечки там. Хотя на втором месте цена та же, что и на третьем, покупателю до него идти дальше. Если бы тот же покупатель зашёл справа, он бы увидел цены 33, 35, 34, 34, затем остановился и вернулся бы к пятому месту.

Число мест, пройденных до принятия решения (K), является функцией жадности и терпеливости покупателя, и, очевидно, различается у разных покупателей. Исследование выявило средний процент BK покупателей для всех значений K (1 <= K <= N, 0 <= B_K <= 99, сумма всех B_K равна 100).

Вам следует определить оптимальную стратегию на этом рынке (то есть цену и положение нового места, которое максимизирует ожидаемый средний доход) в предположении, что половина клиентов идёт в направлении от первого места к N-му, а другая половина - от N-го места к первому, и они следуют описанному шаблону.

Входные данные
В первой строке находится число существующих мест N, во второй строке - N целых чисел - цены на каждом месте, в третьей строке - N целых чисел в диапазоне от 0 до 99 - значения BK для каждого K. Все числа в строках разделены пробелами.

Ограничения: 2 <= N <= 100, исходные цены - целые числа от 1 до 9999.

Выходные данные
Выводятся два целых числа - L и P. L (0 < L < N) - это число существующих мест, после которых должно быть размещено новое (Вам не разрешается устанавливать своё место первым или последним). Число P - оптимальная цена. Если существует более чем одно оптимальное решение, Вы должны выбрать решение с минимальным L, а среди них - с минимальным P.

Компания, занимающаяся железнодорожными перевозками, получила заказ сформировать поезд, состоящий из определённого числа вагонов. Проблема в том, что у компании есть вагоны, выпущенные в разное время, так что каждый из вагонов может иметь один из двух видов сцеплений на каждом конце. У компании также есть один локомотив.

Сцепления и для локомотива, и для вагонов обозначены буквой A или B. Повернуть вагон или локомотив противоположной стороной невозможно.

Дана информация о вагонах и локомотиве. Требуется найти число способов сформировать разные поезда заданной длины из имеющихся видов вагонов. Дополнительным требованием является то, что тип сцеплений на каждом конце состава должен соответствовать типу сцеплений локомотива.

Поезда считаются различными, если при их сравнении от одного конца к другому выявляется хотя бы одно отличие.

Пример 1. Пусть у компании есть вагоны AA, AA, AB, BA, BA и локомотив AB. В поезде должно быть 4 вагона. Из данных вагонов можно сформировать только два различных поезда: BAAAABBA и BAABBAAA. Локомотив можно присоединить к поезду как с левого (используя сцепление B), так и с правого конца (используя сцепление A).

Пример 2. Пусть у компании есть только по одному вагону каждого типа (AA, AB, BA, BB) и локомотив AA, а поезд должен состоять из трёх вагонов. Существует три способа сформировать поезд: AAABBA, ABBAAA и ABBBBA.

Входные данные
В первой строке через пробел N - число вагонов, находящихся в распоряжении компании, и K - требуемая длина поезда в вагонах. Вторая строка описывает тип сцеплений локомотива. Следующие N строк описывают типы сцеплений вагонов. Описания даны как AB, AA, BB или BA.

Ограничения: 1 <= K <= N <= 40.

Выходные данные
В первой строке выводится слово "YES", если можно сформировать хотя бы один поезд, или "NO" - в противном случае.

Если поезд сформировать возможно, во второй строке должно указываться число способов это сделать.

Даны длины трёх отрезков. Если возможно, требуется построить треугольник, в котором один из этих отрезков был бы высотой, один - биссектрисой и один - медианой; все построенные из одной вершины.

Ограничения: длина каждого из трёх отрезков от 0.01 до 100, точность результата должна быть 0.001.

Входные данные
Вводятся три положительных числа, разделённых пробелами, - длины отрезков.

Выходные данные
Выводится одно число - площадь треугольника. Если треугольник нельзя построить, вывести -1. Если может быть построено несколько треугольников с разными площадями, вывести 0.

В калькулятор вводится натуральное число K и нажимается клавиша "+". Калькулятор всё ещё показывает K. Цель игры: получить на экране число, состоящее из одинаковых цифр. Для её достижения можно производить только одно действие - нажимать на клавишу "=" (возможно, 0 раз). После первого нажатия получается результат K + K, после очередного нажатия результат увеличивается на K. Требуется определить, удастся ли достичь цели, а если удастся, то какое число, состоящее из одинаковых цифр, будет получено первым. Количество отображаемых калькулятором цифр считать неограниченным, время работы батареек - тоже.

1 <= K <= 999.

Входные данные
В первой строке находится одно число - K.

Выходные данные
Если цели достичь невозможно, вывести "Impossible", если возможно, вывести два числа через пробел: цифру, из которой состоит искомое число, и количество цифр в числе.

Рассматриваемые пирамиды имеют треугольник в основании, то есть являются тетраэдрами. Требуется по заданным длинам рёбер пирамиды найти её объём.

Ограничения: длины рёбер - целые положительные числа, не превосходящие 1000.

Входные данные

В первой строке находятся 6 чисел через пробел - длины рёбер пирамиды ABCD. Порядок рёбер: AB, AC, AD, BC, BD, CD.

Выходные данные

Вывести одно вещественное число с четырьмя знаками после запятой - объём пирамиды.

При решении задач баллистики следует учитывать сопротивление воздуха. Пусть сила сопротивления воздуха пропорциональна квадрату модуля скорости движения снаряда и направлена противоположно скорости. Считая коэффициент пропорциональности силы сопротивления воздуха квадрату скорости постоянной величиной, рассчитать дальность полёта снаряда (с точностью до 10 м) при стрельбе из 85-миллиметровой пушки Д-44 под заданным углом к горизонту, если масса снаряда равна 9.6 кг, а начальная скорость - 800 м/с. Известно также, что при стрельбе под углом 45 градусов дальность стрельбы составляет 15 650 м. Ускорение свободного падения считать равным 9.8 м/с².

Ограничения: угол от 5 до 85 градусов.

Входные данные
В первой строке находится единственное вещественное число - угол в градусах.

Выходные данные
Вывести одно целое число - дальность в метрах.

Ограниченный алгоритм Маркова состоит из последовательности предложений где s_i и d_i - символы из алфавита A, B, C. Подстрока s₁s₂...s_N называется левой частью, а d₁d₂...d_N - правой частью предложения.

Алгоритм выполняется над исходной текстовой строкой, состоящей из прописных латинских букв A, B, C, следующим образом: перебираются все предложения, начиная с первого. Если левая часть предложения входит в текстовую строку, то самое левое вхождение заменяется правой частью этого предложения, и поиск вновь начинается с первого предложения. Если ни одно предложение не может быть применено, алгоритм останавливается.

При выполнении алгоритма возможны два результата: либо остановка, либо бесконечный цикл с определенным периодом. По данной строке и набору предложений алгоритма Маркова определить количество "ациклических" (выполненных до начала цикла) шагов и длину самого цикла. Если алгоритм останавливается, то длина цикла считается нулевой, а все выполненные шаги - ациклическими.

Входные данные
В первой строке находится исходная текстовая строка, а в следующих строках - предложения, по одному в строке. Строки могут содержать произвольное количество незначащих пробелов.

Ограничения: длина исходной текстовой строки и левых частей предложений - от 1 до 12 букв, количество предложений - от 1 до 50.

Выходные данные
Вывести два целых числа, разделённых пробелом - количество ациклических шагов и длину цикла.

Дан набор переменных x₁, x₂, ..., x_N. Каждая переменная x_i может принимать значение только -1, 0 или +1. Для данного целого числа S требуется определить количество способов присвоить переменным xi значения так, чтобы сумма всех возможных произведений x_i * x_j была равна S, где i < j и i, j = 1, 2, ..., N. Два способа считаются различными, если они содержат различное число x_i = 0.

Ограничения: 2 <= N <= 10 000, -10 000 < S < 10 000.

Входные данные
В первой строке находятся числа N и S, разделённые пробелом.

Выходные данные
Вывести одно целое число - количество способов представить S как сумму произведений.