Информатика

Переведите число {1} из 10-й СС в двоичную СС
 

Переведите число  {1}16  в десятичную систему счисления.

Даны две строки \(S\) и \(T\) из строчных букв английского алфавита.

Посмотрим на следующий процесс. Рассмотрим не более одного раза каждый символ, хотя бы где-то входящий в первую строку. После чего, для рассматриваемого символа \(x\) определим другой символ \(p(x) \neq x\) и заменим некоторые вхождения \(x\) в \(S\) на \(p(x)\). Определите, возможно ли в ходе такого процесса получить из строки \(S\) строку \(T\). При этом разные символы можно заменять на один и тот же символ или на символ, который заменяться не будет.

Например, пусть \(S =\) <<aabab>>, \(T =\) <<abbbc>>. Из \(S\) можно получить \(T\), если выбрать p(‘a’) = ‘b’, p(‘b’) = ‘c’ и заменить второе и третье вхождение ‘a’ на p(‘a’), второе вхождение ‘b’ на p(‘b’).

А если \(S =\) <<aabaс>>, \(T =\) <<bbbbb>>, то все вхождения ’a’ и ’c’ были заменены на ’b’.

Формат входных данных
В первой строке вам дано число \(n\) \((1 \leqslant n \leqslant 200\,000)\). Во второй строке задана \(S\). В третьей строке задана \(T\). Обе строки имеют длину \(n\) и состоят только из букв от ‘a’ до ‘z’.

Формат выходных данных
Если возможно осуществить описанный процесс так, чтобы из \(S\) получилась \(T\), выведите <<YES>>, на следующей строке выведите \(m\) – количество различных символов \(S\), которые хотя бы раз заменялись. Обозначим эти символы за \(c_1,\ c_2,\ \ldots \ c_m\). После чего выведите \(m\) строк. На \(i\)-й строке необходимо вывести символы \(c_i\) и \(p(c_i)\) через пробел. Если это сделать невозможно, выведите <<NO>>.

В развлекательном центре Е-города был установлен игровой автомат нового поколения. В автомат можно бросить монету и следить за её продвижением сверху вниз по разветвляющемуся лабиринту из трубок. В лабиринте есть \(n\) узлов, которые пронумерованы числами от 1 до \(n\). При бросании монета попадает в первый узел. Каждый узел лабиринта, кроме первого, имеет одну входящую сверху трубку, по которой монета может в него попасть. Из каждого узла выходит не более двух трубок, идущих вниз, одна из которых ведет налево, а другая "— направо. Каждая трубка имеет некоторую ширину. Монета проваливается в более широкую трубку, а в случае равенства ширины трубок "— в левую.

После прохождения монеты по трубке ширина этой трубки уменьшается на 1. Монета не может пройти по трубке ширины 0. Если монета достигла узла, из которого она не может дальше двигаться вниз, автомат останавливается и ждёт, когда в него бросят следующую монету.

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

Панкрату понравилась игрушка, которая находится в узле с номером \(v\).

Требуется написать программу, которая определяет, сколько монет должен бросить в автомат Панкрат, чтобы получить игрушку из узла \(v\).

Формат входных данных
В первой строке задано число \(n\) — количество узлов в лабиринте. В последующих \(n\) строках заданы описания всех узлов, в \(k\)-й из этих строк описан узел с номером \(k\).

Описание \(k\)-го узла состоит из четырех целых чисел: \(a_k\), \(u_k\), \(b_k\), \(w_k\). Если из \(k\)-го узла выходит левая трубка, то \(a_k\) — номер узла, в который она ведет (\(k < a_k \leqslant n\)), а \(u_k\) — её ширина. Если левой трубки нет, то \(a_k = u_k = 0\). Если из \(k\)-го узла выходит правая трубка, то \(b_k\) — номер узла, в который она ведет (\(k < b_k \leqslant n\)), а \(w_k\) — её ширина. Если правой трубки нет, то \(b_k = w_k = 0\).

В последней строке задано целое число \(v\) (\(1 \leqslant v \leqslant n\)) — номер узла, в котором находится игрушка, понравившаяся Панкрату.

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

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

 

В первом примере первая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 1, 3 и 4:

Вторая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 2 и 6:

