Перебор

Рассмотрим все представления числа \(n\) в виде суммы различных целых возрастающих слагаемых: \(n = a_1 + a_2 + \ldots + a_k\), \(a_1 < a_2 < \ldots < a_k\).

Будем называть такое разбиение быстро возрастающим, если для него выполнено следующее условие: для любых трех подряд идущих слагаемых разница между большим и средним строго больше, чем между средним и меньшим, иначе говоря, \(a_{i+2} - a_{i+1} > a_{i+1} - a_i\).

Задано число \(n\). Выведите все его быстро возрастающие разбиения на слагаемые.

Формат входных данных
На ввод подается целое число \(n\) (\(1 \le n \le 100\)).

Формат выходных данных

Выведите все быстро возрастающие разбиения на слагаемые числа \(n\). Разбиения можно выводить в любом порядке. Выводите слагаемые в каждом разбиении, разделяя их знаком <<+>> без пробелов.

Будем назвать натуральное число интересным, если в его десятичной записи первая цифра совпадает с последней.

Дано число \(n\). Найдите количество интересных чисел, не превышающих \(n\).

Формат входных данных
На ввод подается целое число \(n\) (\(1 \le n \le 10^{18}\)).

Обратите внимание, что для считывания этого числа вам может понадобиться 64-битный тип данных (<<long long>> в C++, <<long>> в Java, <<int64>> в Паскале).

Формат выходных данных
Выведите одно целое число — количество интересных натуральных чисел, не превышающих \(n\).

Будем называть пару различных целых чисел похожими, если у них \(k\) последних цифр совпадает.

Дано число \(n\), найдите количество пар различных похожих чисел, состоящих из \(n\) цифр. Ведущие нули запрещены. Пары \((a, b)\) и \((b, a)\) считаются одинаковыми.

Формат входных данных
На первой строке находится целое число \(n\) (\(1 \le n \le 10\)).

На второй строке находится целое число \(k\) (\(1 \le k \le n\)).

Формат выходных данных
Выведите одно число — количество пар похожих чисел, состоящих из \(n\) цифр.

В городе П для подготовки к празднику решили украсить аллею. Для этого наняли две бригады, одна отвечает за освещение аллеи, а вторая "— за озеленение аллеи, закупку саженцев сосны.

Аллею можно представить как прямую, и её решили украсить следующим образом — начать с сосны, чередовать лампы и сосны. В итоге на аллее будет высажено \(n + 1\) сосен и установлено \(n\) ламп.

Лампы поставили почти сразу же, причём двух типов — <<A>> и <<B>>. Лампы типа <<B>> светят всегда белым светом, а цвет лампы типа <<A>> зависит от её окружения. Если дерево, которое стоит слева от лампы, выше, чем дерево, которое стоит справа от лампы, то она загорается красным цветом, иначе синим.

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

Помогите ответственным за деревья разместить все \(n + 1\) саженцев так, чтобы разница между количеством красных и синих ламп была минимальна. Формально, если после высадки сосен будет \(r\) красных и \(b\) синих ламп, необходимо минимизировать величину \(|r-b|\).

Формат входных данных
В первой строке вводится одно единственное число \(n\) — количество ламп (\(1 \leq n \leq 2 \cdot 10^5\)). Во второй строке вводится \(n\) символов, \(i\)-й из которых равен <<A>> или <<B>> — тип \(i\)-й лампы.

Формат выходных данных
Выведите \(n + 1\) различных чисел от \(1\) до \(n + 1\) — высоты сосен при оптимальном размещении. Если оптимальных ответов несколько, можно вывести любой из них.

Иллюстрация ко второму примеру

Для наглядности, на иллюстрации красные лампы имеют формулу пятиугольника, а синие имеют форму звезды.

Тогда \(r = 1\), \(b = 1\), \(|r - b| = 0\) и это размещение будет одним из оптимальных.

