Информатика

Дана строка, состоящая из M попарно различных символов. Вывести все перестановки символов данной строки.

Входные данные
В первой строке находится исходная строка. 2 <= M <= 8, символы - буквы латинского алфавита и цифры.

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

Даны 5 целых чисел. Среди них:
* если одинаковы 5, то вывести "Impossible", иначе
* если одинаковы 4, то вывести "Four of a Kind", иначе
* если одинаковы 3 и 2, то вывести "Full House", иначе
* если есть 5 последовательных, то вывести "Straight", иначе
* если одинаковы 3, то вывести "Three of a Kind", иначе
* если одинаковы 2 и 2, то вывести "Two Pairs", иначе
* если одинаковы 2, то вывести "One Pair", иначе
* вывести "Nothing".

Входные данные
В первой строке находятся 5 чисел через пробел. Все числа от 1 до 13 включительно.

Выходные данные
Выводится одна строка - результат анализа.

Для натуральных чисел a и n вычислить aⁿ.

Входные данные
В первой строке находятся разделённые пробелом a и n. 1 <= a <= 9, 1 <= n <= 7000.

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

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

Входные данные
В четырёх строках находятся пары чисел - координаты точек. Числа в первых трёх строках - это координаты вершин треугольника, в четвёртой строке - координаты тестируемой точки. Координаты вершин - целые числа, для любой точки выполняются следующие условия: -10 000 <= x, y <= 10 000.

Выходные данные
Вывести слово "In", если точка находится внутри треугольника, или "Out" - если снаружи.

Даны N целых чисел X₁, X₂, ..., X_N. Расставить между ними знаки "+" и "-" так, чтобы значение получившегося выражения было равно заданному целому S.

Входные данные
В первой строке находятся числа N и S. В следующей строке - N чисел через пробел. 2 <= N <= 24, 0 <= X_i <= 50 000 000, -1 000 000 000 <= S <= 1 000 000 000.

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

На окружности отметили N точек и пронумеровали их последовательно числами от 1 до N. Требуется найти количество различных простых ломаных с вершинами в некоторых из отмеченных точек и с концами в точках с номерами i и j.

Ломаная называется простой, если она не проходит дважды через одну точку (и не содержит самокасаний и самопересечений).

Входные данные
Вводятся три натуральных числа N, i, j (2 ≤ N ≤ 2 000, 1 ≤ i < j ≤ N).

Выходные данные
Требуется вывести остаток от деления количества ломаных на 10⁹.

В текстовом редакторе Microsoft Word имеется достаточно мощный механизм поиска и замены, который доступен после установки флажка Подстановочные знаки (Use wildcards). При этом некоторые символы в строке поиска получают особый смысл.

Так, знаком вопроса в шаблоне поиска можно задать ровно один любой символ. Кроме того, в шаблоне поиска на месте одного из символов в квадратных скобках можно перечислить сразу несколько символов, никак их при этом не разделяя (поиск будет считаться успешным, если на этом месте стоит один из символов, указанных в [ ]). В квадратных скобках можно вместо любого символа указывать и диапазоны символов. Мы будем использовать только три следующих диапазона: 0–9, a–z и A–Z (других диапазонов не будет). В этом случае будет искаться один любой символ из указанного диапазона (диапазонов). Если же первый символ в квадратных скобках – “!”, то, наоборот, искаться будет любой символ, из не перечисленных после восклицательного знака в квадратных скобках (например, [!.a-z,] означает один любой символ кроме точки, запятой, и строчных латинских букв). Если же искать надо один из специальных символов !, ?, [, ], (, ), –, \ то, как в квадратных скобках, так и без скобок перед таким символом ставится \.

Еще одно замечательное свойство строки поиска – выражения. Выражением считается часть строки поиска, взятая в круглые скобки. Пар скобок может быть до 9, но вложенность не допускается. В строке замены выражения представляются в виде \n, где n – порядковый номер выражения в шаблоне поиска (от 1 до 9). Например, по шаблону поиска (k)(?)t и шаблону замены t\2\1 произойдут например, следующие замены:
kot -> tok
kit -> tik

Таким образом, в строке замены существует только один специальный символ – \ , после которого обязательно должна идти цифра. Причем, например, цифра 5 может идти только если в строке поиска было не менее пяти выражений в скобках. При этом символы !, ?, [, ], (, ), – в строке замены указываются без предшествующего символа , а символ \ используется только перед цифрой и обозначает номер выражения. В качестве символа, который должен попасть в конечный текст, символ \ в строке замены не может быть использован.

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

