Алгоритмы

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

Входные данные
Программа получает на вход строку, состоящую из цифр 0, ..., 9 и букв A, ..., F, являющуюся записью некоторого 16-ричного целого числа. Длина строки не превосходит 50 символов, первый символ в строке не равен 0. Необходимо вывести запись этого числа в двоичном виде без лидирующих нулей. 

Выходные данные
Выведите результат перевода.

Фирма OISAC выпустила новую версию калькулятора. Этот калькулятор берет с пользователя деньги за совершаемые арифметические операции. Стоимость каждой операции в долларах равна 5% от числа, которое является результатом операции. На этом калькуляторе требуется вычислить сумму N натуральных чисел (числа известны). Нетрудно заметить, что от того, в каком порядке мы будем складывать эти числа, иногда зависит, в какую сумму денег нам обойдется вычисление суммы чисел (тем самым оказывается нарушен классический принцип “от перестановки мест слагаемых сумма не меняется”). Например, пусть нам нужно сложить числа 10, 11, 12 и 13. Тогда если мы сначала сложим 10 и 11 (это обойдется нам в 1.05 €), потом результат с 12 (1.65 €), и затем с 13 (2.3 €), то всего мы заплатим 5 €, если же сначала отдельно сложить 10 и 11 (1.05 €), потом 12 и 13 (1.25 €) и, наконец, сложить между собой два полученных числа (2.3 €), то в итоге мы заплатим лишь 4.6 €. Напишите программу, которая будет определять, за какую минимальную сумму денег можно найти сумму данных N чисел.

Входные данные
Первая строка входных данных содержит число N (2 ≤ N ≤ 10⁵). Во второй строке заданы N натуральных чисел, каждое из которых не превосходит 10000.

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

Реализуйте структуру данных типа “множество строк”. Хранимые строки  – непустые последовательности  длиной не более 10 символов, состоящие из строчных латинских букв. Структура данных должна поддерживать операции добавления строки в множество, удаления строки из множества и проверки принадлежности данной строки множеству. Максимальное количество элементов в хранимом множестве не превосходит 10⁶.

Входные данные
Каждая строка входных данных задает одну операцию над множеством. Запись операции состоит из типа операции и следующей за ним через пробел строки, над которой проводится операция. Тип операции  – один из трех символов:    + означает добавление данной строки в множество;     -  означает удаление  строки из множества;      ?  означает проверку принадлежности данной строки множеству. Общее количество операций во входном файле не превосходит 106. Список операций завершается строкой, в которой записан один символ # – признак конца входных данных. При добавлении элемента в множество НЕ ГАРАНТИРУЕТСЯ, что он отсутствует в этом множестве. При удалении элемента из множества НЕ ГАРАНТИРУЕТСЯ, что он присутствует в этом множестве.

Выходные данные
Программа должна вывести для каждой операции типа ? одну из двух строк YES или NO, в зависимости от того, встречается ли данное слово в нашем множестве.

Реализуйте структуру данных типа “множество строк”. Хранимые строки  – непустые последовательности  длиной не более 10 символов, состоящие из строчных латинских букв. Структура данных должна поддерживать операции добавления строки в множество и проверки принадлежности  данной строки множеству. Максимальное количество элементов в хранимом множестве не превосходит 10⁶.

Входные данные
Каждая строка входных данных задает одну операцию над множеством. Запись операции состоит из типа операции и следующей за ним через пробел строки, над которой проводится операция. Тип операции  – один из двух символов:   +  означает добавление данной строки в множество;  ?  означает проверку принадлежности данной строки множеству. Общее количество операций во входном файле не превосходит 10⁶. Список операций завершается строкой, в которой записан один символ # – признак конца входных данных. При добавлении элемента в множество НЕ ГАРАНТИРУЕТСЯ, что он отсутствует в этом множестве.

Выходные данные
Программа должна вывести для каждой операции типа ? одну из двух строк YES или NO, в зависимости от того, встречается ли данное слово в нашем множестве.

Дано два массива. Для каждого элемента второго массива определите, сколько раз он встречается в первом массиве.

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

Выходные данные
Выведите M чисел: для каждого элемента второго массива выведите, сколько раз такое значение встречается в первом массиве.

Ожерелье представляет собой нитку, на которую надето 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 знаков).

В этой задаче Вам вновь придется помочь Берляндии. Эта страна состоит из n городов, некоторые пары из которых соединены двусторонними дорогами, каждая дорога характеризуется своей длиной. Все города пронумерованы числами от 1 до n, столица имеет номер 1. Время от време ни Президент объезжает страну, посещая города страны. Целью каждой поездки является один из городов, к которому он едет из столицы вдоль дорог одним из кратчайших путей.

В далекие времена (когда задачи на алгоритм Дейкстры вызывали сложность) специальное ведомство составила такой набор дорог T, вдоль которого можно было проехать из столицы в любой город, причем единственным образом. Разумеется, путь по дорогам из набора T из столицы в каждый город являлся кратчайшим. Особо умные жители страны попросту называли этот набор дорог "деревом кратчайших путей". Известно, что Президент пользовался дорогами из T во время своих поездок. За прошедшие годы этот набор перестал быть секретным, и, поэтому, стал объектом повышенного внимания берляндских экстремистов. У специального ведомства новое задание. Для каждого города кроме столицы необходимо вычислить кратчайшее расстояние до него, при условии, что та дорога по которой Президент должен был закончить свой путь в этот город является атакованной и проезжать по ней нельзя.

Входные данные
В первой строке входного файла записана пара целых чисел n и m (2 ≤ n≤ 4000; n−1 ≤ m ≤100000), где n — количество городов в стране, а m— количество дорог в этой стране. Далее в m строках содержатся описания дорог, по одной дороге в строке. Каждая дорога задается четверкой целых чисел a_j, b_j, l_j, t_j , где a_j, b_j это номера городов, соединяемых дорогой (1 ≤ a_j,b_j ≤ n; a_j≠b_j), l_j — ее длина (1 ≤ l_j≤ 10⁵), а t_j равно 1 если дорога принадлежит дереву кратчайших путей и 0 в противном случае.

Гарантируется, что набор T удовлетворяет описанным выше свойствам. Между парой городов может быть более одной дороги. Все дороги двусторонние.

Выходные данные
Выведите n−1 число в строку через пробелы. i-ое число должно быть равно либо длине кратчайшго пути из столицы в город i+1, при условии, что по той дороге из T, которой Президент заканчивал свой путь в этот город, передвигаться нельзя, либо -1, если добраться до города i+1 вообще невозможно.

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

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

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

Выходные данные
Выведите турнирную таблицу в следующем формате. Таблица должна состоять из K строк с результатами игр команд, занявших первое, второе, …, последнее место (команды, набравшие одинаковое число очков, могут быть расположены в таблице в любом порядке). В каждой строке должно быть записано K чисел через пробел – количество очков, набранных в игре данной команды с первой, второй, … командами соответственно. Количество очков – это число 0, 1 или 2. В клетках на главной диагонали (соответствующих не существующей игре команды "самой с собой") нужно записать нули.

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

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

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

Входные данные
В первой строке содержится единственное натуральное число M (1 ≤ M ≤ 109). Во второй строке задаются натуральные числа a₀, a₁, …, a₃₀, не превосходящие 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.