Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Counting Liars#90175

Корова Беси прячется где-то на числовой прямой. Каждая из \(N\) (\(1\le N\le 1000\)) других коров Фермера Джона имеет информацию, которой она делится с ФД: \(i\)-ая корова говорит, что Беси прячется в некоторой точке меньше либо равной to \(p_i\), или больше либо равной \(p_i\), (\(0\le p_i\le 10^9\)).

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

ФОРМАТ ВВОДА (С КЛАВИАТУРЫ / stdin):

Первая строка содержит \(N\).

Каждая из следующих \(N\) строк содержит символ L или G, за которым следует целое число \(p_i\). L означает, что \(i\)-ая корова говорит, что Беси скрывается в позиции меньше либо равной \(p_i\), а G означает, что \(i\)-ая корова говорит, что Беси скрывается в позиции больше либо равной \(p_i\)

ФОРМАТ ВЫВОДА (на экран / stdout):

Минимальное количество коров, которые солгали.

—Войти и решать

Sleeping in Class#90158

Беси радовалась введённому индивидуальному обучению. К несчастью её тьютор Фермер Джон очень скучный лектор, и поэтому она часто засыпала во время занятий.

ФД попросил Эльзу записывать количество раз, когда Беси засыпала на каждом занятии. Всего было \(N\) занятий (\(2\le N\le 10^5\)), и Эльза зафиксировала \(a_i\) (\(1\le a_i\le 10^{18}\)) засыпаний на \(i\)-ом занятии. Общее количество засыпаний на всех занятиях не превышает \(10^{18}\).

Эльза хочет представить дело так, что Беси засыпала одинаковое количество раз на каждом занятии.

Единственный способ Эльзы модифицировать свои записи - объединить два соседних занятия или разъединить одно занятие на два. Например, если \(a=[1,2,3,4,5],\) тогда если Эльза объединит второе и третье занятие, то лог станет \([1,5,4,5]\) Если Эльза выберет разделить третье занятие на два, то лог может стать одним из \([1,5,0,4,5]\), \([1,5,1,3,5]\), \([1,5,2,2,5]\), \([1,5,3,1,5]\), or \([1,5,4,0,5]\).

По заданным \(Q\) (\(1\le Q\le 10^5\)) кандидатам \(q_1,\ldots,q_Q\) для наименее любимых Беси чисел (\(1\le q_i\le 10^{18}\)), для каждого из них помогите Эльзе вычислить минимальное количество модификаций лога, чтобы все числа в нём стали одинаковыми.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка каждого теста содержит \(N\), а вторая содержит \(a_1,a_2,\ldots,a_N\). Третья строка содержит \(Q\) - количество запросов, за которым следует \(Q\) строк с целым числом \(q_i\) - кандидат в наименее любимое число Беси.

ФОРМАТ ВЫВОДА (на экран / stdout):

Для каждого \(q_i\) вычислите минимальное количество модификаций, которое требуется для Эльзы, чтобы конвертировать лог в \(q_i\) или выведите \(-1\), если это невозможно.

Жадный алгоритм Задачи на моделирование Префиксные суммы(минимумы, ...)

—Войти и решать

Convoluted Intervals#90131

Коровы играют в игру со множеством из \(N\) интервалов (\(1\le N\le 2\cdot 10^5\)), где \(i\)-ый интервал начинается в позиции \(a_i\) на числовой прямой, а заканчивается в позиции \(b_i \geq a_i\). Оба числа \(a_i\) and \(b_i\) - целые, в интервале \(0 \ldots M\), где \(1 \leq M \leq 5000\).

Чтобы играть в эту игру, Беси выбирает некоторый интервал, например \(i\)-ый. И Эльза выбирает некоторый интервал, например, \(j\)-ый, возможно тот же самый. Для заданной величины \(k\) они выигрывают, если \(a_i + a_j \leq k \leq b_i + b_j\).

