Алгоритмы

Примечание

 

Пример

№	Входные данные	Выходные данные
1	5 100 312 0 312 500	5 2 4 1 3

Входные данные
В первой строке задается число N - количество элементов массива (\(1<=N<=100000\)).
Далее идет N строк, по одному числу в строке - элементы массива.

Выходные данные 
Выведите на экран отсортированный массив в одну строку.
 

Примеры

№	Входные данные	Выходные данные
1	5 3 1 2 4 2	1 2 2 3 4

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

Всего на урок пришло N детей, изначально построившихся таким образом, что рост стоящего на позиции i равен hi (используется нумерация c 1). Можно считать, что все числа hi различны и лежат в диапазоне от 1 до N. Шеренга считается упорядоченной, если на первой позиции стоит школьник ростом один, на второй позиции стоит школьник ростом два и так далее.

Феоктист Всеволодович получает большое удовольствие от процесса упорядочивания школьни- ков, поэтому он всегда выбирает наиболее длинную последовательность обменов. С другой стороны, он не хочет чтобы ученики догадались о том, что он умышленно затягивает построение, поэтому никогда не делает заведомо бессмысленных обменов. А именно, преподаватель никогда не меняет местами школьников на позициях i и j, если hi < h_j . Очевидно, что данное ограничение делает процесс сортировки шеренги по росту конечным.

Староста Саша очень любит играть в волейбол и прекрасно понимает, что чем дольше препо- даватель будет расставлять всех по местам, тем меньше времени останется для игры. Ученики уже построились некоторым образом, а Феоктист Всеволодович вышел поговорить по телефону, так что Саша может успеть поменять местами ровно двух школьников, необязательно стоящих рядом в ше- ренге. Разумеется, он хочет сделать это таким образом, чтобы преподаватель как можно быстрее закончил упорядочивать шеренгу (Саша давно уже раскусил, как именно действует Феоктист Всево- лодович). С информатикой у старосты всегда были определённые проблемы, поэтому ему требуется ваша помощь.

Формат входных данных
В первой строке ввода содержится единственное число N — количество школьников на уроке (1 <= N <= 1 000 000). Во второй строке записано N различных целых чисел h_i (1 <= h_i <= N). i-е число соответствует росту школьника стоящего на i-й позиции.

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

Ввод	Вывод
5 2 4 3 5 1	2 5
4 1 2 3 4	-1 -1
10 2 3 7 1 5 10 4 6 9 8	3 7

GLaDOS приготовила для Челл новое, последнее испытание! В его рамках ей предстоит найти торт. Но всё не так-то просто — у неё отобрали портальную пушку и завязали глаза. Единственное, что Челл известно, — что она находится в прямоугольной комнате, выложенной квадратной плиткой, и что где-то в этой комнате расположен торт. Всё что остаётся делать Челл, — слепо переходить с плитки на плитку в поисках торта.

Кроме того, так как действие происходит в Лаборатории Исследования Природы Порталов, на каждой стене комнаты расположен портал, связанный с противоположной стеной. Формально: рас- смотрим комнату как прямоугольную сетку размера W × H и введем систему координат так, чтобы левая нижняя ячейка сетки имела координаты (0, 0), а правая верхняя — (W − 1, H − 1). За один шаг Челл может перейти в одну из четырёх соседних ячеек, причём попытка пройти сквозь стену приводит к тому, что Челл появляется с противоположной стороны комнаты. Например, шаг вниз из ячейки (x, 0) приведёт в ячейку (x, H −1), а шаг влево из ячейки (0, y) приведёт в ячейку (W −1, y).

Чтобы сделать испытание сложнее, GLaDOS не сообщила Челл ни размеры комнаты, ни коорди- наты её изначального положения, ни координаты торта. Более того, так как у Челл завязаны глаза, а портальная технология достигла совершенства в своём развитии, Челл даже не может определить, прошла ли она очередным ходом через портал или нет.

