Информатика

15 724 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Лифт#90843
В вашем отеле необычный лифт — вместо привычных кнопок для каждого этажа, в нём есть только две:  + 3 и  - 2, перемещающие лифт на три этажа вверх и на два этажа вниз соответственно.

Вы хотите попасть с этажа номер 0 (там находится лобби отеля) на этаж номер D (там находится ваш номер), но не хотите постоянно нажимать на кнопки. За какое минимальное число нажатий вы сможете добраться до D-го этажа?

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

В единственной строке дано одно целое число D ( - 1000 ≤ D ≤ 1000) — номер этажа, на который вы хотите попасть. Обратите внимание, что в отеле есть подземные этажи с отрицательными номерами.

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

Выведите одно число — минимальное число нажатий для перемещения с нулевого этажа на этаж с номером D.

Примечание

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

Во втором примере из условия, чтобы спуститься на 5 этажей вниз, нужно один раз подняться на 3 этажа и 4 раза спуститься вниз на 2 этажа, таким образом, получится 5 нажатий кнопок.

Задачи на моделирование
✓ 23✗ 18300лёгкаяВойти и решать
Монотонная подпоследовательность#90465

Монотонная подпоследовательностьстандартный вводстандартный вывод1 секунда256 мегабайт

Рассмотрим последовательность \(a_1, a_2, \ldots, a_n\). Его подпоследовательность \(a_{i_1}, a_{i_2}, \ldots, a_{i_k}\), где \(1 \le i_1 < i_2 < \ldots < i_k \le n\) назвается монотонной, если либо \[a_{i_1} \le a_{i_2} \le \ldots \le a_{i_k},\] либо \[a_{i_1} \ge a_{i_2} \ge \ldots \ge a_{i_k}.\]

Для заданных \(n\) и \(k\), найдите последовательность, состоящую из чисел от 1 до \(n\) таких, что каждое из чисел встречается в ней ровно один раз, а длина самой длинной монотонной подпоследовательности (возрастающей или убывающей) составляет ровно \(k\).

Формат входных данных
Первая строка входных данных содержит целые числа \(n\) и \(k\) (\(1 \le k \le n \le 10^6\)), длина последовательности и требуемая длина самой длинной монотонной подпоследовательности.

Формат выходных данных
Если требуемой последовательности не существует, выведите \(-1\) в первой и единственной строке.

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

 

 
Жадный алгоритм
✓ 1✗ 0—Войти и решать
Двоичные единицы#90463

Рассмотрим натуральное число \(x\). Требуется прибавить к нему минимальное возможное целое неотрицательное число \(y\), чтобы двоичная запись получившегося числа \(x+y\) имела ровно \(k\) единиц.

Формат входных данных
Первая строка ввода содержит натуральное число \(x\) (\(1 \le x \le 10^{18}\)).

Вторая строка ввода содержит натуральное число \(k\) (\(1 \le k \le 60\)).

Формат выходных данных
Выведите минимальное возможное целое неотрицательное число \(y\), такое что двоичная запись числа \(x+y\) имеет ровно \(k\) единиц.

Двоичная система счисления
✓ 2✗ 6—Войти и решать
Против постулата Бертрана#90462

Постулат Бертрана утверждает, что для любого \(n \ge 2\) найдётся простое число \(p\), для которого \(n < p < 2n\). Постулат Бертрана был сформулирован в качестве гипотезы в 1845 году французским математиком Бертраном, проверившим её до \(n = 3\,000\,000\), и доказан в 1852 году Чебышёвым.

Петя хочет повторить подвиг Бертрана и убедиться в справедливости его постулата для разных значений \(n\). Однако, поскольку он не сомневается в корректности доказательства Чебышёва, он немного изменил цель: для данного \(n\), Петя хочет найти максимальный по длине отрезок составных чисел, который лежит строго между \(n\) и \(2n\).

Требуется найти такие \(l\) и \(r\), чтобы \(n < l \le r < 2n\), все числа от \(l\) до \(r\), включительно, были составными и \(r - l\) было максимально. Если подходящих отрезков несколько, необходимо вывести тот, у которого \(l\) минимально.