Для всех \(k\) в интервале \(0 \ldots 2M\), посчитайте количество упорядоченных пар \((i,j)\) для которых Беси и Эльза выиграют в эту игру.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка ввода содержит \(N\) и \(M\). Каждая из последующих \(N\) строк описывает интервал в терминах целых чисел \(a_i\) и \(b_i\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите \(2M+1\) строку, по одной для каждого \(k\) в интервале \(0 \ldots 2M\).

Префиксные суммы(минимумы, ...)

—Войти и решать

Daisy Chains#90084

Каждый день, в рамках своей прогулки вокруг фермы, корова Беси посещает своё любимое пастбище, на котором растут рядком \(N\) цветков, помеченных числами \(1\ldots N\) \((1\le N \le 100)\). Цветок \(i\) имеет \(p_i\) лепестков \((1 \le p_i \le 1000)\).

Как подающий надежды фотограф, Беси решила сделать несколько фото этих цветков. В частности, для каждой пары цветков \((i,j)\) где \(1\le i\le j\le N\), Беси делает фото всех цветков от \(i\) до \(j\) (включая \(i\) и \(j\)).

Затем Беси посмотрела на эти фотки и заметила, что некоторые фото имеют "средний цветок" - цветок, который имеет \(P\) лепестков, где \(P\) - точное среднее число лепестков среди всех цветков на этом фото.

Сколько из фотографий Беси имеют "средний цветок"?

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка ввода содержит \(N\). Вторая строка ввода содержит \(N\) разделённых одиночными пробелами целых чисел \(p_1 \dots p_N\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите количество фотографий, имеющих средний цветок.

Префиксные суммы(минимумы, ...)

—Войти и решать

Balancing Inversions#90075

Беси и Эльза играют на битовом массиве \(A\) длиной \(2N\) (\(1 \leq N \leq 10^5\)). Счёт Беси - это количество инверсий в первой половине массива \(A\), а счёт Эльзы - количество инверсий во второй половине массива \(A\). Инверсия - это такая пара \(A[i]=1\) и \(A[j]=0\), что \(i<j\). Например, если массив состоит из блока 0, за которым следует блок 1, то инверсий нет. А массив в котором за блоком из \(X\) единиц следует блок из \(Y\) нулей, то имеется \(XY\) инверсий.

Фермер Джон остановился около игры и хочет узнать минимальное количество обменов между соседними элементами, которые нужно совершить, чтобы игра получила ничейный счёт. ФОРМАТ ВВОДА (файл balance.in): Первая строка ввода содержит \(N\), следующая строка содержит \(2N\) целых чисел каждое из которых равно 0 или 1. ФОРМАТ ВЫВОДА (файл balance.out): Выведите количество соседних обменов, которые нужно сделать, чтобы игра получила ничейный счёт.

Жадный алгоритм Префиксные суммы(минимумы, ...)

—Войти и решать

Slingshot#90008

Фермер Джон не любит возить навоз. Он придумал перемещать лотки с навозом пор воздуху с помощью гигантской рогатки.

Ферма Джона построена вдоль прямой дороги, поэтому любое место фермы может быть описано позицией на этой дороге (точка на числовой прямой). ФД построил \(N\) рогаток (\(1 \leq N \leq 10^5\)), \(i\)-ая из которых описывается тремя целыми числами \(x_i\), \(y_i\), \(t_i\), указывающими, что рогатка может переместить навоз из позиции \(x_i\) в позицию \(y_i\) за \(t_i\) единиц времени.

У ФД есть \(M\) лотков с навозом для транспортировки (\(1 \leq M \leq 10^5\)). \(j\)-ый лоток нужно переместить из позиции \(a_j\) в позицию \(b_j\). Перемещение лотка с навозом на тракторе на расстояние \(d\) занимает \(d\) единиц времени. ФД надеется сократить время использованием рогаток. Время перемещения трактора без навоза не учитывается.

Для каждого из \(M\) лотков определите минимально возможное время транспортировки. при условии использования не более одной рогатки.

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

Первая строка ввода содержит \(N\) и \(M\). Каждая из следующих \(N\) строк описывает одну рогатку тремя числами \(x_i\), \(y_i\), \(t_i\) (\(0 \leq x_i, y_i, t_i \leq 10^9\)). Последние \(M\) строк описывают лотки навоза, которые необходимо перемещать, двумя целыми числами \(a_j\) и \(b_j\).

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

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

Префиксные суммы(минимумы, ...)

—Войти и решать

My Cow Ate My Homework#89986

Вам дали длинное домашнее задание из \(N\) вопросов (\(3 \leq N \leq 100,000\)), каждый из которых оценивается баллами в интервале 0...10,000. Как это часто бывает, Ваш учитель планирует выставить финальную оценку, отбрасывая вопрос, на котором Вы получили самую низкую оценку, и находя среднюю оценку среди оставшихся. К несчастью, Беси съела Ваши ответы на первые \(K\) вопросов (\(K\) от 1 до \(N-2\))

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

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

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

Первая строка ввода содержит \(N\), а следующая строка содержит оценки по \(N\) вопросам.

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

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

Префиксные суммы(минимумы, ...)

—Войти и решать

Haybale Feast#89981

Фермер Джон готовит деликатесную еду для своих коров. В его амбаре имеется \(N\) стогов сена (\(1 \le N \le 100,000\)). \(i\)-ый стог имеет опредённый вкус \(F_i\) (\(1 \le F_i \le 10^9\)) и определённую пряность \(S_i\) (\(1 \le S_i \le 10^9\)).

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

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

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

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

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

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

"Два указателя"Жадный алгоритм Префиксные суммы(минимумы, ...)

—Войти и решать

Fair Photography#89950

N (2 <= N <= 100,000) коров Фермера Джона стоят в различных позициях вдоль длинной изгороди. I-ая корова стоит на позиции x_i (целое число в диапазоне 0...1,000,000,000) и является либо чисто белой коровой, либо коровой с пятном. Никакие две коровы не занимают одну и ту же позицию и имеется хотя бы одна белая корова.
ФД хочет сделать фото непрерывного интервала коров, так чтобы на фото было одинаковое количество белых и пятнистых коров. ФД хочет определить максимальный размер такого фото, где размер равен разности между максимальной и минимальной позициями коров на фото.
Чтобы дать себе шанс увеличить размер фото, ФД может пририсовать пятно произвольному подмножеству белах коров, тем самым превращая их в пятнистых.
Пожалуйста, определите наибольший размер фото, которое ФД может сделать, с учётом возможности перекрашивания коров из белых в пятнистые. (Конечно, ФД может и не красить коров, если ему так выгоднее)
PROBLEM NAME: fairphoto
Формат ввода:
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит x_i и либо W (для белой коровы) либо S (для пятнистой коровы).
Примечание
Всего есть 5 коров. Одна из них белая на позиции 8 и т.д.

Формат вывода:
* Строка 1: Максимальный размер фото, которое может сделать ФД с учётом возможности перекрашивания белых коров в пятнистых.

Примечание
ФД фотографирует коров с позиции 3 по позицию 10. В этом интервале имеется 4 коровы 3 белых и 1 пятнистая, поэтому он перекрасит одну корову из белых в пятнистую.

Префиксные суммы(минимумы, ...)

—Войти и решать

Fair Photography#89944

N коров (1 <= N <= 100,000) Фермера Джона стоят на различных позициях вдоль длинной прямой изгороди. I-ая корова стоит на позиции x_i (целое число в диапазоне 0...1,000,000,000) и имеет породу B_i (‘G’ либо ‘H’). Никакие две коровы не занимают одну и ту же позицию.
ФД хочет сделать фото непрерывного интервала коров, но так чтобы породы были справедливо представлены на фото. Справедливо это значит, что все типы представлены одним числом, Например фото где все коровы имеют тип ‘H’ – подходит и фото где 27 ‘H’ и 27 ‘G’ тоже подходит, а фото с 10 ‘H’ и 9 ‘G’ – не подходит. Помогите ФД найти справедливое фото максимального размера. Размером фото называется разность между максимальной и минимальной позицией коров на фото. Возможно, что справедливое фото будет состоять из одной коровы, тогда ответ 0.
PROBLEM NAME: fairphoto
Формат ввода:
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит x_i и b_i.
Примечание
Имеется 6 коров с породами слева направо G, H, G, G, H, G.
Формат вывода:
* Строка 1: Одно целое число – максимальный размер справедливого фото.
Примечание
Наибольшее справедливое фото содержит 4 средних коровы, 2 ‘H’ и 2 ‘G’.

Префиксные суммы(минимумы, ...)

—Войти и решать

The Lazy Cow#89941

Сегодня жаркий летний день, и корова Беси чувствует себя утомлённой. Она хочет так расположиться на поле, чтобы она находилась на коротком расстоянии от как можно большего количества вкусной травы.
Поле, на котором живёт Беси, описывается решёткой N*N квадратных ячеек (1 <= N <= 400). Ячейка в строке r и колонке c (1 <= r,c <= N) содержит G(i,j) единиц травы (0 <= G(i,j) <= 1000). От своей начальной ячейки Беси хочет сделать не более K шагов (0 <= K <= 2*N). Каждый шаг – это переход в соседнюю ячейку (на север, юг, запад или восток от текущей).
Например, предположим задана такая решётка где B описывает начальную позицию Беси (строка 3, колонка 3)
50 5 25* 6 17 14 3* 2* 7* 21 99* 10* 1*(B) 2* 80* 8 7* 5* 23* 11 10 0 78* 1 9
Если K=2, то для Беси достижимы только ячейки, помеченные *.
Пожалуйста, помогите Беси определить максимальное количество травы, которое она может достичь, если выберет оптимальное положение на решётке.
PROBLEM NAME: lazy
Формат входных данных
* Строка 1: Целые числа N и K.
* Строки 2..1+N: Строка r+1 содержит N целых чисел, описывающих строку r решётки.
Формат выходных данных
Примечание
В примере выше Беси может достичь 342 единицы травы, если разместится в середине решётки.

Префиксные суммы(минимумы, ...)

—Войти и решать

The Lazy Cow#89936

Сегодня жаркий летний день, и корова Беси чувствует себя утомлённой. Она хочет так расположиться на поле, чтобы она находилась на коротком расстоянии от как можно большего количества вкусной травы.
Имеется N (1 <= N <= 100,000) участков травы на поле Беси, которое представляется числовой прямой. I-тый участок травы содержит g_i единиц травы (1<=g_i<=10,000) и находящихся в различных точках на расстоянии x_i от начала поля (0 <= x_i <= 1,000,000). Беси хочет выбрать на поле такую точку, (возможно некоторую точку из тех, что с травой), чтобы максимальное количество травы находилось на расстоянии не более K шагов от этой точки (1 <= K <= 2,000,000).
Пожалуйста, помогите Беси определить максимальное количество травы если она выберет наилучшее расположение этой точки.
PROBLEM NAME: lazy
Формат входных данных
* Строка 1: Два целых числа N и K.
* Строки 2..1+N: Строка i+1 описывает i-ый кусок травы, используя 2 Целых числа: g_i и x_i
Формат выходных данных
* Строка 1: Максимальное количество травы на расстоянии не превышающем K от оптимальной позиции Беси.

Примечание
Беси должна расположиться на позиции x=4, тогда количества травы, находящиеся в позициях x=1, x=2 и x=7 ,будут достижимы для неё.

Префиксные суммы(минимумы, ...)

—Войти и решать

Breed Proximity#89889

N (1 <= N <= 50,000) коров Фермера Джона выстроились в ряд, каждая описывается своим ID породы.
Коровы одной породы рискуют поругаться, если стоят слишком близко. А именно, две коровы одной породы называются "crowded" если их позиции в ряду отличаются не более чем на K (1<=K< N).
Вычислите максимальный ID пары "crowded" коров.
PROBLEM NAME: proximity
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: N и K.
* Строки 2..1+N: Каждая строка содержит ID породы одной коровы в ряду. Все ID коров находятся в диапазоне 0..1,000,000.

Формат выходных данных
* Строка 1: Максимальный ID породы двух "crowded" коров или -1 если нет такой пары коров.
Примечание
Имеется две пары "crowded" коров - с ID породы 3 и 4.

Префиксные суммы(минимумы, ...)

—Войти и решать

Concurrently Balanced Strings#89847

Коровы Фермера Джона различаются по породам и каждая корова помечена гигантским пятном на боку в виде круглой скобки. В зависимости от направления, в котором смотрит корова, эта скобка может быть левой или правой скобкой.
Однажды утром ФД организовал своих коров в K строк по N коров в каждой строке (1 <= K <= 10, 1 <= N <= 50,000). Коровы смотрят в произвольных направлениях, поэтому построение может быть описано как K строк из N символов-скобок. Назовем эти строки S₁, S₂, :, S_K. ФД заметил, что некоторые диапазоны коров "параллельно сбалансированы". Диапазон i..j коров называется "параллельно сьалансированным" тогда и только тогда, когда строки S₁,S₂,:,S_K сбалансированы в этом диапазоне. Например, если K=3 и у нас есть 3 строки
S₁ = )()((())))(()) S₂ = ()(()()()((()) S₃ = )))(()()))(()) 1111 01234567890123
Тогда диапазон [3:8] параллельно сбалансирован, поскольку S₁[3...8] = ((())) S₂[3...8] = ()()() S₃[3...8] = (()())
Диапазоны [10...13] и [11...12] также параллельно сбалансированы.
Ваша задача - посчитать количество сбалансированных диапазонов для заданных K строк длины N.
Строка S называется сбалансированной, если количество левых скобок равно количеству правых и для любого префикса этой строки количество левых скобок не меньше чем количество правых скобок.
Например эти строки сбалансированы () (()) ()(()())
А эти - нет: )( ())( ((())))
PROBLEM NAME: cbs
Формат входных данных
* Строка 1: Два целых числа, K и N.
* Строки 2..K+1: Каждая строка содержит N скобок.
Формат выходных данных
* Строка 1: Одно целое число - количество сбалансированных диапазонов