Челл может найти торт, только оказавшись в одной клетке с ним. Помогите ей пройти последнее испытание! Формат взаимодействия с тестирующей системой Это интерактивная задача. Ваша программа будет общаться с тестирующей системой по протоколу, описанному ниже. Вам разрешается произвести не более 200 000 ходов. Чтобы переместиться в соседнюю ячейку, выведите строку, содержащую ровно один символ, задающий направление перемещения: «U» — вверх; «D» — вниз; «L» — влево; «R» — вправо. Затем вы должны считать строку, в которой будет находиться ровно один символ, обозначающий результат перемещения: • «Y» — после произведённого хода Челл оказалась в клетке с тортом; • «N» — после произведённого хода Челл оказалась в клетке, не содержащей торт; • «E» — служебный символ, обозначающий, что после произведённого хода Челл всё ещё не нашла торт, а ваша программа превысила ограничение на количество ходов. Обратите внимание, после считывания символа «Y» или «E» вы обязательно должны сразу завершить вашу программу. В противном случае, вердикт тестирующей системы может быть некор- ректным! Гарантируется, что в клетке, в которой исходно находится Челл, нет торта. В точности соблюдайте формат выходных данных. После вывода каждой строки сбрасы- вайте буфер вывода — для этого используйте команды flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в C/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.

На протяжении многих лет Вася работает программистом в одной очень большой и очень из- вестной компании. Эта компания обеспечивает своих сотрудников всем необходимым для приятной и плодотворной работы: бесплатными обедами, транспортом от дома до места работы и многим, многим другим. И вот в один прекрасный солнечный день Вася понял, что ему очень наскучил вид из окна его офиса, и ему нужно, чтобы за окном было что-то новое и прекрасное. А что может быть лучше чудесного горного пейзажа? Придя к этой мысли, Вася попросил своего менеджера подобрать себе новый офис с красивым видом на горы.

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

Более формально, вид из окна офиса представляет собой набор горных цепей, пронумерованных от 1 до N, где горная цепь с номером i представляет собой ломаную на плоскости из li звеньев с вершинами в точках (x_i,j , y_i,j ), причем для любых i, j выполнено x_i,j < x_i,j+1.

Кроме этого, окно в офисе имеет фиксированную ширину, поэтому все горные цепи начинаются и заканчиваются на одной вертикали, то есть существуют такие числа A и B, что для любого номера i горной цепи выполнено x_i,0 = A, x_i,li = B.

Отметим, что из определения горной цепи следует, что для любого значения абсциссы A <= x <= B на ломаной с номером i существует единственная точка (x, yi(x)) с этим значением абсциссы, при- надлежащая этой ломаной. Будем говорить, что горная цепь i находится строго выше горной цепи j в точке x, если выполнено строгое неравенство y_i(x) > y_j (x).

Естественно считать, что цепь под номером i пересекается с цепью под номером j, если су- ществуют такие два значения абсциссы x1, x2, что цепь i находится строго выше цепи j в точке x1, но при этом цепь j находится строго выше цепи i в точке x2, то есть выполнены неравенства y_i(x₁) > y_j (x₁) и y_j (x₂) > y_i(x₂). Обратите внимание на поясняющие рисунки, расположенные в примечании к задаче.

Вам необходимо определить, подойдет ли подобранный офис Васе, и, если нет, то найти любую пару пересекающихся горных цепей.

Формат входных данных 
В первой строке входных данных через пробел идут два целых числа: A и B (−10⁹<=A < B<=10⁹ ).
Во второй строке входных данных находится единственное число N — количество горных цепей, видимых из окна подобранного менеджером Васи офиса (1 <= N <= 100 000).
Далее следуют описания N горных цепей. В первой строке i-го описания содержится число l_i => 1 — количество звеньев ломаной, из которых состоит соответствующая горная цепь. В следую- щих li + 1 строках описания содержатся два целых числа — координаты (x_i,j , y_i,j ) вершин ломаной (0 <= j <= l_i). Суммарное число звеньев всех ломаных не превосходит 200 000.
Гарантируется, что для каждой горной цепи вершины соответствующей ей ломаной идут во входных данных в порядке возрастания абсциссы, причем для любого i выполнено x_i,0 = A, x_i,li = B.

Формат выходных данных 
Если же офис подходит Васе, то есть никакие две горные цепи из входных данных не пересека- ются, в единственной строке выходных данных выведите слово "Yes" (без кавычек).
Иначе выведите в первой строке слово "No" (без кавычек), а на следующей строке выведите два числа — номера двух пересекающихся горных цепей. Горные цепи нумеруются согласно их появлению во входных данных, начиная с 1.

Примеры

Ввод	Вывод
-3 3 2 1 -3 2 3 1 2 -3 2 0 4 3 2	Yes
0 4 2 3 0 3 1 3 3 1 4 1 1 0 2 4 2	No 1 2

Замечание

