Информатика

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

Для уменьшения конкуренции театры хотят разместиться в домах на этой улице так, чтобы минимальное расстояние между двумя соседними театрами было как можно больше.

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

Первая строка входных данных содержит  количество домов на улице N и количество театров K (1 ≤ K ≤ N ≤ 104). Далее идет N чисел в порядке возрастания  – координаты домов на улице.

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

Выведите единственное число  – наибольшее возможное допустимое расстояние между театрами.

Девочка Катя подключилась к тарифу “Очень выгодный”, на котором можно только звонить. Все входящие звонки бесплатны. В случае исходящего звонка не более k₁ первых секунд звонка стоят p₁ копеек, и позвонить можно только если эти деньги на счету есть. За следующие k₂ секунд Катя платит по p₂ копеек за секунду, а все остальное время девочка платит по p₃ копеек за секунду. Деньги снимаются мгновенно после каждой секуны. Как только баланс становится неположительным, связь обрывается. Известно, что Катя положила N копеек на счет, чтобы поговорить со своим лучшим другом. Причем, она хочет потратить все N копеек на этот один телефонный звонок. Посчитатйте, сколько максимально секунд Катя сможет наслаждаться беседой.

Входные данные
Во входном файле записаны через пробел 6 целых чисел: 0 ≤ N ≤ 1000000, 1≤ k₁,k₂ ≤ 1000000, 1 ≤ p₁, p₂, p₃ ≤ 1000000.

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

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

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