Префиксные суммы(минимумы, ...)

—Войти и решать

Typo#89844

Беси только что купила новый лэптоп. Однако ей неудобно работать с клавиатурой, поэтому она набирает строки из круглых скобок. Она может ошибиться и набрать ( вместо ) и наоборот.
Посчитайте количество мест в строке таких, что замена одной скобки на противоположную в этом месте сделает строку сбалансированной.
Есть несколько способов определить, что такое "сбалансированная" строка скобок. Например, так: 1) Всего должно быть одинаковое количество левых ( и правых ) скобок и для любого префикса этой строки, левых скобок должно быть не меньше чем правых.
Следующие строки сбалансированы () (()) ()(()())
А эти - нет:
)( ())( ((())))
PROBLEM NAME: typo
Формат входных данных
* Строка 1: строка из скобок с длиной N (1 <= N <= 100,000).
Формат выходных данных
* Line 1: количество позиций в этой строке, (если они вообще есть), таких, что замена одной скобки на противоположную в этой позиции приведет к тому, что строка станет сбалансированной.
Примечание
Для исходной строки:
12345678 ()(())))
Замена скобки в позиции 2 приводит к такой сбалансированной строке
12345678 (((())))
Аналогично сбалансированные строки получается при замене скобок в позициях 5, 6, и 7.

