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

После нескольких месяцев репетиций, коровы готовы дать ежегодное танцевальное представление - балет "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}$ единиц времени.

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

Building a Tall Barn#90396

Фермер Джон строит новый $N$-этажный амбар с помощью своих $K$ коров ($1 \leq N \leq K \leq 10^{12}$ и $N \leq 10^5$). Чтобы сделать работу быстрее ему нужно оптимально распределить работу между коровами.

Каждая корова должна быть назначена на работу ровно на один этаж. И на каждый этаж должна быть назначена хотя бы одна корова. $i$-ый этаж требует выполнения $a_i$ единиц работы , каждая корова завершает одну единицу работы ровно за час. Поэтому если $c$ коров работают на этаже $i$, то они выполнят всю работу ровно за $a_i / c$ единиц времени. Из соображений безопасности, этаж $i$ должен быть завершён прежде чем начнётся работа на этаже $i+1$.

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

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

Первая строка ввода содержит $N$ и $K$.

Следующие $N$ строк содержат $a_1 \ldots a_N$, каждое - положительное целое не более чем $10^{12}$.

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

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

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

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

Angry Cows#90387

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

Имеется $N$ стогов сена расположенных в целочисленных позициях $x_1, x_2, \ldots, x_N$ на числовой прямой. Если корова приземляется с энергией $R$ в позиции $x$, это вызывает взрыв "радиуса $R$", разрушающий все стоги сена в диапазоне $x-R \ldots x+R$.

Всего имеется $K$ коров для выстрелов, каждая с одной и той же энергией $R$. Определите минимальную целую величину $R$ такую, что возможно используя эти $K$ коров разрушить все стоги сена на сцене.

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

Первая строка ввода содержит $N$ ($1 \leq N \leq 50,000$) и $K$ ($1 \leq K \leq 10$). Каждая из оставшихся $N$ строк содержит целые числа $x_1 \ldots x_N$ (каждое в интервале $0 \ldots 1,000,000,000$).

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

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

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

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

Angry Cows#90381

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

Имеется $N$ стогов сена, расположенных в различных целочисленных позициях $x_1, x_2, \ldots, x_N$ на числовой прямой. Если корова приземлится с энергией $R$ в позиции $x$, это вызовет взрыв "радиусом $R$", что вызовет взрывы всех стогов сена в диапазоне $x-R \ldots x+R$. Все стоги сена в этом диапазоне также одновременно взрываются с радиусом взрыва $R-1$. Все ещё не взорванные стоги сена, попавшие в этот диапазон, снова взрываются уже с радиусом взрыва $R-2$, и т.д.

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

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

Первая строка ввода содержит $N$ ($2 \leq N \leq 50,000$). Оставшиеся $N$ строк содержат целые числа $x_1 \ldots x_N$ (каждое в диапазоне $0 \ldots 1,000,000,000$).

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

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

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

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

Moocast#90361

$N$ ($1 \leq N \leq 1000$) коров Фермера Джона хотят организовать безопасную систему для передачи важных сообщений.

Они купили по одной "воки-токи" для каждой коровы. Каждая такая "воки-токи" имеет ограниченный радиус передачи информации. Но коровы могут передавать сообщения "по эстафете", поэтому нет необходимости для каждой коровы иметь возможность передавать сообщения непосредственно любой другой корове.

Коровам нужно решить сколько денег необходимо потратить на "воки-токи". Если они потратят \$X, они получат "воки-токи", способно передавать на расстояние до $\sqrt{X}$. То есть, квадрат расстояния между коровами стоит не более $X$ чтобы обеспечить их коммуникацией.

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

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

Первая строка ввода содержит $N$.

Каждая из $N$ последующих строк содержит $x$ и $y$ координаты одной коровы. И то и другое - целое в интервале $0 \ldots 25,000$.

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

Напишите в одну строку целое $X$ - минимальное количество денег, которое коровы должны потратить на "воки-токи"

Бинарный поиск по ответу графы Поиск компонент связности

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

Wormhole Sort#90113

Коровы Фермера Джона устали от ежедневных сортировок перед выходом из амбара. Они получили Ph.D по квантовой физике и готовы ускорить этот процесс.