Третья монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 5 и 7:

Вадим работает в ЖКХ и сегодня он крайне озабочен вопросов сосулек. А именно он наблюдает за домом по адресу — проспект Программистов, дом 404. В доме \(n\) этажей, на каждом этаже по \(m\) окон, включая первый. Окна на каждом этаже пронумерованы слева направо от \(1\) до \(m\). \(i\)-e окно \(j\)-го этажа находится ровно под \(i\)-м окном \(j + 1\)-го этажа. Под некоторыми окнами свисают сосульки.

Вадим руководит установкой на дом козырька, который будет установлен ниже первого этажа и проходить под \(d\) окнами. То есть, если начало козырька находится под окном с номером \(i\), то он проходит под всеми окнами с номерами от \(i\) до \(i + d - 1\). Вадим хочет выбрать такую позицию для козырька, чтобы над ним находилось наименьшее возможное количество сосулек и из всех подходящих вариантов выбрать такой, что начало козырька будет находиться как можно левее.

Помогите Вадиму выбрать нужное окно.

Формат входных данных
В первой строке содержатся числа \(n\), \(m\), \(d\), \(k\) — количество этажей, количество окон на каждом этаже, длина козырька и количество окон, под которыми есть сосульки, соответственно (\(1 \le n, m \le 100\),\(1 \le d \le m\), \(0 \le k \le n \cdot m\)).

В следующих \(k\) строках заданы тройки чисел \(x\), \(y\), \(z\) — номер этажа, номер окна на этаже и количество сосулек под ним (\(1 \le x \le n\), \(1 \le y \le m\), \(1 \le z \le 10\)).

Гарантируется, что каждая пара \(x\), \(y\) встречается не более одного раза.

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

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

Во втором примере козырек имеет длину один и если его поставить под окнами с номерами \(1\), \(2\) или \(3\), над ним будет соответственно \(1\), \(0\) или \(2\) сосульки.

В третьем примере возможны две позиции для козырька, но так как под окнами с \(1\)-м и \(3\)-м номерами одинаковое число сосулек, а окна с номерами \(2\) будут над козырьком в любом случае, выбираем наиболее левый вариант расположения.

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

Для некоторого числа \(m\) назовём \(m\)-разбиением массива такое его разбиение на непересекающиеся отрезки, что на каждом из этих отрезков медиана больше либо равна \(m\). Вам дан массив \(a\) длины \(n\) и \(q\) запросов двух видов:

1. присвоить элементу с индексом \(i\) значение \(x\);

2. найти наибольшее число \(k\) такое, что для подотрезка массива с индексами от \(l\) до \(r\) существует \(m\)-разбиение на \(k\) отрезков.

Формат входных данных
В первой строке дается число \(n\) (\(1 \le n \le 2 \cdot 10^5\)) - размер массива. В следующей строке вводятся \(n\) чисел \(a_{i}\) (\(1 \le a_{i} \le 10^9\)) - элементы массива, на следующей строке вводится число \(q\) (\(1 \le q \le 2 \cdot 10^5\)) - количество запросов. В следующих \(q\) строках даются запросы, каждый в одном из следующих форматов:

• \(1\) \(i\) \(x\) —  запрос 1 типа (\(1 \le i \le n, 1 \le x \le 10^9\));

• \(2\) \(m\) \(l\) \(r\) —  запрос 2 типа (\(1 \le m \le 10^9, 1 \le l \le r \le n\)).

Формат выходных данных
Для каждого запроса второго типа в отдельной строке выведите ответ на запрос. В случае если для отрезка не существует никакого \(m\)-разбиения, выведите \(0\).

В задаче присутствуют 6 групп:

1. \(n \le 5, q \le 5\), такие решения будут набирать не менее 10% баллов

2. \(n \le 100, q \le 100\), такие решения будут набирать не менее 20% баллов

3. \(n \le 10000, q \le 10000\), такие решения будут набирать не менее 30% баллов

4. \(m\) - одно и тоже для всех запросов, такие решения будут набирать не менее 25% баллов

5. нет запросов изменения, такие решения будут набирать не менее 35% баллов

6. Ограничения, как и в задаче