Напоминаем, что абсциссой точки называется её x-координата, а ординатой — её y-координата. В первом примере хотя ломаные и касаются друг друга в точке (−3, 2), но, согласно данному выше определению, они не пересекаются. Во втором примере в точке x₁ = 1 одна ломаная выше другой, а в точке x₂ = 3 — наоборот, то есть горные цепи пересекаются.

 

Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки «+», «–», «*» и «/»). На вход подается символьная строка, представляющая собой арифметическое выражение. Все числа целые. Операция «/» выполняется как целочисленное деление 
 

Примеры

№	Входные данные	Выходные данные
1	12*3+45	81
2	12-45/3	-3

Какая система счисления используется в компьютерной технике?

1. двоичная
2. унарная
3. шестнадцатеричная
4. десятичная

Вдохновившись исследованием британских учёных о восприятии человеком текста, Вася решил, что современная письменность нуждается в серьёзном упрощении. В частности, в лексиконе Васи все слова состоят только из букв a, b и c. Кроме того, память у Васи плохая, поэтому Вася помнит лишь слова, которые содержат не более L букв.

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

Британские учёные очень заинтересовались исследованиями Васи. Они вступили с молодым учё- ным в активную переписку, однако, получив очередное Васино сообщение были несколько озадачены тем, что же он имел ввиду. Так как разобраться они так и не смогли, а очередное революционное открытие уже было проанонсировано в СМИ, они решили как-то оценить уровень гениальности автора. Для этого они решили понять, а из какого минимального количества слов может состоять словарный запас Василия?

Формат входных данных
В первой строке входных данных содержится целое число L — максимальная длина слова, кото- рое может содержаться в лексиконе Васи (1 <= L <= 10 000). В следующей строке содержится непустое сообщение, полученное учеными. Длина сообщения не превосходит 20 000 символов.

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

Пример
Ввод:
3
ababaabab

Вывод:
2
aba
ab

Замечание
В первом примере из условия одним из возможных способов проинтерпретировать Васино сооб- щение является: ab aba ab ab.

Графическое изображение, показывающее соотношение каких-либо величин называется

1. графиком
2. таблицей
3. картинкой
4. диаграммой

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

Из-за свойств магии, определяющей работу порталов, каждый портал можно использовать только в одну сторону. Для каждой пары городов A и B известно, можно ли воспользоваться порталом для перемещения напрямую из A в B или из B в A.

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

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

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

Для получения этой информации король планирует запросить в министерстве транспорта соответствующий отчет. Король может запросить либо частичный, либо полный отчет. Содержимое отчета зависит от параметра L, для частичного отчета L = k + 1, для полного отчета L = 1.

Отчет содержит для каждого целого числа m, такого что m ≥ L, число таких пар городов A и B, для которых выполняются следующие условия:
- исходно магический портал позволяет перемещаться напрямую из города A в город B;
- если изменить направление перемещения этого магического портала на противоположное, чтобы он позволял напрямую перемещаться из города B в город A, то количество совершенных городов в королевстве станет равным m.

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

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

Формат входного файла
Первая строка входного файла содержит два целых числа: n — количество городов в королевстве (2 ≤ n ≤ 2000) и p, равное либо 0, если требуется вывести частичный отчет, либо 1, если требуется вывести полный отчет. Последующие n строк содержат по n символов, каждый из которых может быть «+», «–» или «.», и i-я из этих строк описывает магические порталы, соединяющие i-й город с другими городами.
В i-й строке j-й символ равен «+», если магический портал позволяет напрямую перемещаться из i-го города в j-й, равен «–», если магический портал позволяет напрямую перемещаться из j-го города в i-й, и равен «.», если i = j.
Формат выходного файла
Первая строка выходного файла должна содержать одно целое число k — количество совершенных городов в королевстве.
Если требуется частичный отчет (p = 0), то вторая строка выходного файла должна содержать (n – k) целых неотрицательных чисел, разделенных пробелами, где i-е из этих чисел должно быть равно количеству пар городов, изменение направления портала между которыми на противоположное приводит к тому, что количество совершенных городов в королевстве станет равным (k + i). Если при этом k = n, то вторая строка может отсутствовать, либо быть пустой.
Если требуется полный отчет (p = 1), то вторая строка должна содержать n целых неотрицательных чисел, разделенных пробелами, где i-е из этих чисел должно быть равно количеству пар городов, изменение направления портала между которыми на противоположное приводит к тому, что количество совершенных городов в королевстве станет равным i.