Этим утром, как обычно $N$ коров ($1 \leq N \leq 10^5$), последовательно пронумерованных $1 \dots N$, находятся в амбаре на различных позициях, также пронумерованных $1 \dots N$, так что корова $i$ находится в позиции $p_i$. Однако этим утром имеется $M$ туннелей ($1 \leq M \leq 10^5$), которые пронумерованы $1 \dots M$, при этом туннель $i$ двунаправленно связывает позиции $a_i$ и $b_i$ и имеет ширину $w_i$ ( $1\le a_i,b_i\le N, a_i\neq bi, 1\le w_i\le 10^9$ ).

В любой момент времени две коровы, расположенные на противоположных концах туннеля могут параллельно поменяться позициями через него. Коровы могут таким образом меняться позициями сколько угодно раз пока корова $i$ не окажется в позиции $i$ для $1 \leq i \leq N$.

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

ОЦЕНИВАНИЕ:

Тесты 3-5 удовлетворяют ограничениям $N,M\le 1000.$
Тесты 6-10 не имеют дополнительных ограничений.

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

Первая строка содержит два целых числа $N$ и $M$.

Вторая строка содержит $N$ целых чисел $p_1, p_2, \dots, p_N$. Гарантируется, что $p$ есть перестановка чисел $1\ldots N.$

Для каждого $i$ между $1$ и $M$, строка $i+2$ содержит целые числа $a_i$, $b_i$, и $w_i$.

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

Одно целое число: наибольшая минимальная ширина туннеля, в которую поместится коров во время процесса сортировки. Если коровы не используют туннели во время сортировки выведите $-1$.

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

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

Loan Repayment#90112

Фермер Джон должен Беси $N$ галлонов молока ($1\le N\le 10^{12}$). Он должен вернуть ей молоко в течение $K$ дней. Однако он не хочет отдавать молоко слишком быстро. С другой стороны, он должен показывать прогресс в возвращении долга. Поэтому он должен возвращать Беси не менее $M$ галлонов молока ($1\le M\le 10^{12}$) каждый день.

ФД собирается делать так. Он выбирает положительное целое число $X$. А затем повторяет следующую процедуру каждый день:

Предположим, что ФД уже отдал Беси $G$ галлонов молока, он вычисляет $\frac{N-G}{X}$ с округлением вверх. Назовём это число $Y$.
Если $Y$ меньше чем $M$, то устанавливает $Y$ равным $M$.
Даёт Беси $Y$ галлонов молока.

Определите максимальное $X$ такое, что если ФД будет следовать этой процедуре, то ФД отдаст Беси не менее $N$ галлонов молока после $K$ дней ($1\le K\le 10^{12}$).

ОЦЕНИВАНИЕ:

Тесты 2-4 удовлетворяют ограничению $K\le 10^5.$
Тесты 5-11 не имеют дополнительных ограничений.

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

Единственная строка ввода содержит три разделённых пробелом целых положительных числа $N$, $K$, $M$ удовлетворяющих $K\cdot M<N$.

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

Выведите наибольшее положительное целое число $X$ такое, что ФД отдаст Беси не менее $N$ галлонов молока используя описанную выше процедуру.

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

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

Milking Order#90027

$N$ коров ($1 \leq N \leq 10^5$), фермера Джона, пронумерованных $1 \ldots N$, разработали социальную иерархию, в соответствии с которой ФД доит их каждое утро.

ФД сделал $M$ наблюдений об этой структуре ($1 \leq M \leq 50,000$). Каждое наблюдение - упорядоченный список некоторых из его коров, указывающий что их нужно доить именно в таком порядке. Например список 2 5 1 означает, он должен подоить корову 2, некоторое время спустя - корову 5 и некоторое время после - корову 1.

Наблюдения ФД приоритезированы, поэтому его цель - максимизировать значение $X$ так, чтобы выполнились условия первых $X$ наблюдений. Если несколько порядков дойки могут удовлетворять $X$ наблюдениям, он выбирает тот, в котором корова с меньшим номером доится раньше. Иными словами, если несколько порядков дойки удовлетворяют этим условиям, ФД выбирает лексикографически наименьший. Порядок $x$ является лексикографически меньшим, чем порядок $y$, если для некоторого $j$, , $x_i = y_i$ для всех $i < j$ и $x_j < y_j$ (другими словами два порядка идентичны до некоторой точки, в которой $x$ меньше чем $y$).