Есть шарики, пронумерованные от \(1\) до \(n\). Также поступают \(q\) запросов:

• \(add\) \(x\) - добавить в дек шарик с номером \(x\). Вы можете положить шарик либо сверху, либо снизу дека.

• \(del\) \(x\) - удалить из дека шарик с номером \(x\). Вы находите шарик с номером \(x\) в деке, достаете все шарики НИЖЕ \(x\), удаляете шарик \(x\), потом кладете достанные шарики (без \(x\)) обратно в том же порядке.

На запросы \(1\)-го типа вы тратите \(1\) действие, а на запросы \(2\)-го типа - \(2k + 1\) действий, где \(k\) - количество шариков, которые лежат ниже удаляемого (то есть вы сначала достаете \(k\) шариков, потом удаляете нижний, потом кладете достанные \(k\) шариков обратно в том же порядке).

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

Формат входных данных
Первая строка содержит числа \(n\) и \(q\) (\(1 \leq n, q \leq 2 \cdot 10^5\)) - максимальный номер шарика и количество запросов. Далее следуют \(q\) строк в формате:

• \(add\) \(x\) - добавить шарик с номером \(x\) (\(1 \leq x \leq n\)) в начало или конец дека.

• \(del\) \(x\) - удалить шарик с номером \(x\) (\(1 \leq x \leq n\)) из дека.

Гарантируется, что никакой шарик не добавляется 2 раза, а также, что если есть запрос удаления шарика \(x\), то он присутствует в деке в данный момент.

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

Замечание

В тесте 1 независимо от того, как вы добавите шарики, вы потратите 4 действия (на удаление и на добавление каждого из шариков).

В тесте 2 вам необходимо добавить шарик 5 вниз, шарик 8 вверх, шарик 1 вниз, шарик 4 вверх, тогда вы потратите ровно 6 действий.

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

На каждом уровне игры генерируется новый проспект из небоскребов, где каждая высотка задается уникальной положительной координатой относительно начала проспекта. После этого Похпид выбирает здание, с которого он начинает свой путь, при этом он может прыгать только на здание, координата которого больше текущей. Трудность этой игры заключается в том, что после каждого прыжка Похпид устает и уже не может прыгать также далеко как раньше. Формально говоря, на каждом уровне генерируется \(n\) зданий, координаты которых равны \(a_1, a_2, \ldots, a_n\). Игрок выбирает стартовый небоскреб и с него может прыгнуть на любое здание, которое находится правее, при этом длина первого прыжка может быть любой. Для всех последующих прыжков должно быть выполнено условие: если сейчас игрок находится на здании с координатой \(a_i\), а до этого был на позиции \(a_j\), то он может перепрыгнуть на здание с координатой \(a_k\), если \(a_i - a_j > a_k - a_i\).

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

Формат входных данных
В первой строке входных данных дается число уровней \(t\) \((1 \leq t \leq 1000)\).

В следующих строках каждый уровень задается числом зданий \(n\) \((1 \leq n \leq 5\,000)\) в одной строке и позициями этих зданий \(a_1, a_2, \ldots, a_n\) \((0 \leq a_i \leq 10 ^ {18}, \, a_i \neq a_j\) если \(i \neq j)\) в следующей строке. Гарантируется, что сумма \(n\) по всем уровням не превосходит \(30\,000\).

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

Решения, работающие при \(n \leq 10\) и \(t = 1\) будут получать не меньше 25% баллов.

Решения, работающие при \(n \leq 100\) и \(t \leq 10\) будут получать не меньше 50% баллов.

Решения, работающие при \(n \leq 2500\) и \(t \leq 10\) будут получать не меньше 75% баллов.

В первом примере оптимальный выбор небоскребов \(3, 5, 4, 1\) их координаты соответственно будут равны \(3, 6, 8, 9\).

Во втором примере ответы для уровней получаются выбором следующих 3 наборов индексов соответственно:
1) \(2, 1, 3\)
2) \(3, 2, 8, 7, 5\)
3) \(5, 1, 4, 2\)