Входные данные
В первой строке входных данных задаются целые числа N (2 <= N <= 10) и R (0 < R ≤ 50. В следующих Nстроках  содержится по 4 числа, описывающих движение кораблей. Первые два числа строки – координаты корабля в момент времени 0, по модулю не превосходящие 10⁵. Следующие два числа – значения координат вектора скорости, по модулю не превосходящие 1000. Все эти числа целые.

Гарантируется, что никакие 2 корабля не имеют одинаковые векторы скорости.Однако вполне возможно, что в какой-то момент времени два корабля пройдут через одну точку.

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

Если решений несколько, выведите любое из них.

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

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

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

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

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

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

Вася последовательно сортировал всю таблицу несколько раз. Вам дана последовательность номеров столбцов, по которым Вася сортировал таблицу — в этой последовательности один и тот же столбец мог встречаться несколько раз, например, если Вася отсортировал ее сначала по 1-му столбцу, потом по 2-му, а затем снова по 1-му.

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

Входные данные
В первой строке вводится одно число N – количество сортировок, которые сделал Вася (1 ≤ N ≤ 10⁶).  Во второй строке содержатся N натуральных чисел, не превосходящих 10⁵ – номера столбцов, по которым осуществлялась сортировка, в том порядке, в котором Вася это делал. Среди чисел могут быть равные.

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

Жил-был жадный Король. Он приказал своему главному Архитектору построить стену вокруг его замка. Король был таким жадным, что не послушал предложение Архитектора построить красивую кирпичную стену совершенной формы с изящными высокими башнями. Вместо этого он приказал построить стену вокруг всего замка, используя минимальное количество камня, но потребовал, чтобы стена не подходила к замку ближе некоторого расстояния. Если Король узнает, что Архитектор использовал больше ресурсов для постройки стены, чем было абсолютно необходимо для удовлетворения требований, Архитектор лишится головы. Более того, Архитектор должен представить проект стены, где указано точное количество ресурсов.

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

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



Входные данные
Первая строка содержит два целых числа N и L, разделённых пробелом: N - число углов в замке Короля, а L - минимальное число футов, на которое Король разрешил приблизить стену к замку.

Следующие N строк описывают координаты углов замка в порядке обхода по часовой стрелке. Каждая строка содержит два целых числа x_i и y_i, разделённых пробелом и представляющих собой координаты i-го угла в футах. Все углы имеют различные координаты, и стены замка не пересекаются иначе как в углах.

Ограничения: 3 <= N <= 1000, 1 <= L <= 1000, -10 000 <= x_i, y_i <= 10 000.

Выходные данные
Выводится единственное число - минимальная длина стены в футах, которая может быть построена вокруг замка согласно требованиям Короля. Вы должны представить Королю целое число футов, потому что вещественные числа ещё не изобретены. Однако результат нужно округлить так, чтобы он отличался не более чем на 8 дюймов от правильного (1 фут = 12 дюймов), потому что большей неточности Король не потерпит.

Напишите программу, выполняющую функции очень простой электронной таблицы. Она работает с таблицей из 9 строк от 1 до 9 и 26 столбцов от A до Z. Клетки таблицы обозначаются именами, составленными из кодов столбца и строки, например, B1, S8.

Каждая клетка содержит выражение. Выражения используют целые константы, ссылки на клетки, скобки, бинарные операторы +, -, * и / (целочисленное деление). Например, 567, E8/2, (3+B3)*(C4-1) являются правильными выражениями. Все операторы целочисленные. Деление на ноль даёт в результате ноль.

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

Ограничения: длина выражения в одной ячейке до 255 символов, все аргументы и результаты меньше 1 000 000.

Входные данные
Первая строка содержит число выражений N. Следующие N строк имеют формат <Имя клетки>=<выражение>. Все выражения корректные, и каждая ячейка определена не более чем одним выражением.

Выходные данные
В единственной строке выводится или значение клетки A1, или число 1000000 (один миллион), если значение клетки A1 не может быть найдено из-за циклической ссылки.

Жил-был жадный Король. Он приказал своему главному Архитектору построить поле для королевского крикета в парке. Король был таким жадным, что не послушал предложение своего Архитектора построить поле прямо в центре парка и окружить его живописным бордюром деревьев, специально посаженных вокруг. Вместо этого он приказал не срубать деревья и не сажать новых, но построить самое большое поле для крикета, какое только можно. Если Король обнаружит, что Архитектор посмел тронуть даже единственное дерево в парке или спроектировал меньшее поле, чем было возможно, Архитектор лишится головы. Более того, он потребовал от Архитектора представить план поля, где указаны его точное положение и размер.

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

Задача слегка упрощена тем, что парк Короля имеет прямоугольную форму и расположен на плоской поверхности. Более того, границы парка параллельны направлениям север - юг и восток - запад. В то же время игра в королевский крикет всегда происходит на квадратном поле, границы которого также параллельны направлениям север - юг и восток - запад. Архитектор уже сопоставил парку прямоугольную декартову систему координат и точно определил координаты каждого дерева. Оси этой системы координат, конечно, параллельны направлениям север - юг и восток - запад. Юго-западный угол парка имеет координаты (0, 0), а северо-восточный - координаты (W, H), где W и H - длина и ширина парка соответственно.

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



Входные данные
Первая строка содержит три целых числа, N, W и H, разделённых пробелами: N - число деревьев в парке, W и H - длина и ширина парка соответственно.

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

Ограничения: 1 <= N <= 100, 1 <= W, H <= 10 000, 0 <= x_i <= W, 0 <= y_i <= H.

Выходные данные
Вывести через пробел три целых числа, P, Q и L, где (P, Q) - координаты юго-западного угла поля для крикета, L - длина его сторон. Если существует несколько возможных положений поля максимального размера, вывести любое.

Билл пытается компактно представить последовательности прописных символов от A до Z с помощью упаковки повторяющихся подпоследовательностей внутри них. Например, один из способов представить последовательность AAAAAAAAAABABABCCD - это 10(A)2(BA)B2(C)D. Он формально определяет сжатые последовательности символов и правила перевода их в несжатый вид следующим образом:

• Последовательность, содержащая один символ от A до Z, является упакованной. Распаковка этой последовательности даёт ту же последовательность из одного символа.
• Если S и Q - упакованные последовательности, то SQ - также упакованная последовательность. Если S распаковывается в S', а Q распаковывается в Q', то SQ распаковывается в S'Q'.
• Если S - упакованная последовательность, то X(S) - также упакованная последовательность, где X - десятичное представление целого числа, большего 1. Если S распаковывается в S', то X(S) распаковывается в S', повторённую X раз.

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

Ограничения: длина исходной последовательности от 1 до 100.

Входные данные
В первой строке находится последовательность символов от A до Z.

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

Определим правильные скобочные выражения так:

Пустое выражение - правильное.
Если выражение S правильное, то (S) и [S] также правильные.
Если выражения A и B правильные, то и выражение AB - правильное.
Дана последовательность скобок "(", ")", "[" и "]". Требуется найти самое короткое правильное выражение, в котором данная последовательность является подпоследовательностью, то есть такое, из которого можно вычеркнуть некоторые символы (возможно, ноль) и получить исходную последовательность, не меняя порядок оставшихся.

Ограничения: исходная последовательность содержит не более 100 скобок.

Входные данные
В первой строке находятся символы (, ), [ и ] без пробелов.

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

Примеры

№	Входные данные	Выходные данные
1	([(]	()[()]
2	(	()

{F_k} - бесконечная последовательность целых чисел, которая удовлетворяет условию Фибоначчи F_k = F_k - 1 + F_k - 2 (для любого целого k). Даны i, F_i, j, F_j, n (i <> j). Найти F_n. Пример части последовательности:

k	-2	-1	0	1	2	3	4	5	6
Fk	-5	4	-1	3	2	5	7	12	19

Ограничения: -1000 <= i, j, n <= 1000, -2 000 000 000 <= F_k <= 2 000 000 000 (k = min(i, j, n) ... max(i, j, n)).

Входные данные
В первой строке находятся числа i, F_i, j, F_j, n.

Выходные данные
Вывести одно число F_n.

Две бесконечные равномерные прямоугольные решётки заданы размерами ячеек x₁ y₁ и x₂ y₂. Решётки расположены на плоскости параллельно друг другу и координатным осям так, что смещение одного из узлов второй решётки относительно узла первой составляет Dx по горизонтали и Dy по вертикали. В результате наложения образуется новая, "составная" решётка с более мелкими ячейками различного размера. Требуется вывести в порядке возрастания все различные площади ячеек составной решётки.

Ограничения: 1 <= x₁, y₁, x₂, y₂ <= 100, 0 <= D_x < x₁, 0 <= D_y < y₁, все числа целые.

Входные данные
В первой строке находятся числа x₁, y₁, x₂, y₂, D_x, D_y, разделённые пробелами.

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

Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке (x₁, y₁), а вторая - в точке (x₂, y₂).

К сожалению, осталось лишь несколько отрезков трубы различной длины. Более того, из-за специфики местной технологии трубы могут быть проложены только в направлении с севера на юг или с востока на запад и соединяются, образуя или прямую, или угол 90 градусов. Требуется, зная длины отрезков труб L₁, L₂, ..., L_K и количество отрезков каждой длины C₁, C₂, ..., C_K, сконструировать трубу, соединяющую две заданные точки, или определить, что это невозможно.

Ограничения: 1 <= K <= 4, 1 <= x₁, y₁, x₂, y₂, L_i <= 1000, 1 <= C_i <= 10, все числа целые.



Входные данные
В первой строке находятся числа x₁, y₁, x₂, y₂, K, затем 2_K чисел: L₁, L₂, ..., L_K, C₁, C₂, ..., C_K.

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

Гирлянда состоит из N лампочек на общем проводе. Один её конец закреплён на заданной высоте A мм (H₁ = A). Благодаря силе тяжести гирлянда прогибается: высота каждой неконцевой лампы на 1 мм меньше, чем средняя высота ближайших соседей (H_i = (H_i - 1 + H_i + 1) / 2 - 1 для 1 < i < N). Требуется найти минимальную высоту второго конца B (B = H_N) при условии, что ни одна из лампочек не должна лежать на земле (H_i > 0 для 1 <= i <= N).

Ограничения: 3 <= N <= 1000 - целое, 10 <= A <= 1000 - вещественное.

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

Выходные данные
Вывести одно вещественное число B с двумя знаками после запятой.

Каждый член последовательности десятичных цифр d¹, d², d³..., начиная с четвёртого, равен последней цифре суммы трёх предыдущих. По заданным d¹, d², d³ найти N-й член последовательности.

Ограничения: 1 <= N <= 10¹⁵.

Входные данные
В первой строке находятся цифры d₁, d₂, d₃, разделённые пробелами, во второй - число N.

Выходные данные
Вывести одну цифру - d_N.

Напишите программу, реализующую сложение, вычитание, умножение и деление дробей. Формат дробей во входных и выходных данных:

• знак числа (пишется только в случае, когда его отсутствие изменяет число);
• целая часть числа (нулевая целая часть не пишется, если есть числитель и знаменатель);
• пробел (не пишется, если отсутствует целая или дробная часть);
• числитель (если он не равен нулю);
• знак / (если есть числитель);
• знаменатель (если есть числитель).

Примеры представления дробных чисел: -7 3/4, 8 1/2, -7/11, 0, 11.

Ограничения (как на входные, так и на выходные данные): целая часть может принимать значения из диапазона 0...30 000, числитель и знаменатель могут принимать значения от 1 до 30 000, при делении второй операнд не равен нулю.

Входные данные
В первой строке вводится дробь (первый операнд), во второй - знак операции ("+" - сложение, "-" - вычитание, "*" - умножение, "/" - деление), в третьей строке - дробь (второй операнд). Обе дроби могут быть сократимы.

Выходные данные
В единственной строке выводится несократимая правильная дробь (результат) в описанном формате.

В последовательности чисел a₁, a₂, a₃, ... задан первый член, а остальные вычисляются по формуле a_i = (a_i - 1)2 mod 10 000. Найти N-й член последовательности.

Ограничения: 0 <= a₁ < 10 000, 1 <= N <= 2 000 000 000.

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

Выходные данные
Вывести одно число - a_N.

Строку Фибоначчи F(K) для натуральных чисел K определим так: F(1) = 'A', F(2) = 'B', F(K) = F(K - 1) + F(K - 2) при K > 2, где "+" означает конкатенацию строк. Требуется найти количество вхождений строки S, состоящей из символов A и B, в строку Фибоначчи F(N).

Ограничения: длина S от 1 до 25, 1 <= N <= 45.

Примечание. Длина F(45) равна 1 134 903 170.

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

Выходные данные
Выводится одно число - количество вхождений строки S в строку Фибоначчи F(N).

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

Входные данные
В первой строке содержится число прямоугольников N. Далее идут N строк, содержащих по 4 числа x₁, y₁, x₂, y₂ - координаты двух противоположных углов прямоугольника.

Ограничения: 1 <= N <= 100, координаты представляют собой целые числа и по абсолютной величине не превосходят 10 000.

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

Три компьютера соединены сетью. Один из них - сервер, два других - клиенты. На сервере есть несколько файлов. Полные имена файлов, состоящие из двух частей (имя и расширение), различны. Оба клиента знают полные имена всех файлов, находящихся на сервере. Сервер выбирает один из своих файлов и посылает его имя одному из клиентов, а расширение - второму.

Затем клиенты начинают общаться друг с другом, пытаясь определить, какой файл был выбран сервером (они хотят узнать полное имя файла). Однако клиенты вынуждены общаться очень ограниченным способом. Они по очереди посылают сообщения друг другу, но могут сказать только, что не знают полного имени файла. Если клиент не знает полного имени выбранного файла, он может послать другому клиенту сообщение, говорящее: "Я не знаю полного имени файла". Клиенты чередуются, посылая только это сообщение туда и обратно. Так продолжается до тех пор, пока один из клиентов не узнает полное имя файла, или они не решат закончить диалог. Клиент, получивший первую часть полного имени файла, всегда ждёт, что второй клиент пошлёт первое сообщение.

Пусть Вы знаете все полные имена файлов, находящихся на сервере, и слушаете разговор клиентов. Основываясь на этой беседе, Вы должны определить набор файлов, которые могли быть выбраны сервером. Файлы в этом наборе называются файлами-кандидатами.

Входные данные
В первой строке находятся два целых числа, N и M, разделённые пробелом: N - число файлов на сервере, M - число сообщений, посланных клиентами, пытающимися определить полное имя файла.

Каждая из следующих N строк содержит одно полное имя файла. Полное имя файла дано в стиле, аналогичном формату 8.3 MS-DOS. Каждое полное имя представлено в форме имя.расширение, где и имя, и расширение состоит только из заглавных латинских букв и цифр. Имя всегда имеет от одного до восьми символов. Расширение имеет до трёх символов и может быть пусто. Если расширение пусто, разделяющая точка может быть опущена.

Каждое полное имя файла появляется во входном файле не более одного раза.

1 <= N <= 1000, 1 <= M <= 100.

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

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