Префиксные суммы(минимумы, ...)

—Войти и решать

Haybale Restacking#89837

Фермер Джон заказал большое количество пакетов с сеном. Он хочет разложить их в N кучек (1 <= N <= 100,000), расположенных по кругу, где куча i содержит B_i пакетов с сеном. Водитель грузовика разложил пакеты в N куч с A_i пакетов в каждой. Известно, что сумма B_i равна сумме A_i.
ФД хочет переместить кучи из их текущего положения A_i в требуемое B_I. X единиц работы требуется, чтобы переместить один пакет из кучи в другую, которая отстоит на X шагов от данной по кругу.
Определите минимальное количество работы, требуемое для преобразования "хаоса" в "порядок".

PROBLEM NAME: restack
Формат входных данных
* Строка 1: Одно целое число N.
* Строки 2..1+N: Строка i+1 содержит два целых числа A_i и B_i (1 <= A_i, B_i <= 1000).
Формат выходных данных
Примечание
Минимальное количество работы, которое надо совершить, равно 13: переместить 6 пакетов из кучи 1 в кучу 4, переместить 1 пакет из кучи 3 в кучу 2, переместить 6 пакетов из кучи 3 в кучу 4.

Префиксные суммы(минимумы, ...)

—Войти и решать

Haybale Stacking#89826

