Информатика

Вывести квадрат, состоящий из N*N клеток, заполненных числами от 1 до N² по спирали (см. примеры).

Входные данные
В первой строке находится единственное число N. 2 <= N <= 100.

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

Даны два целых неотрицательных числа: M и N. Найти их сумму.

Входные данные
В первой строке содержится M, во второй - N. 0 <= M, N < 10³⁰⁰⁰⁰.

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

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

Входные данные
В первой строке содержатся координаты первого конца первого отрезка, во второй - второго конца первого отрезка, в третьей и четвёртой - координаты концов второго отрезка. Kоординаты целые и по модулю не превосходят 10 000.

Выходные данные
Выводится слово "Yes", если общая точка есть, или слово "No" - в противном случае.

В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.

Входные данные
В первой строке находится число N. В следующих N строках содержатся по N цифр без пробелов. 2 <= N <= 250.

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

Дана строка, состоящая из 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", если можно, то вывести равенство. Если решение не единственное, вывести любое.

В текстовом редакторе 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. Разделяйте числа пробелами.

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

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


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

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

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

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

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

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

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

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

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



Для задания конфигурации головоломки удобно рассмотреть ее развертку - "разрезать" поверхность цилиндра вдоль вертикальной линии, проходящей по границам квадратиков, и обозначить черные клетки символом "1", а белые - символом "0". Пусть, например, одна из возможных разверток головоломки, приведенной на рисунке, следующая (на рисунке видно только первые три столбца этой развертки):
        000110 001110 101000 001000 011111 011110
Задача решающего головоломку состоит в том, чтобы, поворачивая слои, добиться того, чтобы все вертикальные столбцы были различны. Например, головоломка приведенная выше, не решена, поскольку два из ее столбцов (четвертый и пятый на приведенной развертке) одинаковы. Если же повернуть нижний слой влево на один квадратик, развертка головоломки примет следующий вид:
        000110 001110 101000 001000 011111 111100
Теперь все столбцы различны и, следовательно, головоломка решена.

Для того, чтобы решать головоломку было интереснее, на ее раскраску наложено дополнительное условие: нельзя повернуть один из слоев головоломки меньше, чем на полный оборот таким образом, что внешний вид головоломки останется тем же. Так, например, для n  = 6 слой с раскраской "010101" не разрешается, поскольку при его повороте на 2 квадратика внешний вид головоломки не меняется.

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


Входные данные
В первой строке вводится число n  - количество слоев в головоломке и количество квадратиков в одном слое (1 <= n  <= 200). Следующие n
 строк содержат по n  символов, каждый из которых равен 0 или 1 - развертку головоломки.

Выходные данные
Если решить головоломку можно, в первой строке выведите слово "Yes". В этом случае следующие n  строк должны содержать произвольную развертку решенной головоломки.

Если решить головоломку нельзя, выведите в первой и единственной строке выходных данных слово "No".

 

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

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

Входные данные
В первой строке вводятся число n - количество ключевых слов в языке (0 <= n <= 50) и два слова C и D, каждое из которых равно либо "yes", либо "no". Слово C равно "yes", если идентификаторы и ключевые слова в языке чувствительны к регистру символов, и "no", если нет. Слово D равно "yes", если идентификаторы в языке могут начинаться с цифры, и "no", если нет.

Следующие n строк содержат по одному слову, состоящему из букв латинского алфавита и символов подчеркивания - ключевые слова. Все ключевые слова непусты, различны, при этом, если язык не чувствителен к регистру, то различны и без учета регистра. Длина каждого ключевого слова не превышает 50 символов.

Далее до конца входных данных идет текст программы. Он содержит только символы с ASCII-кодами от 32 до 126 и переводы строки.

Размер входных данных не превышает 10 килобайт. В программе есть хотя бы один идентификатор.

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