Формат входных данных
На вход подаётся одно целое чиcло \(n\) (\(3 \le n \le 10^7\)).

Формат выходных данных
Выведите искомые \(l\) и \(r\).

Решето Эратосфена
✓ 2✗ 16—Войти и решать
Электричка#90455

В столице Флатландии открыта линия городской электрички. На линии \(n\) станций, пронумерованных от \(1\) до \(n\). Линия проходит город по диаметру и обоими концами уходит в область. А именно, станции с \(1\)-й по \(a\)-ю находятся в области, затем станции с \((a+1)\)-й по \((b-1)\)-ю находятся в городе, а станции с \(b\)-й по \(n\)-ю находятся в области.

Стоимость билета на электричку зависит от начальной, конечной станции и того, через какие станции проезжает пассажир.

  • Если и начальная, и конечная станция находятся в городе, применяется тариф <<город>>.

  • Если обе станции находятся в области, причём между этими станциями электричка не проезжает через город, то применяется тариф <<область>>.

  • В противном случае применяется тариф <<полный>>.

Напишите программу, которая по начальной станции \(s\) и конечной станции \(t\) определяет, какой тариф необходимо применить.

Формат входных данных
Первая строка содержит три целых числа: \(n\), \(a\) и \(b\) (\(3 \le n \le 10^9\), \(1 \le a\), \(b \le n\), \(b - a > 1\)).

Вторая строка содержит два целых числа: \(s\) и \(t\) (\(1 \le s, t \le n\), \(s \ne t\)).

Формат выходных данных
Если необходимо применить тариф <<город>>, выведите <<City>>.

Если необходимо применить тариф <<область>>, выведите <<Outside>>.

Если необходимо применить тариф <<полный>>, выведите <<Full>>.

Разбор случаев
✓ 2✗ 1—Войти и решать
Шахматная доска#90452

Саша пронумеровала клетки шахматной доски, начиная с левого нижнего угла (клетки a1) по горизонталям сверху вниз, внутри горизонтали слева направо. У неё получилась следующая нумерация:

image

По заданному номеру клетки выведите, что это за клетка.

На вход подаётся одно число \(n\) от 1 до 64.

Выведите, какая клетка получила номер \(n\).

В этой задаче 20 тестов, каждый оценивается независимо в 5 баллов.

Вычисление по заданной формуле
✓ 2✗ 1—Войти и решать
Why Did the Cow Cross the Road III#90434

Ферма Джона представляет собой квадратную решётку из \(N \times N\) полей (\(2 \leq N \leq 100\)). Определённые пары соседних полей (север-юг или запад-восток) разделены дорогами, и высокий забор идёт вокруг периметра всей решётки, не давая коровам возможности покинуть ферму. Коровы могут свободно перемещаться с любого поля на любое соседнее поле (на сервер, юг, запад, восток), хотя они предпочитают переходить дороги только когда это абсолютно необходимо.

Имеется \(K\) коров (\(1 \leq K \leq 100, K \leq N^2\)) на ферме, каждая расположена в различном поле. Пара коров называется "далёкой", если для того чтобы одна корова смогла посетить другую, необходимо перейти хотя бы одну дорогу. Помогите ФД посчитать количество пар удалённых коров.

ФОРМАТ ВВОДА (файл countcross.in):

Первая строка ввода содержит \(N\), \(K\), \(R\). Следующие \(R\) строк описывают \(R\) дорог существующие между парами соседних полей. Каждая строка имеет вид \(r\) \(c\) \(r'\) \(c'\) (целые числа в интервале \(1 \ldots N\)), указывающих, что имеется дорога между соседними полями (строка \(r\), колонка \(c\) и строка \(r'\), колонка \(c'\)). Последние \(K\) строк описывают местоположение \(K\) коров (строка, колонка).

ФОРМАТ ВЫВОДА (файл countcross.out):

Выведите количество пар "далёких" коров.