Помогите ФД определить наилучший порядок дойки его коров.

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

Первая строка содержит числа $N$ и $M$. Каждая из следующих $M$ строк описывает одно наблюдение. Строка $i+1$ описывает наблюдение $i$ и начинается с количества коров $m_i$ в этом наблюдении, за которым следует список из $m_i$ целых чисел, определяющих порядок коров в этом наблюдении. Сумма $m_i$ не превышает $200,000$.

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

Выведите $N$ разделённых пробелом целых чисел дающих перестановку чисел of $1 \ldots N$, содержащую порядок в котором ФД должен доить своих коров.

Бинарный поиск по ответу графы Топологическая сортировка

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

Convention#89997

На ферме Джона состоится съезд по поеданию травы.

Коровы со всего мира прибывают в местный аэропорт, чтобы посетить съезд и поесть траву. А именно $N$ ($1 \leq N \leq 10^5$) коров прибывают в аэропорт, и корова $i$ прибывает в момент времени $t_i$ ($0 \leq t_i \leq 10^9$). ФД организовал $M$ ($1 \leq M \leq 10^5$) автобусов для транспортировки коров из аэропорта. Каждый автобус может вместить до $C$ ($1 \leq C \leq N$) коров. ФД ждёт вместе с автобусами в аэропорту и собирается распределить прибывающих коров по автобусам. Автобус убывает из аэропорта в момент, когда прибывает последняя корова. ФД хочет, чтобы прибывающие коровы не ждали в аэропорту слишком долго. Каково наименьшее значение максимального времени ожидания из всех коров, если ФД оптимально назначит их по автобусам. Время ожидания коровы есть разность между временем её прибытия и временем отправления автобуса, в который она распределена.

Гарантируется, что $MC \geq N$.

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

Первая строка содержит три разделённых одиночными пробелами целых числа $N$, $M$, $C$. Следующая строка содержит $N$ разделённых одиночными пробелами целых чисел, представляющих время прибытия каждой коровы.

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

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

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

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

Sabotage#89938

Фермер Пауль решил саботировать доильное оборудование Фермера Джона. Доильное оборудование составляет ряд из N (3 <= N <= 100,000) доильных машин, где i-ая машина производит M_i единиц молока. ФП планирует отсоединить непрерывный блок этих машин от i-ой до j-ой (2 <= i <= j <= N-1). Заметим, что ФД не собирается отключать первую и последнюю машины, поскольку это очень заметно и легко обнаружить. Цель ФП – минимизировать среднее производство молока оставшимися машинами.
Пожалуйста, помогите ФД определить минимальное среднее значение производства молока оставшимися машинами в случае оптимальных действий ФП.
PROBLEM NAME: sabotage
Формат входных данных
* Строки 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит M_i.
Формат выходных данных
* Строка 1: Минимально возможное среднее, которого может достичь ФП, округлённое до 3 цифр после десятичной точки и с выводом 3 цифр после десятичной точки.
Примечание
Оптимальное решение – удалить машины 7 т 8 оставив 5 1 2, среднее которых равно 8/3.

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

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

Cross Country Skiing#89932

Лыжная трасса описана решёткой из M x N высот (1 <= M,N <= 500), каждая из высот в диапазоне 0 .. 1,000,000,000.
Некоторые из этих ячеек обозначены как точки маршрута гонки. Организаторы хотят назначить маршруту рейтинг трудности D так, чтобы корова могла попасть в любую точки маршрута из любой другой точки маршрута, последовательно перемещаясь между соседними ячейками, абсолютная разность высот которых не превышает D. Две ячейки считаются соседними, если они граничат по стороне (в направлении на север, юг, запад или восток одна от другой). Рейтинг трудности маршрута это минимальное значение D такое, что все точки маршрута взаимно достижимы при выполнении вышеописанного требования.
PROBLEM NAME: ccski
Формат входных данных
* Строка 1: Целые числа M и N.
* Строки 2..1+M: Каждая из этих M строк содержит N целых высот.
* Строки 2+M..1+2M: Каждая из этих M строк содержит N величин 0 или 1, 1 указывает, что данная высота – точка маршрута гонки.

