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

Медиана объединений#56019

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

Входные данные
Сначала вводятся числа N и L (2≤N≤100, 1≤L≤300). В следующих N строках задаются параметры, определяющие последовательности.

Каждая последовательность определяется пятью целочисленными параметрами: x₁, d₁, a, c, m. Элементы последовательности вычисляются по следующим формулам: x₁ нам задано, а для всех i от 2 до L: x₁ = x₁–1+d_i-1. Последовательность d_i определяется следующим образом: d₁ нам задано, а для i≥2 di=((a*d_i-1+c) mod m), где mod – операция получения остатка от деления (a*d_i-1+c) на m.

Для всех последовательностей выполнены следующие ограничения: 1≤m≤40000, 0≤a<m, 0≤c<m, 0≤d1<m. Гарантируется, что все члены всех последовательностей по модулю не превышают 10⁹.

Выходные данные
В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N-1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

Бинарный поиск в массиве Бинарный поиск по ответу

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

Медиана объединений#55404

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

Входные данные
Сначала вводятся числа N и L (2≤N≤200, 1≤L≤50000). В следующих N строках задаются параметры, определяющие последовательности.

Каждая последовательность определяется пятью целочисленными параметрами: x₁, d₁, a, c, m. Элементы последовательности вычисляются по следующим формулам: x₁ нам задано, а для всех i от 2 до L: x₁ = x₁–1+d_i-1. Последовательность d_i определяется следующим образом: d₁ нам задано, а для i≥2 di=((a*d_i-1+c) mod m), где mod – операция получения остатка от деления (a*d_i-1+c) на m.

Для всех последовательностей выполнены следующие ограничения: 1≤m≤40000, 0≤a<m, 0≤c<m, 0≤d1<m. Гарантируется, что все члены всех последовательностей по модулю не превышают 10⁹.

Выходные данные
В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N-1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

Бинарный поиск в массиве Бинарный поиск по ответу

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

Выборы#53910

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

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

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

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

Формат входных данных
Первая строка содержит целое число $n$ — количество партий ($1 \le n \le 10^5$). Следующие $n$ строк описывают партии. Каждая из этих строк содержит по два целых числа: $v_i$ — количество жителей, которые собираются проголосовать за эту партию перед началом агитационной компании, и $p_i$ — взятка, которую необходимо дать лидеру партии для того, чтобы сформированное ей в случае победы правительство действовало в интересах бизнесмена ($1 \le v_i \le 10^6$, $1 \le p_i \le 10^6$ или $p_i = -1$). Если партия является идеологически устойчивой, то $p_i$ равно $-1$. Гарантируется, что хотя бы одно $p_i$ не равно $-1$.

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

Бинарный поиск Бинарный поиск по ответу Быстрая сортировка

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

Cow Dance Show#90399

После нескольких месяцев репетиций, коровы готовы дать ежегодное танцевальное представление - балет "Cowpelia".

Остался непрояснённым только размер сцены. Сцена размера $K$ может выдержать $K$ коров, танцующих одновременно. $N$ коров в стаде ($1 \leq N \leq 10,000$) пронумерованы последовательно $1 \ldots N$ в порядке, в котором они должны появиться на сцене во время танца. Каждая корова $i$ планирует танцевать определённое время $d(i)$. Изначально коровы $1 \ldots K$ появляются на сцене и начинают танцевать. Когда первая из этих коров завершит свой танец, она покидает сцену и корова $K+1$ немедленно начинает танцевать и т.д. Поэтому всегда $K$ коров танцуют, за исключением последнего отрезка шоу, когда коровы уходят, но не добавляются. Шоу завершается, когда последняя корова завершит свой танец в момент времени $T$.

Понятно, что чем больше значение $K$, тем меньше время $T$. Поскольку шоу не может длится очень долго, вам на вводе даётся верхняя граница $T_{max}$, указывающая максимально возможное значение величины $T$. Ваша задача - определить минимально возможное подходящее значение $K$.

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

Первая строка ввода содержит $N$ и $T_{max}$, где $T_{max}$ - целое число, не более 1 000 000.

Следующие $N$ строк задают длительности танцев $d(1) \ldots d(N)$ для коров $1 \ldots N$. Каждое из $d(i)$ - целое число в интервале $1 \ldots 100,000$.

Гарантируется, что если $K=N$, шоу закончится вовремя.

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

Выведите наименьшее возможное значение $K$ такое, что танцевальное шоу закончится не более чем через $T_{max}$ единиц времени.

Бинарный поиск по ответу Жадный алгоритм Очередь

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

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

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

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

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

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

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

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

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

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

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

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

ОЦЕНИВАНИЕ:

ФОРМАТ ВВОДА:

ФОРМАТ ВЫВОДА:

ОЦЕНИВАНИЕ:

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

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

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

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

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

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

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

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