Информатика

Как известно, красить забор Тому Сойеру помогали многочисленные друзья. Каждый друг покрасил неcколько подряд идущих досок, при этом какие-то доски могли быть покрашены несколько раз, а какие-то доски могли остаться непокрашенными. Определите общее количество покрашенных досок.

Входные данные
В первой строке содержится натуральное число N ≤ 10⁵  – количество друзей Тома Сойера. Далее идет N пар целых неотрицательных чисел  – номер (от начала забора) доски, с которой друг начал красить забор и номер доски, на которой он закончил покраску. Каждый друг покрасил непрерывный участок забора, включая две заданные доски. Номера досок  – целые числа от 1 до 10⁹.

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

Пастбище представляет собой прямоугольник, разбитый на N  x N  клеток. В каждой клетке растет трава, имеющая свою калорийность (во всех клетках калорийность травы разная). В левой нижней клетке стоит корова Мурка. Съев всю траву в своей клетке, она перемещается на одну клетку вправо или на одну клетку вверх, всегда выбирая ту из клеток, калорийность травы в которой больше (за пределами поля трава не растет). В конце концов корова приходит в правую верхнюю клетку. Требуется определить, сколько всего калорий получит корова (считая калории травы в первой и в последней клетках).

Входные данные
Сначала вводится число N  – размер поля (2 ≤ N  ≤ 10). В следующей строке вводятся через пробел числа, задающие количество калорий в клетках верхнего ряда, в следующей – количество калорий в клетках следующего ряда, …, в последней – количество калорий в клетках нижнего ряда. Все числа – различные, натуральные, не превосходящие 100.

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

Что выведет на экран приведенный ниже программный код?

a = "I'm studying"
b = 'Python'

print('a')
print('b')

1)
I'm studying
Python
2)
'a'
'b'
3)
I'm studying Python
4)
a
b
5)
произойдёт ошибка

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

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

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

Отрезок целочисленной прямой длины N разбит на единичные отрезки, которые пронумерованы от 1 до N.

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

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

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

Первоначально нет ни одной группы.

Входные данные
Первая строка входных данных содержит число N – количество отрезков и число K – количество запросов (1 ≤ N, K ≤10⁵). Далее идет K строчек, содержащих запросы к структуре данных. Каждый запрос начинается с числа 1 (запрос на создание группы) или 2 (запрос на удаление группы). После числа 1 указывается два других числа l и r (1 ≤ l ≤ r ≤ N), после числа 2 указывается одно число i (1 ≤ i ≤ N).

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

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

Реализуйте структуру данных, которая на данном массиве из N целых чисел позволяет узнать максимальное значение на этом массиве и индекс элемента, на котором достигается это максимальное значение.

Входные данные
В первой строке вводится натуральное число N (1 ≤  N ≤ 10⁵) – количество элементов в массиве. В следующей строке содержатся N целых чисел, не превосходящих по модулю 10⁹ – элементы массива. Далее идет число K  (0 ≤ K ≤ 10⁵) – количество запросов к структуре данных. Каждая из следующих K строк содержит два целых числа l и r (1 ≤ l ≤ r ≤ N) – левую и правую границы отрезка в массиве для данного запроса.

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

Напишите программу, переводящую запись числа между двумя произвольными системами счисления.

Входные данные
На вход программа получает три величины: n, A, k, где n и k — натуральные числа от 2 до 36, основания системы счисления, A — число, записанное в системе счисления с основанием n, A<2³¹.

Выходные данные
Необходимо вывести значение A в системе счисления с основанием k без лидирующих нулей.

Цифры записываются следующими символами: 0, 1, 2, ..., 9, A, B, C, ..., Z.

Ожерелье представляет собой нитку, на которую надето N различных бусинок. У нитки два конца: левый и правый. С бусинками на нитке можно делать следующие операции:

ML (move left) – снять крайнюю левую бусинку и надеть ее на правый конец нитки. По сути, при этом происходит циклический сдвиг ожерелья.
MR (move right) – снять правую бусинку и надеть ее на левый конец.
RL (remove left) – снять крайнюю левую бусинку и положить ее на стол (не одевать на нитку).
RR (remove right) – снять крайнюю правую бусинку и положить ее на стол.
PL (put left) – взять со стола бусинку и надеть ее на левый конец нитки.
PR (put right) – взять со стола бусинку и надеть ее на правый конец нитки.

На столе может лежать не более одной снятой бусинки, то есть после операции RL или RR нельзя использовать другую операцию RL или RR, пока не будет выполнена операция PL или PR.

Ваша задача: используя только перечисленные операции, отсортировать исходное ожерелье.

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

Выходные данные
Программа должна вывести последовательность команд ML, MR, RL, RR, PL, PR, которая переводит исходную перестановку бусинок к перестановке 1, . . . , N.

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

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

Стопка определяется заданием диаметра каждой оладьи в стопке в порядке следования (сверху вниз). Переворачивание определяется количеством оладий, которое переворачивается. Например, из стопки 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⁴.

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

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