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

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 верхняя правая точка не достижимы из других двух.

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

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

Cow Lineup#89882

N коров (1 <= N <= 100,000) Фермера Джона выстроились в ряд. Каждая корова идентифицирована числом в диапазоне 0...1,000,000,000; которое обозначено B(i). Множество коров могут иметь один и тот же идентификатор.
ФД думает, что ряд коров будет впечатлять больше, если бы там был большой непрерывный участок, на котором все коровы имеют одинаковый идентификатор. Для того чтиобы создать такой участок, ФД выбирает до K идентификаторов и удаляет из своего ряда всех коров имеющих эти идентификаторы.
Помогите ФД вычислить длину наиблоьшего последовательного блока коров с одним и тем же идентификатором, после такого удаления.

PROBLEM NAME: lineup
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: N и K.
* Строки 2..1+N: Строка i+1 содержит идентификатор B(i).
Формат выходных данных
* строка 1: Размер наибольшего непрерывного блока коров с одним идентификатором, который может создать ФД.
Примечание
Удалив всех коров с идентификатором 3, ФД получит ряд: 2, 7, 7, 7, 7, 5, 7. Имеется наибольший непрерывный участок из четырех чисел 7.

"Два указателя"

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

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.

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

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

Cow Lineup#89804

Problem 2: Cow Lineup [Brian Dean]
Фермер Джон нанял профессионального фотографа, чтобы сфотографировать некоторых из своих коров. Поскольку у него есть коровы разных пород, он хочет иметь фото как минимум одной коровы каждой породы.
N коров ФД выстроены в ряд (позиция каждой указывается x-координатой) и целочисленным номером породы. ФД планирует сделать фотографию непрерывного участка коров. Стоимость фотографии равна ее размеру – то есть разностью между максимальной и минимальной x-координатами коров, представленных на фотографии.
Помогите ФД вычислить минимальную стоимость фотографии, в которой находится по крайней мере одна корова каждой породы.
PROBLEM NAME: lineup
Формат входных данных
* Строка 1: количество коров, N (1 <= N <= 50,000).
* Строки 2..1+N: Каждая строка содержит два числа, разделенных одиночным пробелом, указывающих x-координату и номер породы одной коровы. Оба числа не превосходят миллиард.
Формат выходных данных
* Строка 1: Минимальную стоимость фотографии, содержащей не менее одной коровы каждой породы.
Примечание
Диапазон от x=22 до x=26 (длиной 4) содержит коровы всех пород (1,3,7).

"Два указателя"

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

Moo Sick#89799

Problem 3: Moo Sick [Rob Seay]
Каждый знает, что коровы любят слушать музыку. Великий композитор Мууцарт однажды открыл, некоторые последовательности нот действуют на коров угнетающе. Поэтому их нужно избегать во всех композициях для коров.
Фермер Джон, не знакомый с этим фактом, решил проигрывать свою любимую песню через громкоговорители в амбаре. Ваша задача – определить все угнетающие последовательности нот в его песне, чтобы оценить, насколько она вредна для коров.
Песня, которую озвучивает ФД, представляет собой последовательность из N нот, каждая в диапазоне от 1 до 88. Угнетающая последовательность состоит из С (1<=C<=10) различных нот, также целых чисел от 1 до 88. Однако, если ноты транспонированы (увеличены или уменьшены на одну и ту же величину), или переупорядочены, то эта последовательность нот все равно остается угнетающей. Например, если «4 6 7» - угнетающая последовательность нот, то последовательности «3 5 6» (транспонирована на -1), «6 8 9» (транспонирована на +2), «6 4 7» (переупорядочена), «5 3 6» (транспонирована и переупорядочена) , также являются угнетающими.
Таким образом, угнетающей последовательностью нот являются C подряд идущих нот, удовлетворяющих вышеописанному критерию. Поэтому она однозначно определяется своим стартовым положением в песне. Определите стартовое положение всех угнетающих последовательностей.
PROBLEM NAME: moosick
Формат входных данных
* Строка 1: Одно целое число: N.
* Строки 2..1+N: N нот в песне ФД, по одной ноте на строке.
* Строка 2+N: Одно целое число: C.
* Строки 3+N..2+N+C: C нот определяющих угнетающую последовательность. Все транспозиции и переупорядочивания также угнетающие последовательности.

Формат выходных данных
* Строка 1: Количество, K, угнетающих последовательностей, которые есть в песне ФД. Заметим, что различные экземпляры угнетающих последовтельностей могут перекрываться друг с другом.
* Строки 2..1+K: Каждая строка указывает начальную позицию угнетающей последовательности (1 – первая нота в песне ФД, N - последняя). Эти начальные позиции должны указываться в порядке возрастания.
Примечание
Две угнетающих последовательности встретились в песне ФД и они перекрываются в одной ноте. Первая – 8,5,7 (транспонирована на 1 и переупорядочена), начинается с позиции 2, а вторая 7,9,10 (транспонирована на 3) , начинается с позиции 4.