Беси согласилась помочь ФД уложить пакеты с сеном. Она начинает с N (1 <= N <= 1,000,000, N нечетное) пустых стеков, пронумерованных от 1 до N. Затем ФД дает ей последовательность из K инструкций (1 <= K <= 25,000), каждая вида A B, означающая, что Беси должна добавить по одному пакету с сеном в каждый из стеков в диапазоне от A до B. Например, инструкция 10 13 означает, что Беси должна положить по пакету сеном в стеки 10, 11, 12, 13.
После того как вся работа закончена, ФД хочет узнать медианную высоту всех N своих стеков - то есть высоту среднего стека, если все стеки упорядочить по высоте. По условию N нечетно, поэтому этот стек уникален. Пожалуйста, помогите Беси ответить на этот вопрос.
PROBLEM NAME: stacking
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N K.
* Строки 2..1+K: Каждая строка содержит одну инструкцию ФД в виде двух целых (разделенных пробелом) чисел A B (1 <= A <= B <= N).

Формат выходных данных
* Строка 1: Медианная высота после того как Беси выполнит все инструкции

Примечание
После того, как Беси закончит, стеки будут иметь высоты 0,1,2,3,3,1,0. Если их упорядочить, получим: 0,0,1,1,2,3,3. Средний элемент равен 1.