Поиск компонент связности
—Войти и решать
Why Did the Cow Cross the Road II#90433
Длинная дорога через ферму Джона имеет \(N\) перекрёстков, последовательно пронумерованных \(1 \ldots N\) (\(1 \leq N \leq 100,000\)). Чтобы помочь коровам переходить дорогу на этих перекрёстках, ФД установил светофоры, на которых загорается зелёная корова, когда коровам можно идти, и красная - в противном случае. К несчастью, большой электрический шторм повредил некоторые из этих светофоров. По списку повреждённых светофоров, вычислите минимальное количество светофоров, которое ФД должен восстановить, чтобы существовал непрерывный блок из не менее \(K\) работающих светофоров.

ФОРМАТ ВВОДА (файл maxcross.in):

Первая строка ввода содержит \(N\), \(K\) и \(B\) (\(1 \leq B, K \leq N\)). Следующие \(B\) строк описывают номер сломанного светофора.

ФОРМАТ ВЫВОДА (файл maxcross.out):

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

Префиксные суммы(минимумы, ...)
—Войти и решать
Why Did the Cow Cross the Road#90432
Коровы Фермера Джона учатся переходить через дорогу эффективно. И ищут цыплят в качестве учителей.

Цыплята очень занятые существа и имеют ограниченное время для помощи коровам. Всего имеется \(C\) цыплят на ферме (\(1 \leq C \leq 20,000\)), последовательно пронумерованных \(1 \ldots C\), и каждый цыплёнок \(i\) может помогать коровам ровно время \(T_i\). Коровы никуда не торопятся. Всего имеется \(N\) коров на ферме (\(1 \leq N \leq 20,000\)), последовательно пронумерованных \(1 \ldots N\), и корова \(j\) способно переходить дорогу между временами \(A_j\) и \(B_j\). В идеале корова \(j\) хочет найти цыплёнка \(i\), который поможет её перейти через дорогу. Для того, чтобы их расписания были совместимы, необходимо чтобы выполнялось неравенство \(A_j \leq T_i \leq B_j\).

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

ФОРМАТ ВВОДА (файл helpcross.in):

Первая строка ввода содержит \(C\) и \(N\). Следующие \(C\) строк содержат \(T_1 \ldots T_C\), а последующие \(N\) строк содержат \(A_j\) и \(B_j\) (\(A_j \leq B_j\)) для \(j = 1 \ldots N\). \(A\), \(B\), \(T\)' – все неотрицательные числа (не обязательно различные) не более 1,000,000,000.

ФОРМАТ ВВОДА (файл helpcross.out):

Вычислите максимально-возможное количество пар корова-цыплёнок.

Жадный алгоритм
—Войти и решать
Why Did the Cow Cross the Road III#90431
Фермер Джон продолжает исследование переходов коров через дорогу, описанную в двух предыдущих задачах. Теперь он считает дружественными породы коров \(a\) и \(b\), если if \(|a - b| \leq K\), и недружественными в противном случае.

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

ФОРМАТ ВВОДА (файл friendcross.in):

Первая строка ввода содержит \(N\) (\(1 \leq N \leq 100,000\)) и \(K\) (\(0 \leq K < N\)). Следующие \(N\) строк описывают порядок по номерам пород, полей на первой стороне дороги. Каждый номер породы - это число в интервале \(1 \ldots N\). Последние \(N\) строк описывают порядок по номерам пород, полей на второй стороне дороги. Каждый номер породы появится ровно один раз с каждом порядке.

ФОРМАТ ВВОДА (файл friendcross.out):

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

Дерево отрезков, RSQ, RMQ
—Войти и решать
Why Did the Cow Cross the Road#90429

Фермер Джон растит \(N\) пород коров (\(1 \leq N \leq 100,000\)), каждое из его полей предназначено для пастбища одной специфической породы коров, например, поле предназначенное для коров породы 12 может быть использовано только для коров породы 12 и не может быть использовано для коров других пород. Длинная дорога идёт вдоль фермы. Имеется последовательность из \(N\) полей вдоль одной стороны дороги (по одному для каждого типа коров) и \(N\) полей вдоль другой стороны дороги (тоже по одному для каждого типа коров). Когда корова пересекает дорогу, она переходит из одного поля, предназначенного для этой породы коров в другое поле, предназначенное для этой породы коров.