Требуется по данному образцу поиска и образцу замены, произвести все замены в заданном тексте.

Входные данные
В первой строке входных данных расположен текст, в котором требуется произвести все необходимые замены. Длина текста не превышает 100 символов. Во второй строке записан шаблон для поиска. Шаблон является корректным: каждой открывающей скобке соответствует закрывающая, восклицательный знак как спецсимвол употребляется только сразу за символом [ и т.д. В третьей строке расположен шаблон для замены. Выражения в шаблоне для замены также корректны. Длины шаблонов не превышают 100 символов. Коды всех символов, встречающихся как в тексте, так и в шаблонах находятся в диапазоне от 32 до 126. Символы перевода строки в сами шаблоны и в текст не входят.

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

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

Входные данные
Вводятся два целых неотрицательных числа K и L – количество узлов и единичных отрезков сетки соответственно. Оба числа не превосходят 1000.

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

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

Входные данные
В первой строке входных данных содержится одно целое число N (1 ≤ N ≤ 50) – количество вершин в исходном графе. Далее в N строках записано по N неотрицательных целых чисел в каждой ( j -е число в i -й строке соответствует стоимости добавления ребра, соединяющего вершины i и j, 0 соответствует уже существующему ребру, положительное число – несуществующему), числа не превышают 100. Матрица симметрична.

Выходные данные
Вывести единственное число – минимально возможную стоимость дополнения данного графа до связного.

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

Входные данные
В первой строке входных данных содержится одно целое число N
 (1 ≤ N ≤ 50) – количество точек. Далее в N строках записано по 2 натуральных числа – координаты точек (координаты не превышают 100). Все точки различны. Далее дано число M – количество уже существующих отрезков. В следующих M строках записаны по 2 числа – номера начала и конца соответствующего отрезка.

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

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

Входные данные
В первой строке входных данных содержится одно целое число N (1 ≤ N ≤ 50) – количество вершин в исходном графе. Далее в N строках записано по N положительных целых чисел в каждой ( j -е число в i -й строке соответствует стоимости добавления ребра, соединяющего вершины i и j ), числа не превышают 100. В следующих N строках записаны по N чисел, каждое из которых является единицей или нулем (1, если вершины соединены, и 0, если не соединены). Обе матрицы симметричны.

Выходные данные
Вывести единственное число – минимально возможную стоимость дополнения данного графа до связного.

Том Сойер получил важное задание по покраске забора. Забор состоит из n досок. Он когда-то был покрашен, однако с некоторых участков забора краска облупилась. Эти доски Тому и необходимо покрасить. Так как забор большой, пришлось подвезти к забору целую цистерну с краской. Цистерна была помещена у края забора и не может перемещаться. У Тома есть ведерко, набрав краски в которое, Том может покрасить k
 досок забора. При этом Том может в любой момент вернуться за краской к цистерне.

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

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

Входные данные
Первая строка содержит количество досок в заборе n (1 ≤ n ≤ 10⁹) и вместимость ведерка k (1 ≤ k ≤ 100). Во второй строке содержится количество неокрашенных отрезков забора m (1 ≤ m ≤ 50).
Далее следуют m строк, в каждой из которых описан один неокрашенный отрезок. Отрезок описывается своей левой границей li и правой границей ri (1 ≤ l_i ≤ r_i ≤ n). Такое описание означает, что не покрашены l_i-я, (l_i+1)-я, …, (r_i–1)-я, r_i-я доски забора (доски нумеруются от 1 до n). Гарантируется, что неокрашенные отрезки, заданные во входном файле, не пересекаются.

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

Строительная компания хочет построить дом, в котором будет n квадратных комнат. Каждая комната характеризуется своим размером — длиной стены. Обозначим размеры комнат в новом доме как a₁, a₂, …, a_n.

При этом для того, чтобы квартиры в доме активнее распродавались, компания объявила его «Домом оригинальности и гармонии». Оригинальность означает, что размер любой комнаты не должен делиться на размер никакой другой комнаты. Свойство гармонии требует, чтобы площадь любой комнаты делилась на размер каждой из комнат. Иначе говоря, для любых различных i и j должны выполняться условия: ai не делится на a_j, а a_i² делится на a_j.

Требуется по заданному числу n выбрать такие размеры комнат, чтобы выполнялись свойства оригинальности и гармонии. При этом с целью экономии строительных материалов размер каждой комнаты не должен превышать 2⁶³ – 1.

Входные данные
Строка содержит число n (1 ≤ n ≤ 1000).

Выходные данные
Выведите размеры комнат — n положительных целых чисел, не превосходящих 2⁶³ – 1. Разделяйте числа пробелами.

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

Входные данные
В первой строке входных данных содержатся два натуральных числа: N (1 <= N <= 10000) - значение выражения и K (1 <= K <= 10000) - наибольшее число, которое разрешается использовать в выражении.

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

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

Компания Macrohard выпустила новую версию своего редактора Nottoobad, который понимает некоторые голосовые команды. К сожалению, этих команд всего две - "повторить последнее слово" и "стереть последний символ". Причем при исполнении команды "повторить последнее слово" редактор автоматически вставляет пробел, который разделяет слова.

Однако компания утверждает, что с помощью этого редактора можно набирать текст, нажимая клавиши на клавиатуре гораздо реже. Например, чтобы набрать фразу "this thin thing" достаточно нажать на клавиши на клавиатуре всего 6 раз:


Чтобы повысить популярность своего продукта, компания решила провести конкурс, победителем которого станет тот, кто сможет набрать заданный набор слов в редакторе за наименьшее количество нажатий на клавиши. Причем первое слово зафиксировано, а остальные могут быть набраны в произвольном порядке. То есть, если надо набрать слова "apple", "plum" и "apricote", то первым надо набрать "apple", а слова "plum" и "apricote" можно поменять местами.

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

Входные данные
В первой строке входных данных задано число N (1 <= N <= 100) – количество слов, которые предстоит набрать. Следующие N строк содержат слова – последовательности маленьких латинских букв, не длиннее 100 символов. Помните, что первое слово необходимо набрать первым!

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

При организации движения по сложным перекресткам, для того, чтобы траектории водителей, выполняющих различные маневры не пересекались, вводят ограничения на возможные маневры водителей, в зависимости от того, по какой полосе движения водитель подъехал к перекрестку. Для этого используется знак <<движение по полосам>>, на рисунке справа приведен пример такого знака, установленного перед одним из перекрестков в Санкт-Петербурге.

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

Пусть дорога содержит \(n\) полос для движения. Пронумеруем полосы от 1 до \(n\) слева направо, самая левая полоса получит номер 1, следующая номер 2, и т. д. Знак <<движение по полосам>> разрешает каждой из полос движение по некоторым из \(m\) возможных направлений. При этом должны выполняться следующие условия:

1. если с \(i\)-й полосы разрешено движение в \(a\)-м направлении, а с \(j\)-й полосы — в \(b\)-м направлении, причем \(i < j\), то \(a \le b\);

2. с каждой полосы разрешено движение хотя бы в одном направлении;

3. в каждом направлении разрешено движение хотя бы с одной полосы.

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

Формат входных данных
Строка содержит два целых числа: \(m\) и \(n\) (\(2 \le m \le 50\), \(1 \le n \le 15\)).

Формат выходных данных
Выведите одно число — количество возможных знаков <<движение по полосам>>, которые можно установить перед перекрестком.

В примере возможны следующие варианты знаков <<движение по полосам>>:

С клавиатуры подается два целых числа. Напишите программу, которая запрашивает ввод с клавиатуры данные числа и выводит их на экран.
 
Входные данные
Единственная строка входных данных содержит два натуральных числа через пробел. Значения не превышают 10⁹.

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

С клавиатуры подается одно целое число. Напишите программу, которая запрашивает ввод с клавиатуры данного числа и выводит его на экран.
 
Формат входных данных
Единственная строка входных данных содержит одно натуральные число. Значения не превышают 10⁹.

Формат выходных данных
Выведите на экран считанное число.


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

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

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

Входные данные
В первой строке вводится число n - количество селений (1 <= n  <= 100000). Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го селения. В третьей строке входных данных задается число m - количество бомбоубежищ (1 <= m <= 100000). Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го бомбоубежища. Все расстояния положительны и не превышают 10⁹. Селение и убежище могут располагаться в одной точке.

Выходные данные
Выведите n чисел - для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до m в том порядке, в котором они заданы во входных данных.