Информатика

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

Входные данные
В первой строке находится число N. В следующих N строках находятся пары чисел - координаты точек. Если соединить точки в данном порядке, а также первую и последнюю точки, получится заданный многоугольник. 3 <= N <= 50 000, координаты вершин целые и по модулю не превосходят 20 000.

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

N  гангстеров собираются в ресторан. i-й гангстер приходит в момент времени T и имеет богатство P_i. Дверь ресторана имеет K + 1 степень открытости, они обозначаются целыми числами из интервала [0, K]. Степень открытости двери может изменяться на единицу в единицу времени, то есть дверь может открыться на единицу, закрыться на единицу или остаться в том же состоянии. В начальный момент времени дверь закрыта (степень открытости 0). i-й гангстер заходит в ресторан, только если дверь открыта специально для него, то есть когда степень открытости двери соответствует его полноте S_i. Если в момент, когда гангстер подходит к ресторану, степень открытости двери не соответствует его полноте, он уходит и больше не возвращается. Ресторан работает в интервале времени [0, T]. Требуется собрать гангстеров с максимальным суммарным богатством в ресторане, открывая и закрывая дверь соответствующим образом.

Входные данные
В первой строке находятся числа N, K, T, во второй - T₁, T₂, ..., T_N, в третьей - P₁, P₂, ..., P_N. в четвёртой - S₁, S₂, ..., S_N. Числа в строках разделены пробелами. 1 <= N <= 100, 1 <= K <= 100, 1 <= T <= 30 000, 0 <= T_i <= T, 1 <= P_i <= 300, 1 <= S_i <= K, все числа целые.

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

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

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

Выходные данные
В каждой строке выводится одно из представлений. В сумме слагаемые разделяются знаком "+".

Число называется совершенным, если оно равно сумме всех своих делителей, меньших его самого. Требуется найти все совершенные числа от M до N.

Входные данные
В первой строке находятся разделённые пробелом числа M и N. M и N целые, 1 <= M <= N <= 10⁹, (N - M) * sqrt(N) <= 10⁷.

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

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

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

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

Даны целые неотрицательные числа M и N. Найти M*N.

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

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

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

Входные данные
В первой строке находятся размеры открытки, во второй - размеры конверта. Pазмеры открытки и конверта - целые положительные числа, не превосходящие 100.

Выходные данные
Если открытку можно вложить в конверт, вывести "Possible", если нет - вывести "Impossible".

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

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

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

Вывести квадрат, состоящий из 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. Матрица симметрична.

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