Использование сортировки Поиск подстроки в строке

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

Выбор участка - 1 (24-25)#89300

Маша хочет построить дачу на одной приглянувшейся ей улице. Эта улица имеет длину n, то есть состоит из n одинаковых идущих подряд участков. На каждом участке указан уровень шума от 1 до 9 (где 1 — тишина, 9 — очень шумно).

Маша хочет найти участок с уровнем шума ровно 1 (тихий участок), который находится максимально далеко от шумных участков. Шумным считается участок с уровнем шума 7 или больше.

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

Если таких участков несколько, выбрать участок с наименьшим номером.

Гарантируется, что есть хотя бы один тихий участок (уровень шума 1) и хотя бы один шумный участок (уровень шума ≥ 7).

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

В первой строке натуральное число n (1 ≤ n ≤ 6 000 000)
Во второй строке n чисел от 1 до 9 через пробел

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

Номер участка и расстояние до ближайшего шумного (через пробел)

Линейный поиск

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

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

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

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

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

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

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

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

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

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

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

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

Ищем даты#67734

В заданном тексте, состоящем не более чем из 100 строк, найдите все даты в формате DD-MM-YYYY. Выведите эти даты в столбик в порядке их встречаемости в тексте. Валидность даты проверять не нужно.

Формат даты: DD-MM-YYYY, где:

DD - день (две цифры, 01-31)
MM - месяц (две цифры, 01-12)
YYYY - год (четыре цифры, обычно 0000-9999)
Разделитель: дефис "-"

Формат входных данных
В первой строке записано натуральное число N - количество строке текста. Далее, идут сами строки текста.

Формат выходных данных
Выведите все искомые даты, каждая дата в отдельной строке.

Конечные автоматы Поиск подстроки в строке Строки

✓ 2✗ 41 000средняяВойти и решать

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средняяВойти и решать

Места в ряду#60648

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

Формат входных данных
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 2 · 10⁵ ) — количество мест в ряду.
Вторая строка содержит целое число k (1 ≤ k ≤ n) — количество приходящих людей.
Третья строка содержит строку s длины n, состоящую из символов «0» и «1» и задающую первоначальную рассадку. Занятые места обозначаются единицами, пустые — нулями. Гарантируется, что в строке s содержится не менее k нулей.
Формат выходных данных
Программа должна вывести k чисел — номера выбранных мест в порядке прихода новых людей.

Замечание
В первом примере первоначально заняты места 1, 2 и 6 (рисунок А).
Если первый пришедший будет двигаться с левой стороны ряда, он пройдёт мимо 1 и 2 места, прежде чем доберётся до свободного места с номером 3. Если же он будет двигаться с правой стороны ряда, то ему понадобится пройти мимо одного места с номером 6, после чего он сможет занять место 5. Именно это место он и выберет (рисунок Б).
Второй пришедший может занять либо место с номером 3, двигаясь с левой стороны и проходя мимо двух занятых мест 1 и 2, либо место с номером 4, двигаясь с правой стороны и проходя мимо двух занятых мест 6 и 5. Поскольку в обоих случаях ему нужно пройти мимо двух занятых мест, он будет двигаться с левой стороны и займёт место с номером 3.
Во втором примере в ряду 6 мест, второе и пятое места изначально уже заняты, заходят ещё 3 человека. Первый заходящий человек будет выбирать между первым и шестым местами, заходя с левого или правого края соответственно. В обоих случаях ему придётся пройти мимо нуля занятых мест, поэтому он решит зайти слева и сесть на 1 место. Второй человек будет выбирать между третьим и шестым местами. В первом случае ему придётся идти мимо двух занятых мест, во втором — мимо нуля, поэтому он выберет зайти справа — 6 место. Третий человек будет выбирать между третьим и четвертым местами. В обоих случаях ему придётся пройти мимо двух занятых мест, поэтому он выберет зайти слева — 3 место.

"Два указателя"

✓ 9✗ 241 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 мальчиков поставим на стульчики в четвёртом.

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

✓ 11✗ 341 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✗ 438800средняяВойти и решать

Качели#60586

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

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

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

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

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

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

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

Речные прогулки#60127

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

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

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

Формат входных данных
Первая строка входных данных содержит целое число \(n\) (\(3\le n\le 2\cdot 10^9\)) — общее количество пристаней на маршруте. Вторая строка содержит число \(a\) — время подъёма судна на один километр вверх по течению реки, третья строка содержит число \(b\) — время спуска на один километр вниз по течению, \(1\le b < a\le 2\cdot 10^9\).

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

Примечание
В примере из условия начальным пунктом маршрутов нужно сделать пристань 3. Тогда вверх по течению судно поднимется за \((3-1)\times 7=14\) минут, а вниз по течению реки спустится за \((8-3)\times3=15\) минут. Разница в продолжительности маршрутов составит 1, меньшей разности в данном примере достичь невозможно.

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

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