Миша сидел на занятиях математики в Высшей школе экономики и решал следующую задачу: дано \(n\) целых чисел и нужно расставить между ними знаки \(+\) и \(\times\) так, чтобы результат полученного арифметического выражения был нечётным (например, между числами \(5\), \(7\), \(2\), можно расставить арифметические знаки следующим образом: \(5 \times 7 + 2 = 37\)). Так как примеры становились все больше и больше, а Миша срочно убегает в гости, от вас требуется написать программу решающую данную задачу.

Формат входных данных
В первой строке содержится единственное число \(n\) (\(2 \leq n \leq 10^5\)). Во второй строке содержится \(n\) целых чисел \(a_i\), разделённых пробелами (\(-10^9 \leq a_i \leq 10^9\)). Гарантируется, что решение существует.

Формат выходных данных
В одной строке выведите \(n - 1\) символ \(+\) или \(\times\), в результате применения которых получается нечётный результат. (Для вывода используйте соответственно знаки <<+>> (ASCII код—43) и <<x>> (ASCII код—120), без кавычек).

 

Определите, сколько раз выполнится тело цикла, а также последнее число, которое будет выведено на экран в процессе выполнения программы. В ответе запишите два числа через пробел: сначала сколько раз выполнится цикл, затем последнее выведенное число. Если программа ничего не выводит на экран, то в вместо второго числа напишите слово None.

var n: integer;
begin
  n := {1};
  while n >= {2} do
  begin
    writeln(n);
    n := n - {3};
  end;
end.

Определите, сколько раз выполнится тело цикла, а также последнее число, которое будет выведено на экран в процессе выполнения программы. В ответе запишите два числа через пробел: сначала сколько раз выполнится цикл, затем последнее выведенное число. Если программа ничего не выводит на экран, то в вместо второго числа напишите слово None.

var n: integer;
begin
  n := {1};
  while n < {2} do
  begin
    writeln(n);
    n := n + {3};
  end;
end.

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

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

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

Формат входных данных
В первой строке входных данных задается число N (1 ≤ N ≤ 50) — количество веревочек единичной длины, из которых состоит кусок сети. Следующие N строк содержат по две пары целых чисел — координаты концов веревочек. Каждая четверка чисел описывает отрезок единичной длины, параллельный одной из осей координат.

Координаты всех точек неотрицательны и не превосходят 50.

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

Примечание

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

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

Единственная строка входных данных содержит два натуральных числа через пробел. Значения чисел не превышают 10⁹.

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

Реализуйте структуру данных для эффективного вычисления номера максимального из нескольких подряд идущих элементов массива.

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

Во второй строке вводятся N чисел от 1 до 100000 — элементы массива.

В третьей строке вводится одно натуральное число K (\(1 <= K <= 30000\)) — количество запросов на вычисление максимума.

В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).

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

Числа выводите в одну строку через пробел.

У Саши есть блокнот, состоящий из \(n\) листочков, пронумерованных от 1 до \(n\). На \(i\)-м листочке написано целое число \(a_i\).

Аня собирается разорвать блокнот на \(k\) частей, для этого она выбирает \(k-1\) число \(1 \le r_1 < r_2 < \ldots < r_{k-1} < n\) и разрывает блокнот так, что листки с 1 по \(r_1\)-й оказываются в первой части, листки с \((r_1+1)\)-го по \(r_2\)-й оказываются во второй части, и т.д., последняя \(k\)-я часть содержит листки с \((r_{k-1}+1)\)-го по \(n\)-й.

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

Формат входных данных
Первая строка ввода содержит два числа: \(n\) и \(k\) (\(2 \le k \le n \le 300\)). Вторая строка содержит \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)).

Формат выходных данных
На первой строке выведите максимальное значение суммы, которое удастся достичь Ане. На второй строке выведите значения \(r_1, r_2, \ldots, r_{k-1}\), которые ей необходимо выбрать. Если вариантов разорвать блокнот, чтобы максимизировать искомую сумму несколько, выведите любой из них.

Примечание
В приведенном примере Аня разорвала блокнот на части \([1, 10, 2]\), \([8]\), \([9]\), \([3, 5, 4]\) и \([7, 6]\). Искомая сумма равна \(1 + 8 + 9 + 3 + 6 = 27\).

