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

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$, с которой должна приземлится корова, для того, чтобы взорвать все стоги сена. Ответ округлить и вывести с одним знаком после десятичной точки.

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

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

Counting Haybales#90366

Фермер Джон разместил свои $N$ ($1 \leq N \leq 100,000$) стогов сена в различных точках одномерной дороги вдоль его фермы. Вам требуется ответить на $Q$ ($1 \leq Q \leq 100,000$) запросов, о том сколько стогов сена находится внутри указанного участка дороги.

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

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

Следующая строка содержит $N$ различных целых чисел, каждое в интервале $0 \ldots 1,000,000,000$, указывающих местоположения стогов сена.

Каждая из последующих $Q$ строк содержит два целых числа $A$ и $B$ ($0 \leq A \leq B \leq 1,000,000,000$) задающих запрос на количество стогов сена между $A$ и $B$, включительно.

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

Вы должны вывести $Q$ строк. Для каждого запроса выведите количество стогов сена в соответствующем интервале.

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

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

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 коровы в каждой.

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

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

Cow Baseball#89861

N (3 <= N <= 1000) коров Фермера Джона стоят в ряд, каждая в различной позиции на числовой прямой. Они бросают друг другу мяч по кругу в порядке подготовки к важной игре с коровами с соседней фермы.
ФД заметил, что группа из 3 коров (X,Y,Z) делает два успешных броска. Корова X бросает мяч вправо от себя корове Y, а затем корова Y бросает Мяч вправо от себя корове Z. ФД заметил также, что второй бросок получается на расстояние не менее чем первый бросок и не более чем в два раза превышает первый бросок. Посчитайте количество возможных троек коров, которые ФД мог наблюдать.
PROBLEM NAME: baseball
Формат входных данных
* Строка 1: Количество коров, N.
* Строки 2..1+N: Каждая строка содержит целую координату одной коровы (целое число в диапазоне 0..100,000,000).
Формат выходных данных
* Строка 1: Количество троек коров (X,Y,Z), где Y справа от X, а Z справа от Y и расстояние от Y до Z находится между XY и 2XY (включительно), где XY представляет расстояние от X до Y.
Примечание
Три возможных тройки: 1-3-7, 1-4-7, 1-4-10, 4-7-10.

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

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

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.

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

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

Бинарный поиск в подмножестве#84682

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

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

В первой строке — число N (1 ≤ N ≤ 100000) — размер набора.

Во второй строке — N целых чисел (1 ≤ число ≤ 1000000).

В третьей строке — число Q (1 ≤ Q ≤ 100000) — количество запросов.

В следующих Q строках — по одному числу X (1 ≤ X ≤ 1000001).

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

Для каждого запроса выведите ответ на отдельной строке.

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

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

65820#65820

Словом Чемпернауна называется длинная строка, полученная из натуральных чисел, записанных подряд без пробелов и запятых. Так, для десятичной системы счисления слово Чемпернауна начинается с 123456789101112…, а для семеричной – с 1234561011121314151620…
Найдите, какие цифры стоят на заданных местах (индексах) в слове Чемпернауна, записанном в семеричной системе счисления. Например, под индексом 3 находится цифра «4», а под индексом 1 цифра «2» – нумерация начинается с нуля.

Формат входных данных
На вход программе в первой строке подается натуральное число N (N ≤ 1000) – количество индексов, для которых надо определить цифру в записанном в семеричной системе слове Чемпернауна. Во второй строке даётся последовательность из N неотрицательных чисел, разделённых пробелами, каждое из которых не превосходит 2*10⁹ – индексы, для которых надо найти цифру. Нумерация индексов начинается с 0.

Формат выходных данных
Вывести строку из N цифр – цифр, стоящих на заданных местах в слове Чемпернауна, записанном в семеричной системе счисления.

Бинарный поиск значения функции Разные системы счисления

✓ 5✗ 5700средняяВойти и решать

6#65811