Бригада скорой помощи выехала по вызову в один из отделенных районов. К сожалению, когда диспетчер получил вызов, он успел записать только адрес дома и номер квартиры K₁, а затем связь прервалась. Однако он вспомнил, что по этому же адресу дома некоторое время назад скорая помощь выезжала в квартиру K₂, которая расположена в подъезда P₂ на этаже N₂. Известно, что в доме M этажей и количество квартир на каждой лестничной площадке одинаково. Напишите программу, которая вычилсяет номер подъезда P₁ и номер этажа N₁ квартиры K₁.

Входные данные
Во входном файле записаны пять положительных целых чисел K₁, M, K₂, P₂, N₂. Все числа не превосходят 1000.

Выходные данные
Выведите два числа P₁ и N₁. Если входные данные не позволяют однозначно определить P₁ или N₁, вместо соответствующего числа напечатайте 0. Если входные данные противоречивы, напечатайте два числа –1 (минус один).

В связи с проведением межпланетного шашечного турнира было принято решение о строительстве орбитальной гостиницы. Она должна была представлять собой большой куб из N×N×N блоков – маленьких кубиков 1×1×1, и каждый блок должен был быть окрашен снаружи со всех сторон в какой-то один цвет. При этом некоторые блоки могли быть покрашены в один и тот же цвет.

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

Итак, вам необходимо по видам гостиницы (куба N×N×N, из которого, возможно, выкинуты некоторые кубики 1×1×1) с 6 сторон определить, из какого максимального количества блоков 1×1×1 она может состоять. Может оказаться так, что гостиница состоит из двух или более не связанных между собой частей.

Входные данные
В первой строке входного файла находится число N — размер гостиницы (1≤N≤10). На следующих N строках записаны виды гостиницы с 6 сторон (в следующем порядке: спереди, слева, сзади, справа, сверху, снизу). Каждый такой вид представляет собой таблицу N×N, в которой различными заглавными латинскими буквами обозначены различные цвета, а символом «.» (точка) — то, что в этом месте можно будет смотреть прямо сквозь гостиницу. Два последовательных вида отделяются друг от друга ровно одним пробелом в каждой из N строк.

Нижняя граница вида сверху соответствует верхней границе вида спереди, а верхняя граница вида снизу — нижней границе вида спереди. Для видов спереди, сзади и с боков верх и низ вида соответствуют верху и низу гостиницы.

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

Выходные данные
Выведите в выходной файл одно число — искомое максимальное количество оставшихся блоков в гостинице.

Склад конторы MacroHard представляет собой прямоугольную комнату размером NxM. На складе нарисована разметка, состоящая из линий, параллельных стенам склада, которые разбивают его на NxM квадратов 1x1.

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

Размещать изделия на складе разрешается только так, чтобы хотя бы одна сторона изделия была параллельна какой-то из стен склада, и, вдобавок, все углы изделия находились в точках пересечения линий разметки склада. Рисунки 1,2,3 иллюстрируют неправильное положение изделий, а 4,5 –



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

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

Входные данные
В первой строке входного файла записаны три целых числа: N, M (размеры склада) и K (количество изделий, которые уже находятся на складе). Следующие K строк содержат по 6 целых чисел — координаты углов соответствующего изделия. Система координат введена так, что оси координат параллельны стенам склада и при этом один из углов склада имеет координаты (0,0), а противоположный — (N,M).

Ограничения

1<=N<=4, 1<=M<=4

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

Однажды Юрик оказался в лесу у костра, где собрались \(n\) человек. Оказалось, что некоторые из них знакомы друг с другом. Для удобства пронумеруем людей целыми числами от \(1\) до \(n\). Обозначим как \(d_i\) количество людей, сидящих у костра, с которыми знаком \(i\)-й человек. Неожиданно оказалось, что два человека с номерами \(i\) и \(j\) (\(i \ne j\)) знакомы друг с другом тогда и только тогда, когда \(d_i = d_j\).

Вернувшись домой, Юрик задумался, какое минимальное количество пар людей могли быть знакомы, чтобы выполнялось это условие?

Формат входных данных
Единственная строка содержит одно целое число \(n\) (\(1 \le n \le 5\,000\)) — количество людей.

Формат выходных данных
Выведите одно целое число — минимальное количество пар знакомых людей.