Пример:

Ввод	Вывод
5 0 .-+++ +.+++ --.+- ---.+ --+-.	1 0 0 0 3
5 1 .-+++ +.+++ --.+- ---.+ --+-.	1 7 0 0 0 3

Пояснение к примерам

В приведенных примерах изначально совершенным является только город 2.
Изменив направление порталов, соединяющих пары городов (2, 3), (2, 4) или (2, 5), можно сделать все города совершенными. Изменение направление любого другого портала делает совершенным один город.

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

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т.д.

Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2M-й, 3M-й день, и т.д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A + B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

Фермер Николай хочет понять, за сколько дней лесорубы срубят все деревья, и он сможет засеять кукурузное поле. Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

Входные данные: на вход подаётся пять целых чисел, разделенных пробелами: A, K, B, M и X (\(1 <= A,\ B <= 10^9\) , \(2 <= K,\ M <= 10^{18}\), \(1 <= X <= 10^{18}\)).

Входные данные: выведите одно целое число — искомое количество дней.
 

Примеры

№	Входные данные	Выходные данные
1	2 4 3 3 25	7

Пояснение к примеру
В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим образом:
- 1-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 5 деревьев;
- 2-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 10 деревьев;
- 3-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 12 деревьев;
- 4-й день: Дмитрий отдыхает, Федор срубает 3 дерева, итого 15 деревьев;
- 5-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 20 деревьев;
- 6-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 22 дерева;
- 7-й день: Дмитрий срубает 2 дерева, Федор срубает оставшееся 1 дерево, итого все 25 деревьев срублены.
 

Введите с клавиатуры целое число X (|X| ≤ 10⁹).
В первых трех строках выведите это число на экран в двоичной, восьмеричной, 16-ричной системах счисления.
В следующих двух строках выведите, поместится ли это число в ячейке типа byte и ячейке типа short ("YES"/"NO").
Запрещается использовать циклы и знания о том, сколько именно байт/бит памяти занимают переменные типа int, byte, short.
Пример ввода:

123

 
Пример вывода:

1111011 173 7B YES YES

 
Пример ввода:

40000

 
Пример вывода:

1001110001000000 116100 9C40 NO NO

Постфиксная запись представляет собой такую запись алгебраического выражения, в которой сначала записываются операнды, а затем – знак операции. Например, для выражения a + b * c постфиксная запись будет a b c * +.

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


Входные данные
На вход подается символьная строка. Знак / в записи означает целочисленное деление.

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

Примеры

№	Входные данные	Выходные данные
1	5 3 + 7 4 - *	24

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

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

Примеры тестов

Примечание

Вам дано три числа a, b и c. Вы должны в таком порядке приписать эти числа друг к другу, чтобы в результате получилось минимальное число. Например, если a = 12, b = 5, c = 3, приписыванием можно получить числа 1253, 1235, 3125, 3512, 5123, 5312. Минимальным, среди этих чисел является 1235.

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

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

Примеры тестов

В интеллектуальном шоу «Твоя игра» принимают участие 3 человека. Им даются 5 тем, каждая из которых содержит по 5 вопросов стоимостью 100, 200, 300, 400 и 500 баллов. Если игрок правильно отвечает на вопрос, то к его текущей сумме прибавляется стоимость вопроса, если же он допускает ошибку, то от его суммы стоимость вопроса отнимается. При этом у игрока может оказаться отрицательная сумма баллов.

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

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

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

В следующих строках содержится информация о сыгранном вопросе. Сперва идёт имя участника, отвечавшего на вопрос, а через пробел — полученная им сумма баллов. Если количество баллов положительно, то ответ оказался правильным, если же отрицательно, то игрок ошибся. Гарантируется, что разыгранное количество вопросов каждой стоимости (100, 200, 300, 400 и 500) не превосходит 5. Также гарантируется, что во время игры будет разыгран хотя бы один вопрос.

В последней строке находится надпись «GAME OVER», означающая, что игра окончена и больше вопросов не будет.

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

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

Ввод:

Напишите функцию, вычисляющую количество делителей числа

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, выводит на экран число с максимальным количеством делителей
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100),
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно  число, в котором количество делителей максимально среди всех чисел, если таких чисел несколько, то необходимо вывести число, которое встретилось в последовательности раньше

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).

Пример

Ввод	Вывод
5 22790 94 66 18 18	22790
2 21 46	21

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