В королевстве Полерам расположен длинный линейный сад из N деревьев, стоящих в один ряд (по порядку с запада на восток). У каждого дерева i (нумерация от 1 до N) имеется некоторый урожай a_i — количество собранных яблок (целое число, может быть положительным, нулевым или даже отрицательным, если учитывать затраты или потери).
Королевский интендант хочет упаковывать собранный урожай в большие ящики, рассчитанные ровно на K яблок. Для удобства он рассматривает непрерывные отрезки деревьев [L,R] и проверяет, делится ли сумма (a_L )+ (a_L+1) + … + (aR) на K без остатка. Если делится, то такой отрезок можно упаковать в ящики без недогруза и перегруза.
Требуется найти общее количество таких отрезков [L,R], для которых сумма урожая деревьев на этом участке кратно K, количество яблонь нечётное, а количество собранных яблок - положительное число.
Примечание:
В отрезке [L, R] должно быть выполнено неравенство 1<= L <= R <= N.
Формат входных данных
Первая строка: два целых числа N и K, (1 <= N <= 200000, 1 <= K <= 10⁶).
Вторая строка: N целых чисел a₁, a₂, …, a_N (-10⁶ <= a_i <= 10⁶).
Формат выходных данных
Выведите одно число — количество всех пар (L, R) для которых (a_L )+ (a_L+1) + … + (a_R) делится без остатка на K, количество яблонь нечётное, а количество собранных яблок - положительное число.

Пояснение: в данном примере есть четыре последовательности: (1 + 2), (1 + 2 + 3), (3), (6), в данном случае все с положительным количеством собранных яблок, но только 3 с нечётным количеством яблонь.

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

✓ 4✗ 31900средняяВойти и решать

Летовецкие числа#60944

Летовецкие числа — это положительные целые числа, которые делятся на a, b или c.

Напишите программу, которая находит n-е по счёту летовецкое число.

Формат входных чисел
Программа получает на вход четыре целых положительных числа n, a, b, и c. Каждое число записано в отдельной строке.
Ограничения на входные данные

1 <= n, a, b, c <= 10⁹
1 <= a * b * c <= 10¹⁸
Гарантируется, что результат находится в диапазоне [1, 2 * 10⁹].

Формат выходных чисел
Ваша программа должны вывести одное число - n-е по счёту летовецкое число.

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

✓ 7✗ 2931 100средняяВойти и решать

Мастерство фотографии#60647

Фотографа попросили сделать фотосессию группы детей для выпускного альбома в детском саду. В числе прочих, он должен сделать групповой снимок, на котором должны присутствовать все дети одновременно. Фотограф считает, что для красивой фотографии группы требуется очень тщательно расставить детей в кадре. В частности, с его точки зрения, группа должна расположиться как можно компактнее по ширине, то есть количество людей в самом длинном ряду на фотографии должно быть как можно меньше.
Для гармоничного расположения детей фотограф размещает детей не более чем в четыре ряда. Девочек он располагает либо во втором ряду, сидящими на стульчиках, либо стоящими в третьем ряду. Мальчиков он размещает либо в первом ряду, сидящими на корточках, либо в четвёртом ряду, стоящими на стульчиках. Группа состоит из a мальчиков и b девочек. В студии есть стулья в количестве c штук. Какие-то ряды могут быть пустыми. Все стулья использовать не обязательно.
По заданным числам a, b и c требуется определить, какого наименьшего по ширине расположения группы сможет добиться фотограф.
Формат входных данных
Программа получает на вход три целых неотрицательных числа a, b и c, записанных в отдельных строках — количество мальчиков, девочек и стульев соответственно. Все числа не превосходят 10¹⁸ .
Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Вывести одно целое число — минимальную ширину группы, которую сможет организовать фотограф.