Недавно на кружке по математике Миша узнал про разбиения на слагаемые. Разбиением числа \(n\) на слагаемые называется представление его в виде суммы неубывающего набора натуральных чисел. Например, \(9=1+2+2+4\) является разбиением числа 9 на слагаемые.

Миша называет разбиение интересным, если никакие два слагаемых в наборе не равны и не отличаются ровно на 1. Так, например, разбиение, приведенное выше не является интересным, а разбиение \(9=1+3+5\) — является.

Помогите Мише вывести все интересные разбиения числа \(n\) на слагаемые.

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

Формат выходных данных
Выведите все интересные разбиения числа \(n\) на слагаемые. Разбиения можно выводить в любом порядке. Соблюдайте формат из примера.

Сеня решил написать операционную систему. Для начала он планирует написать подпрограмму, которая будет рисовать рамки окон.

Поле для рисования представляет собой прямоугольник \(h \times w\) пикселей, строки занумерованы сверху вниз от 1 до \(h\), столбцы — слева направо от 1 до \(w\).

На поле последовательно рисуются \(n\) рамок, \(i\)-я рамка представляет собой границы прямоугольника с противоположными углами в точках \((r_{i,1}, c_{i,1})\) и \((r_{i,2}, c_{i,2})\).

Требуется вывести получившееся изображение в виде \(h\) рядов по \(w\) символов, пискель, который не был использован при изображении рамок, следует вывести с использованием символа <<.>>, а пиксели \(i\)-й рамки с использованием \(i\)-го символа латинского алфавита (первая рамка изображается буквами <<a>>, вторая — <<b>>, и т.д.)

Формат входных данных
Первая строка содержит целые числа \(h\), \(w\) и \(n\) — размеры поля и число рамок (\(2 \le h, w \le 80\), \(1 \le n \le 26\)). Следующие \(n\) строк содержат по четыре целых числа каждая: \(r_{i,1}, c_{i,1}, r_{i,2}\) и \(c_{i,2}\) (\(1 \le r_{i,1} < r_{i,2} \le h\),. \(1 \le c_{i,1} < c_{i,2} \le w\)).

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

Маша и Петя решили выяснить, чья комната больше. Машина и Петина комнаты имеют форму прямоугольников, причем Машина комната имеет размеры \(a\) на \(b\) метров, а Петина — \(c\) на \(d\) метров.

Напишите программу, которая определит, чья комната больше: Машина или Петина.

Формат входных данных
На ввод подается четыре натуральных числа, разделенных пробелами: \(a\), \(b\), \(c\) и \(d\) (\(1 \le a, b, c, d \le 1000\)).

Формат выходных данных
Если Машина комната больше, выведите латинскую букву <<M>>. Если Петина комната больше, выведите латинскую букву <<P>>. Если комнаты ребят имеют одинаковую площадь, выведите латинскую букву <<E>>.

В секретной лаборатории профессора Хаоса проходит эксперимент по выращиванию особо опасных бактерий. В начале первого дня эксперимента у Хаоса имеется \(a\) особо опасных бактерий.

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

После извлечения бактерий из инкубатора \(c\) из них используются для проведения различных опытов и затем уничтожаются. Если после извлечения из инкубатора имеется менее \(c\) бактерий, для проведения опытов используются все имеющиеся бактерии, и эксперимент заканчивается.

Оставшиеся бактерии в конце дня необходимо поместить в контейнер и продолжить использовать в эксперименте. Однако в контейнер можно поместить не более \(d\) бактерий, поэтому если число оставшихся бактерий больше \(d\), то в контейнер помещаются \(d\) бактерий, а остальные уничтожаются.

Теперь профессор Хаос хочет выяснить, сколько особо опасных бактерий будет у него в контейнере после \(k\)-го дня эксперимента. Помогите ему найти ответ на этот вопрос.

Формат входных данных
В единственной строке входного файла содержится пять целых чисел \(a\), \(b\), \(c\), \(d\) и \(k\) (\(1 \le a, b \le 1000\), \(0 \le c \le 1000\), \(1 \le d \le 1000\), \(a \le d\), \(1 \le k \le 10^{18}\)).

Формат выходных данных
Выведите одно число — количество бактерий у Хаоса к концу \(k\)-го дня. Если эксперимент завершится в \(k\)-й день или ранее, выведите число 0.