Формат выходных данных
* Строка 1: Рейтинг трудности маршрута (минимальное значение D такое, что все точки маршрута взаимно достижимы)
Примечание
Если D = 21, то все 3 точки маршрута взаимно достижимы. Если D<21 верхняя правая точка не достижимы из других двух.

Бинарный поиск по ответу графы Обход в ширину

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

Tractor#89878

Одно из полей Фермера Джона весьма холмисто. И он хочет купить новый трактор для работы на этом поле. Поле описывается решеткой из N x N (1 <= N <= 500) неотрицательных целых высот ячеек. Трактор может перемещаться из ячейки в соседнюю (на один шаг на север, юг, запад или восток), с разницей их высот D ровно за D единиц денег.
ФД хочет заплатить достаточно, так чтобы его трактор, начиная с некоторой ячейки поля мог посетить как минимум половину ячеек поля. Если число ячеек в поле - нечетное, то половина, округленная вверх.
Определите минимальную стоимость покупки трактора способного выполнить эту задачу.

PROBLEM NAME: tractor
Формат входных данных
* Строка 1: Значение N.
* Строки 2..1+N: Каждая строка содержит N разделенных одиночными пробелами неотрицательных целых чисел (каждое не более миллиона), определяющих строку поля ФД.
Формат выходных данных
* Line 1: Минимальная стоимость трактора, который способен объехать не менее половины этого поля.
Примечание
Трактор стоимостью 3 способен перемещаться из ячейки с высотой 0 в ячейку с высотой 3. Поэтому он может посетить все ячейки с высотами 0 и 3. Вместе они представляют не менее половины фермы.

Бинарный поиск по ответу Обход в ширину Поиск компонент связности

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

Partitioning the Farm#89873

Ферма Джона разделена на N x N квадратов пастбищ (2<=N<=15). Снаружи есть изгородь, но между пастбищами коровы могут переходить свободно.
ФД решил построить изгороди, чтобы отделить коров друг от друга. Каждая изгородь может быть горизонтальной или вертикальной через всю ферму, и изгороди не могут проходить через пастбища. По финансовым соображениям ФД может построить не более чем K изгородей (1 <= K <= 2N - 2).
ФД хочет построить изгороди так, чтобы минимизировать размер наибольшей из получившихся в результате групп коров (две коровы находятся в одной группе, если они могут посетить друг друга, не пересекая никакую изгородь).
По заданным количествам коров на пастбищах, вычислите размер наибольшей группы коров, если ФД построит изгороди оптимально.

PROBLEM NAME: partition
Формат входных данных
* Строка 1: Два целых числа, N and K
* Строки 2..1+N: Имеется N чисел на каждой строке, описывающих количества коров в каждом пастбище одной строки фермы. На каждом пастбище не менее 0 и не более 1000 коров.

Формат выходных данных
* Строка 1: Минимально возможный размер наибольшей группы коров.
Примечание
ФД должен построить изгороди между колонками 2 и 3 и между строками 2 и 3. В результате получится 4 группы по 4 коровы в каждой.

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

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

Flowerpot#89839

Фермер Джон нуждается в Вашей помощи в организации поливки. Вам даны координаты N поливателей (1 <= N <= 100,000) на декартовой плоскости, где y представляет высоту поливателя. А x - его местоположение на прямой.