Замечание
Во всех примерах в условии группа состоит из 9 мальчиков и 15 девочек.
В первом примере стульев нет, поэтому все девочки стоят, все мальчики сидят на корточках, общая ширина группы 15.
Во втором примере есть 4 стула. Можно посадить 4 девочек во втором ряду на эти стулья, остальные 11 девочек будут стоять в третьем ряду. Все мальчики будут сидеть на корточках в первом ряду. Общая ширина группы 11.
В третьем примере есть 7 стульев. Тогда есть два способа получить группу ширины 9. Например, можно посадить на все стулья девочек, тогда в первом ряду будет 9 мальчиков, во втором ряду будет 7 девочек, в третьем ряду 8 девочек. Либо можно посадить на стулья 6 девочек и поставить одного мальчика в четвёртый ряд. Тогда получим 8 мальчиков в первом ряду, 6 девочек во втором, 9 девочек в третьем и 1 мальчика в четвёртом. В любом из этих двух случаев ширина группы равна 9.
В четвёртом примере стульев много и есть несколько способов организовать группу ширины 8. Один из способов такой: посадим на корточки 4 мальчика в первом ряду, далее посадим 8 девочек на стулья во втором ряду, оставшиеся 7 девочек встанут в третьем и 5 мальчиков поставим на стульчики в четвёртом.

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

✓ 12✗ 391 100средняяВойти и решать

Две сестры#60646

Аполлинария Прокофьевна и Белла Прокофьевна — две сестры-пенсионерки. Аполлинарии Прокофьевне каждый день необходимо принимать одну таблетку от забывчивости. К сожалению, этот режим она не соблюдает и вспоминает о лекарстве только раз в a дней (то есть приняв лекарство сначала в первый день, в следующий раз она примет его в день номер 1 + a). Белле Прокофьевне каждый день необходимо принимать одну таблетку от жадности. Ко всеобщему огорчению, и её болезнь сильнее лекарства, поэтому каждый день она глотает b таблеток. Внешне эти таблетки выглядят совершенно одинаково и каждая из сестёр считает, что вот этот пузырёк с n пилюлями именно её. На сколько дней им хватит этого количества лекарств?

Формат входных данных
Три строки входных данных содержат три целых числа a, b (1 ≤ a, b ≤ 100) и n (1 ≤ n ≤ 10¹⁸).
Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Программа должна вывести одно число — ответ на задачу.

Замечание
В первом примере Аполлинария Прокофьевна принимает по одной таблетке раз в два дня (начиная с первого), Белла Прокофьевна принимает по три таблетки каждый день. В пузырьке 12 таблеток.
В первый день Аполлинария принимает одну таблетку, а Белла — три. В пузырьке осталось восемь пилюль.
Во второй день Аполлинария забывает принять таблетку, а Белла опять съедает три. В пузырьке осталось пять пилюль.
В третий день Аполлинария принимает одну таблетку, а Белла — три. В пузырьке осталась последняя пилюля, ещё на один день этого количества сёстрам не хватит.
Во втором примере начального количества таблеток не хватит даже на один день.

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

✓ 102✗ 439800средняяВойти и решать

Качели#60586

Трое друзей — Аня, Боря и Саша — пришли на детскую площадку, чтобы покачаться на качеляхбалансире. Качели представляют собой длинную балку, закреплённую в центре, на которую дети садятся с разных концов.

Массы детей равны A, B и C кг. Чтобы держать баланс на качелях, разница масс на двух концах качелей должна быть не более D кг. Друзьям повезло: рядом с площадкой оказалась груда достаточно тяжёлых камней. Один из детей может взять с собой любой камень, чтобы сделать разность масс на концах качелей допустимой. Помогите друзьям определить минимальную массу камня, благодаря которому они смогут покачаться на качелях.

Формат входных данных
Программа получает на вход три числа A, B, C, записанных в отдельных строках, — массы друзей. В четвёртой строке записано число D — наибольшая допустимая разница масс на концах качелей. Все числа — целые, положительные и не превосходящие 10⁹ .

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

Замечание
В первом примере Аня и Саша сядут на одну сторону, их суммарная масса будет равна 65 кг. На другую сторону сядет Боря, взяв 15-килограммовый камень, тогда масса Бори с камнем составит 55 кг. Разница весов на концах качелей примет значение 10 кг. Во втором примере Аня и Боря сядут на одну сторону (50 кг), Саша — на другую сторону (45 кг). Разница весов будет равна 5 кг, поэтому камень не понадобится.

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

✓ 117✗ 246600лёгкаяВойти и решать