Рассмотрим первый пример из условия. Возможны следующие варианты:

1. Любые два человека знакомы друг с другом. В этом случае количество пар знакомых людей равно \(\frac{4 \cdot 3}{2} = 6\).

2. Некоторые три человека попарно знакомы друг с другом, четвертый человек не знаком ни с кем. В этом случае количество пар знакомых людей равно \(3\).

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

Информация, записанная на билете, кодируется K числами (0 или 1). При этом непосредственно на билете записывается последовательность из N чисел (N>=K) так, что числа, записанные на расстоянии K, совпадают. Таким образом, для проверки подлинности билета достаточно проверить, что все числа на расстоянии K совпадают. К сожалению, при считывании информации с билета иногда могут происходить ошибки — считается, что одно из чисел может исказиться (то есть 0 заменится на 1, или 1 — на 0). Такой билет все равно нужно считать подлинным. Во всех остальных случаях билет считается поддельным.

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

Входные данные
В первой строке входного файла записаны числа N и K (1<=N<=50000, 1<=K<=1000, K<=N). Во второй строке записано N чисел, каждое из которых является 0 или 1 — информация, считанная с билета.

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

Парламент некоторой страны принял новый закон о праздничных днях. Согласно этому закону первые K дней года, а также 23 февраля (День олимпиады по информатике) и 8 марта объявляются праздничными, а все остальные праздники отменяются. При этом все выходные (суббота и воскресенье), попавшие на праздничные дни, переносятся на следующие за этими праздниками рабочие дни.

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

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

Входные данные
На вход подается единственное число K (1≤K≤50).

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

На шахматной доске (размером 8 × 8 клеток) стоит несколько ферзей. За один ход разрешается взять одной фигурой другую (цвет фигур значения не имеет; ходы без взятия делать нельзя). Требуется найти последовательность ходов: за каждый ход один из ферзей может взять другого ферзя. В результате доске должна остаться одна фигура. После каждого хода количество ферзей на поле должно уменьшиться.
Ферзь ходит по горизонтали, вертикали или диагонали на любое число клеток. Он не может перепрыгивать через другие фигуры.

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

Выходные данные
В выходной файл выведите возможную последовательность в следующем формате. Для каждого хода указывается сначала клетка, с которой делается ход, затем двоеточие, затем клетка, на которую делается ход. Клетка задается столбцом и строкой: столбцы нумеруются слева направо строчными латинскими буквами a, b, c, d, e, f, g, h; строки — снизу вверх цифрами 1, 2, 3, 4, 5, 6, 7, 8.
Если решений несколько, приведите любое из них. Если решений нет, выведите NO SOLUTION

На склад, который имеет форму прямоугольного параллелепипеда, привезли ноутбуки, упакованные в коробки. Каждая коробка также имеет форму прямоугольного параллелепипеда.

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

Стороны коробок должны быть параллельны сторонам склада

Коробку при помещении на склад разрешается расположить где угодно (с выполнением предыдущего условия), в том числе на другой коробке, но все коробки должны быть ориентированы одинаково (т.е. нельзя одну коробку расположить «стоя», а другую – «лежа»)

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

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

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

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

Входные данные
Вводятся 6 чисел (от 0 до 3) – требуемое количество крестиков в первом, втором, третьем столбце, в первой, второй, третьей строке.

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

На базаре есть ряд из 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.

Дан набор переменных x₁, x₂, ..., x_N. Каждая переменная x_i может принимать значение только -1, 0 или +1. Для данного целого числа S требуется определить количество способов присвоить переменным xi значения так, чтобы сумма всех возможных произведений x_i * x_j была равна S, где i < j и i, j = 1, 2, ..., N. Два способа считаются различными, если они содержат различное число x_i = 0.

Ограничения: 2 <= N <= 10 000, -10 000 < S < 10 000.

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

Выходные данные
Вывести одно целое число - количество способов представить S как сумму произведений.

Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке (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, состоящие из круглых и квадратных скобок.

Входные данные
В первой строке находится единственное число N. 1 <= N <= 14, N - чётное.

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

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

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

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

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

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

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