Каждая капля воды падает вертикально (по направлению к оси x) со скоростью 1 единица в секунду. Вы должны разместить клумбу (шириной W) с цветами так, чтобы разница во времени, когда первая капля упадет на клумбу и когда последняя капля упадет на клумбу была не менее некоторой величины D. Капля, которая попадает на границу клумбы, считается попавшей на клумбу.
Вам даны значения D, а также местоположения и высоты поливателей. Вычислите минимально возможную величину W.
PROBLEM NAME: fpot
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа N и D. (1 <= D <=1,000,000) * Строки 2..1+N: Строка i+1 содержит разделенные пробелом координаты (x,y) поливателя i, все величины в интервале 0...1,000,000.
Формат выходных данных
* Строка 1: Одно целое число, минимально-возможную ширину клумбы. Выведите -1, если невозможно построить клумбу, которая получала бы воду в течение не менее D единиц времени
Примечание
Клумба шириной 2 возможна, если разместить ее с x от 4 до 6. Тогда она будет получать капли с поливателей #1 и #3, втечение времени 10-3 = 7.

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

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

Медиана объединений#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—Войти и решать

Японский кроссворд#55499

Наиболее известная игра, дошедшая до нас из Японии – это Судоку. Новая игра должна затмить ее славу. Про нее известно следующее. Нам дан квадрат, разделенный сеткой на n×n клеток, а каждая клетка содержит картинку одного из k типов. Игрок должен переместить их, чтобы получить максимально возможное число одинаковых первых рядов (два ряда считаются одинаковыми, если оба заполнены одинаковыми картинками и в одинаковом порядке). По виду таблицы определите, сколько одинаковых рядов в ней можно сложить (если менять картинки как угодно).

Например, если нам дана такая таблица:

одно из результирующих состояний в игре будет:

Входные данные
Первая строка входных данных содержит два числа n (1≤n≤40000) и k (1≤k≤50000). Каждая из следующих k строк содержит число картинок в таблице каждого из k типов. Все числа больше 0, их сумма в точности равна n².

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

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

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

Даша и кризис#55464

Даша имеет n ювелирных украшений. Каждое украшение имеет стоимость wi и значимость для Даши vi. В связи с финансовым кризисом Даша решила продать некоторые украшения и сохранить только k из имеющихся. Чтобы решить, что именно сохранить, Даша вводит параметр важности для набора из выбранных k украшений, который вычисляет по следующей формуле:
$\frac{\sum_{j=1}^k v_i}{\sum_{j=1}^k w_i}$

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

Входные данные
Первая строка ввода содержит числа n – количество ювелирных изделий у Даши и k – количество ювелирных изделий, которые планируется оставить (1 ≤ k ≤ n ≤ 100000).

В следующих n строках содержатся по два числа – v_i и w_i(0 ≤ v_i ≤ 10⁶,1≤w_i≤10⁶, обе суммы всех значений vi и wi не превосходят 10⁷ каждая).

Выходные данные
Выведите k чисел – номера ювелирных украшений, которые следует оставить. Если существует несколько решений, то выведите любое из них.

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

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

Электрик-ковбой Джо#55414

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

Вот и сейчас ему поручили проверить два стоящих на расстоянии d друг от друга столба высоты h₁ и h₂ соответственно. Чтобы убедиться, что все хорошо, Джо должен побывать на вершинах обоих столбов.

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

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

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

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

Входные данные
Входной файл содержит четыре положительных целых числа: d, h₁, h₂ и l - расстояние между столбами, высоту первого и второго столбов и максимальный допустимый перепад высот при прыжке, соответственно. Все числа во входном файле не превышают 10⁶.

Выходные данные
Выведите ответ с максимальной возможной точностью. Ответ будет проверяться с точностью до 10⁻⁵.

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

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

Медиана объединений#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—Войти и решать

Поезда#55205

В связи с увеличившимся количеством аварий на железной дороге, руководство дороги решило изменить график движения поездов. Анализ состояния полотна дороги показал, что оптимальным является следующий график движения: сначала T₁ минуту поезд идет со скоростью V₁ метр в минуту, потом T₂ минуты со скоростью V₂ метра в минуту, ..., наконец, T_N минут со скоростью V_N метрв в минуту. При этом на любом из этих участков поезд может стоять (V_i = 0).

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

Входные данные
Первые две строки входных данных содержат числа L и N (100 ≤ L ≤ 10000, 1 ≤ N ≤ 1000). Далее идет N строк, задающих график движения поезда, каждая строка содержит пару чисел T_i и V_i (1 ≤ T_i ≤ 1000, 0 ≤ V_i ≤ 1000).

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

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

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