Алгоритмы обработки Использование сортировки Префиксные суммы(минимумы, ...)

—Войти и решать

Above the Median#89800

Problem 1: Above the Median [Brian Dean]
Фермер Джон выстроил N (1 <= N <= 100,000) своих коров, чтобы померять их высоты. Корова i имеет высоту H_i (1 <= H_i <= 1,000,000,000) нанометров. ФД производит очень точные измерения! ФД хочет сфотографировать некоторую непрерывную последовательность своих коров, и послать эту фотографию на соревнование.
Допускается к соревнованию только фотография группы коров, у которой медианная высота не менее чем заданная величина X (1 <= X <= 1,000,000,000).
В этой задаче мы определяем медианой массива A[0..K] значение A[ceiling(K/2)] после того, как A отсортировали. Здесь ceiling(K/2) – это округление K/2 до ближайшего целого. Например, медиана от {7, 3, 2, 6} есть 6, а медиана от {5,4,8} есть 5.
Помогите ФД посчитать количество различных непрерывных последовательностей коров, фотографии которых будут допущены к соревнованию.
PROBLEM NAME: median
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: N и X.
* Строки 2..N+1: Строка i+1 содержит одно целое число H_i.
Формат выходных данных
* Строка 1: Количество подпоследовательностей коров ФД, у которых медиана не менее X. Заметим, что это число может не поместиться в 32-битное целое.
Примечание
Всего существует 10 непрерывных последовательностей. Однако только 7 из них имеют медиану не менее 6: {10}, {6}, {10, 5}, {5, 6}, {6, 2}, {10, 5, 6}, {10, 5, 6, 2}.