Если бы ФД "подумал вперёд" он мог бы упорядочить поля под породы таким образом, чтобы поля для одной и той же породы по разные стороны дороги находились друг напротив друга, и никакие коровы не могли бы столкнуться при переходе дороги. Однако упорядочивание полей по породам с разных сторон дороги может быть и различным, и тогда могут быть пары пород, для которых их пути пересекаются при переходе дороги. Пара различных пород \((a,b)\) называется "пересекающейся", если любой путь через дорогу для коровы породы \(a\) должен пересекаться с любым путём через дорогу для коровы породы \(b\).

ФД хочет минимизировать количетво пересекающихся пар пород. По логистическим причинам ФД может перемещать коров "по кругу" на одной стороне дороги, так что поля осуществляют "циклический сдвиг". То есть для некоторого \(0 \leq k < N\), каждая корова перемещается на \(k\) полей вперёд, а коровы из последних \(k\) полей пермещаются в первые \(k\) полей. Например, если поля на одной стороне дороги упорядочены так: 3, 7, 1, 2, 5, 4, 6 и выполняется сдвиг на \(k=2\), то новый порядок будет такой: 4, 6, 3, 7, 1, 2, 5. Определите минимальное возможное количество пересекающихся пар пород, которые могут существовать после соответствующего циклического сдвига полей на одной стороне дороги.

ФОРМАТ ВВОДА (файл mincross.in):

Первая строка содержит число \(N\). Следующие \(N\) строк описывают порядок, по номерам пород на полях вдоль первой стороны дороги. Каждый номер породы - целое число в интервале \(1 \ldots N\). Последние \(N\) строк описывают порядок, по номерам пород коров, полей на другой стороне дороги.

ФОРМАТ ВЫВОДА (фвйл mincross.out):

Выведите минимальное количество пересекающихся пар пород коров после циклического сдвига полей на одной стороне дороги (любая сторона может сдвигаться).

Префиксные суммы(минимумы, ...)
—Войти и решать
Why Did the Cow Cross the Road III#90428
Ферма Джона имеет большую круглую дорогу по периметру главного поля, на котором его коровы пасутся каждый день. Каждое утро коровы переходят через эту дорогу, идя в поле, а каждый вечер переходят дорогу ещё раз, возвращаясь в амбар.

Как известно, коровы - существа привычки, поэтому они переходят дорогу одним и тем же способом каждый день. Каждая корова приходит в поле в точке, отличающейся от той, в которой она с него уходит, и все эти точки для разных коров также отличаются друг от друга. У ФД есть \(N\) коров, последовательно пронумерованных \(1 \ldots N\), Поэтому имеется ровно \(2N\) точек у дороги. ФД выписал все эти точки по номерам коров, по часовой стрелке, сформировав последовательность из \(2N\) чисел, каждое из которых встречается в этой последовательности ровно дважды. Он не записывал, является ли эта точка точкой входа или точкой выхода.

По его карте точек ФД хочет узнать, сколько путей различных пар коров могут пересечься в течение дня. Он называет пару коров \((a,b)\) пересекающейся парой, если путь коровы \(a\) от входа к выходу должен пересечься с путём коровы \(b\) от входа к выходу. Помогите ФД вычислить общее количество пересекающихся пар.

ФОРМАТ ВВОДА (файл circlecross.in):

Первая строка ввода содержит \(N\) (\(1 \leq N \leq 50,000\)), а последующие \(2N\) строк описывают номера коров в последовательности входов и выходов вокруг поля.

ФОРМАТ ВЫВОДА (файл circlecross.out):

Выведите количество пересекающихся пар.

Префиксные суммы(минимумы, ...)
—Войти и решать
Поделиться
Класснуть