Префиксные суммы(минимумы, ...)

—Войти и решать

Хроноробот#84671

В 2147 году корпорация «ТемпоралТех» создала первого робота-разведчика для исследования опасных планет. Робот оснащён уникальной системой хронометок — устройством, позволяющим мгновенно вернуться в безопасную точку при обнаружении угрозы.

Робот перемещается по бесконечному полю и выполняет программу:

L — шаг влево (x уменьшается на 1)
R — шаг вправо (x увеличивается на 1)
U — шаг вверх (y увеличивается на 1)
D — шаг вниз (y уменьшается на 1)
( — установить хронометку (запомнить текущую позицию как безопасную)
) — экстренный возврат (переместиться к последней метке, метка исчезает)

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

Робот начинает разведку в точке (0, 0). По записи бортового журнала определи, в какой точке робот завершил миссию.

Пример

Журнал: RRR(RR)DD

Робот прошёл 3 клетки вправо, поставил метку на случай опасности, продолжил разведку ещё на 2 клетки вправо. Затем обнаружил угрозу и активировал возврат к метке. Оказавшись в безопасности, спустился на 2 клетки вниз.

Шаг  Команда  Позиция   Что произошло
─────────────────────────────────────────────
 0      —     (0, 0)    Старт миссии
 1      R     (1, 0)    Шаг вправо
 2      R     (2, 0)    Шаг вправо
 3      R     (3, 0)    Шаг вправо
 4      (     (3, 0)    Метка установлена
 5      R     (4, 0)    Шаг вправо
 6      R     (5, 0)    Шаг вправо
 7      )     (3, 0)    Возврат к метке!
 8      D     (3, -1)   Шаг вниз
 9      D     (3, -2)   Шаг вниз

Финальная позиция: 3 -2

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

Одна строка — запись бортового журнала.

Символы: L, R, U, D, (, )
Длина: от 1 до 10⁵ символов
Гарантируется корректность: каждому ) предшествует непогашенная (

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

Два целых числа через пробел — координаты (x, y) финальной позиции робота.

Стек

✓ 2✗ 0—Войти и решать

Космический турнир#84529

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

Каждое попадание x приносит базовые очки
Капитан может активировать силовое поле, введя символ ( — пока оно активно, все очки удваиваются
Деактивация поля происходит по вводу символа ) — возврат к обычному режиму
Силовые поля могут быть вложенными — тогда множители перемножаются!

Запись матча — строка из символов x, ( и ). Подсчитай итоговый счёт команды.

Пример

Запись матча: xx(x(xx)x)x

Символ	Множитель	Очки	Пояснение
`x`	×1	+1	Обычный режим
`x`	×1	+1	Обычный режим
`(`	—	—	Поле активировано, ×2
`x`	×2	+2	Внутри поля
`(`	—	—	Второе поле, ×4
`x`	×4	+4	Двойная вложенность
`x`	×4	+4	Двойная вложенность
`)`	—	—	Внутреннее поле снято, ×2
`x`	×2	+2	Снова одинарное поле
`)`	—	—	Все поля сняты, ×1
`x`	×1	+1	Обычный режим

Итого: 1 + 1 + 2 + 4 + 4 + 2 + 1 = 15

Формат ввода

Одна строка, содержащая запись матча.

Символы: x (попадание), ( (активация поля), ) (деактивация)
Длина строки: 1 ≤ |s| ≤ 10⁵
Гарантируется корректность скобочной последовательности

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

Одно целое число — итоговый счёт команды.

Стек

✓ 2✗ 2—Войти и решать