Бинарный поиск

156 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Социальное дистанцирование#39380
Болеющие коровы решили помочь Фермеру Джону.
Для того, чтобы ограничить передачу болезни, N (2 ≤ N ≤ 105) коров ФД решили попрактиковаться в "социальном дистанцировании" и "распределились" по ферме. Ферма представлена в виде прямой линии, с M взаимно не имеющими общих точек интервалами (1 ≤ M ≤ 105), на которых растёт трава. Коровы хотят расставиться в точках с различными координатами, каждая точка покрыта травой, так, чтобы максимизировать значение D. Где D представляет расстояние между ближайшей парой коров. Помогите коровам определить наибольшее значение D.

Входные данные
Первая строка ввода содержит N и M. Каждая из следующих M строк описывает интервал двумя целыми числами a и b, где 0 ≤ a ≤ b ≤1018. Никакие два интервала не перекрываются и не касаются своими конечными точками. Корова, стоящая на конечной точке интервала считается стоящей на траве.
Выходные данные
Выведите наибольшее возможное значение D такое, что все пары коров не менее чем на D единиц друг от друга. Гарантируется, что существует решение с D>0.
Примеры
№ Входные данные Выходные данные
1 5 3
0 2
4 7
9 9		 2
Бинарный поиск по ответу
✓ 6✗ 871 200средняяВойти и решать
Эльфы и олени#38920
Скоро новый год и Санта-Клаус уже начал готовить свою волшебную оленью упряжку, на которой он развозит подарки детям. Известно, что упряжку везут несколько волшебных оленей, на каждом из которых едут два эльфа.

Но волшебные олени – строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью ai, а каждый эльф – темпераментом bi. Два эльфа j и k могут ехать на i-м олене в том и только в том случае, если либо bj < ai < bk, либо bk < ai < bj.

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

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

Входные данные
В первой строке вводятся два целых числа m и n – количество оленей и эльфов, соответственно ( 1 ≤ m, n ≤ 100 000).

Вторая строка содержит m целых чисел ai – строптивость оленей ( 0 ≤ ai ≤ 109). В третьей строке записаны n целых чисел bi – темперамент эльфов ( 0 ≤ bi ≤ 109).

Выходные данные
В первой строке  выведите одно число k – максимальное количество оленей, которое Санта-Клаус может включить в свою упряжку. В следующих k строках выведите по три целых числа: di, ei, 1, ei, 2 – для каждого оленя в упряжке выведите его номер и номера эльфов, которые на нем поедут. Если решений несколько, выведите любое.

И эльфы, и олени пронумерованы, начиная с единицы, в том порядке, в котором они заданы во входных данных.
Примеры
№ Входные данные Выходные данные
1 4 6
2 3 4 5
1 3 2 2 5 2		 2
1 1 2
3 4 5
Бинарный поиск по ответуБыстрая сортировкаЖадный алгоритмЭвристические методы
✓ 18✗ 571 100средняяВойти и решать
Чет-нечет#38474
Дана возрастающая последовательность целых чисел 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ... Она сформирована следующим образом: берется одно нечетное число, затем два четных, затем три нечетных и так далее. Выведите N-й элемент этой последовательности.

Входные данные
Одно целое число N (1 ≤ N ≤ 10100).

Выходные данные
Выведите одно целое число - N-й элемент последовательности.
Примеры
№ Входные данные Выходные данные
1 1 1
2 4 5
"Длинная" арифметикаБинарный поиск по ответу
✓ 19✗ 1021 000средняяВойти и решать
Выбор цветов для букета#38384
Володя хочет красиво поздравить свою жену с годовщиной их свадьбы и собирается подарить ей букет из n цветов.

Придя в цветочный магазин, Володя обнаружил, что букет можно составлять из цветов m различных видов, причём количество цветов каждого вида не ограничено. Володя знает, что от первого цветка i-го вида в букете его супруга становится счастливее на ai, а от каждого следующего цветка  
такого вида она становится счастливее на bi. То есть, если в букете xi > 0 цветов вида i, то от цветов этого вида жена Володи становится счастливее на ai + (xi − 1) · bi.

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

Формат входных данных
В первой строке вводятся два целых числа n и m (1 ≤ n ≤ 109 , 1 ≤ m ≤ 100 000) — требуемое 
количество цветов в букете и количество доступных видов цветов.
Каждая из следующих m строк описывает i-й вид цветов и содержит два целых числа ai и bi (0 ≤ ai , bi ≤ 109 ) — увеличение счастья от первого цветка i-го вида и увеличение счастья от каждого последующего цветка этого вида.

Формат выходных данных
В единственной строке выведите одно число — максимальное увеличение счастья, которое может получить жена Володи от букета из n цветов.
 
Примеры
№ Входные данные Выходные данные
1 4 3
5 0
1 4
2 2		 14
2 5 3
5 2
4 2
3 1		 16
Бинарный поиск в массивеПрефиксные суммы(минимумы, ...)
✓ 6✗ 331 000средняяВойти и решать
Словарь#38196
У Васи на клавиатуре не работает клавиша пробел. Поэтому все тексты он теперь набирает слитно. Напишите программу, которая будет разделять набранный Васей текст на слова из данного словаря.

Входные данные
Сначала на вход программы поступает текст, введенный Васей – одна строка из не более чем 100 латинских строчных букв. В следующей строке входных данных задается значение N – количество слов в словаре (N – натуральное число, не превосходящее 2000). В следующих N строках записаны слова из словаря – по одному слову в  строке, каждое слово содержит не более 20 латинских строчных букв. Слова записаны в алфавитном порядке.


Выходные данные
Выведите Васин текст с пробелами между словами (пробел после последнего слова допустим). Если возможно несколько вариантов разбиения строки на слова, выведите  любой их них. Гарантируется, что хотя бы один способ разбиения строки на словарные слова существует.
Примеры
№ Входные данные Выходные данные
1 whatcanido
6
a
an
can
do
i
what		 what can i do 
Бинарный поиск в массивеДинамическое программирование: один параметр
✓ 7✗ 17800средняяВойти и решать
Acowdemia#38128
Беси опубликовала N статей (1 <= N <= 105). i-ая статья процитирована ci раз (0 <= ci <= 105).
h-индекс это наибольшее число h такое, что имеется не менее h статей, каждая из которых цитируется не менее чем h раз. Например, есть 4 статьи с количествами цитат (1,100,2,3), тогда h-индекс равен 2, а при количествах цитат (1,100,3,3) h-индекс равен 3.

Чтобы повысить свой h-индекс, Беси планирует написать K обзорных статей (0 <= K <= 105), каждая из которых цитирует несколько ее прошлых статей. Беси имеет право цитировать не более L статей в каждом обзоре (0 <= L <= 105). Конечно, никакая статья не может цитироваться более одного раза в одном обзоре (однако статья может цитироваться в нескольких обзорах).

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

Входные данные
Первая строка содержит N, K, L. Вторая строка содержит N разделённых пробелом целых чисел c1,...,cN.

Выходные данные
Максимальный h-индекс.
 
Примеры
№ Входные данные Выходные данные Пояснение
1 4 4 1
1 100 1 1		 3 В этом примере Беси может написать 4 обзорные статьи, в каждой из которых можно процитировать не более 1 статьи. Если процитировать первую и третью статьи по 2 раза, её h-индекс станет 3.
2 4 1 4
1 100 1 1		 2 В этом втором примере Беси может написать не более одной статьи. Если Беси процитирует любую из её 1,2 или 4 статью хоть раз, её h-индекс станет 2.
Алгоритмы сортировкиБинарный поиск по ответу
✓ 22✗ 501 100средняяВойти и решать
Жевательные ленты#34966

Громозека с планеты Чумороза впечатлителен, раним, легко приходит в уныние и начинает плакать, попутно выпуская из ноздрей едкий дым. 
Громозека привез со своей родной планеты N штук жевательных лент, которую так любят земные дети. Он хочет поделить все ленты между K детьми. Но, оказывается, если у детей размер жевательной ленты будет различным, то они начнут ругаться и ссориться. В этот момент Громозека придёт в уныние. 
Помогите Громозеке поделить все жевательные ленты таким образом, чтобы из них можно было набрать K штук одинаковых. Радость детей прямо пропорциональна длине жевательных лент. Громозека хочет, чтобы дети получили как можно больше радости.
 

Входные данные
В первой строке заданы два числа - N (1 <= N <= 10001) и K (1 <= K <= 10001). Далее, в каждой из последующих N строк, записано по одному числу - длина каждой привезенной жевательной ленты. Длина ленты задана в сантиметрах. Все длины лежат в интервале от 1 до 107 сантиметров включительно.

Выходные данные
Выведите одно целое число - максимальную длину жевательной ленты в сантиметрах. В случае, если Громозека придёт в уныние, выведите 0.
 
Примеры
№ Входные данные Выходные данные
1 4 11
802
743
457
539		 200
Бинарный поиск по ответу
✓ 133✗ 176600лёгкаяВойти и решать
Интересные числа#34923
Роман коллекционирует числа, кажущиеся ему интересными. Например, сейчас он считает интересным положительные числа, запись которых в системе счисления с основанием k заканчивается нечетным числом нулей. Например, при k = 2 такими числами являются 210 = 102, 2410 = 110002.
Для того, чтобы пополнить свою коллекцию, Роман хочет найти n-ое в порядке возрастания такое число. Поскольку n он взял достаточно большим, то вручную у него это сделать не получается. Помогите Роману — напишите программу, которая найдет число, которое нужно ему для пополнения коллекции.

Входные данные: Первая строка содержит два целых числа (1 <= n <=1015, 2 <= k <= 10).
Выходные данные: Выведите n-ое в порядке возрастания число, запись которого в системе счисления с основанием k заканчивается на нечетное число нулей. Это число необходимо вывести в десятичной системе счисления.
Примеры
входные данные
1 2
выходные данные
2

входные данные
10 10
выходные данные
110
Бинарный поиск по ответу
✓ 68✗ 100900средняяВойти и решать
Провода#34922

Дано N отрезков провода длиной L1, L2, ..., LN сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.
 

Формат входных данных
В первой строке находятся числа N и K. В следующих N строках L1, L2, ..., LN, по одному числу в строке.

Ограничения 
  • 1 <= N <= 10 000,
  • 1 <= K <= 10 000,
  • 100 <= Li <= 10 000 000,
  • все числа целые.

Формат входных данных
Вывести одно число - полученную длину отрезков.
Бинарный поиск по ответу
✓ 355✗ 778600лёгкаяВойти и решать
K-квест#34879
В одной из компьютерных игр-квестов есть следующее задание. На карте игрового мира размещены N персонажей, с каждым из которых может встретиться игрок. От общения с i-м персонажем карма игрока меняется на величину ai, которая может быть как положительной, так отрицательной или даже нулем.

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

Комнаты, в которых находятся персонажи, соединены односторонними магическими порталами, поэтому игроку придется встречать персонажей в определенной последовательности: после персонажа номер i он попадает к персонажу номер i + 1, затем к персонажу номер i + 2, и т.д. В комнате последнего персонажа с номером N портала к другому персонажу нет.

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

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

Входные данные
В первой строке входных данных записаны два числа: количество персонажей N и необходимый уровень кармы K (|K| ≤ 109, K ≠ 0). Во второй строке через пробел записаны N целых чисел a1, a2, ..., aN — величины, на которые меняется карма героя после общения с персонажами с номерами 1, 2, ..., N соответственно.

Выходные данные
Выведите номер комнаты, в которую надо войти игроку и номер комнаты, из которой надо выйти, чтобы набрать карму K. Если возможных вариантов несколько, то необходимо вывести самый короткий путь, а если и таких несколько, то путь, начинающийся в комнате с как можно большим номером. Если достичь кармы K последовательно общаясь с персонажами невозможно, то выведите одно число  - 1.
 
Ввод Вывод
5 3
-2 2 -1 2 4		 2 4
7 1
1 -1 1 -1 1 -1 2		 5 5
4 3
2 2 2 2		 -1

 
Бинарный поискБыстрая сортировка
✓ 5✗ 981 100средняяВойти и решать
Управляющий совет#34775
В управляющий совет школы входят родители, учителя и учащиеся школы, причём родителей должно быть не менее одной трети от общего числа членов совета. В настоящий момент в совет входит N человек, из них K родителей. Определите, сколько родителей нужно дополнительно ввести в совет, чтобы их число стало составлять не менее трети от числа членов совета.

Формат входных данных
Программа получает на вход два целых числа N и K (N > 0, 0 ≤ K ≤ N), записанные в отдельных строках, — текущее число членов совета и число родителей в совете.

Формат выходных данных
Программа должна вывести единственное число — минимальное число родителей, которое необходимо ввести в совет.

Пояснение к примеру
В примере совет состоит из 27 человек, из которых родители составляют 7 человек. Если в совет ввести ещё 3 родителей, то в совете станет 30 человек, из которых родителей будет 10.

Бинарный поиск по ответуЦелые числа
✓ 246✗ 1 068600лёгкаяВойти и решать
Количество чисел, равное искомому#33591

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

Входные данные

В первой строке вводится одно натуральное число N, не превосходящее 105: количество чисел в массиве.

Во второй строке вводятся N натуральных чисел, не превосходящих 109, каждое следующее не меньше предыдущего.

В третьей строке вводится количество искомых чисел M - натуральное число, не превосходящее 106.

В четвертой строке вводится M натуральных чисел, не превосходящих 109.

Выходные данные

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

Если в массиве нет такого числа, выведите 0.

Примеры
№ Входные данные Выходные данные
1 4
1 2 2 4
4
1 4 3 2		 1
1
0
2
Бинарный поиск в массиве
✓ 413✗ 751600лёгкаяВойти и решать
*Рапорт#33253
Верс нужно подготовить рапорт о последнем боевом вылете. Она уже сочинила в голове текст, осталось лишь его записать. Рапорт будет состоять из двух частей: первая будет содержать n слов, i-е из которых состоит из ai букв, вторая — m слов, j-е из которых состоит из bj букв. Язык Крии не содержит никаких знаков препинания. Верс должна записать рапорт на клетчатом рулоне бумаги, шириной w клеток. Так как рапорт состоит из двух частей, она разделит вертикальной чертой рулон на две части целой ширины, после чего в левой части напишет первую часть, а в правой — вторую.
Обе части рапорта записываются аналогично, каждая на своей части рулона. Одна буква слова занимает ровно одну клетку. Первое слово записывается в первой строке рулона, начиная с самой левой клетки этой части рулона. Каждое следующее слово, если это возможно, должно быть записано в той же строке, что и предыдущее, и быть отделено от него ровно одной пустой клеткой.
Иначе, оно пишется в следующей строке, начиная с самой левой клетки. Если ширина части рулона меньше, чем длина какого-то слова, которое должно быть написано в этой части, написать эту часть рапорта на части рулона такой ширины невозможно.
Гарантируется, что можно провести вертикальную черту так, что обе части рапорта возможно написать. Верс хочет провести вертикальную черту так, чтобы длина рулона, которой хватит, чтобы написать рапорт, была минимальна. Помогите ей найти эту минимальную длину.
 
Входные данные: 
- в первой строке даны три целых числа w, n и m — ширина рулона, количество слов в первой и второй части рапорта (\(1 <= w <= 10^9\); \(1 <= n, m <= 100 000\));
- в следующей строке дано n целых чисел ai — длина i-го слова первой части рапорта \(1 <= a_i <= 10^9\);
- в следующей строке дано m целых чисел bj — длина j-го слова второй части рапорта \(1 <= b_j <= 10^9\).
Гарантируется, что возможно провести черту так, что обе части рапорта возможно написать.

Входные данные: в единственной строке выведите одно целое число — минимальную длину рулона, которой достаточно, чтобы написать рапорт.
 
Примеры
№ Входные данные Выходные данные
1
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3
 3

Примечание
В тесте из примера рулон можно разделить на две части, проведя черту между 7 и 8 столбцом клеток, а затем записать по два слова в каждой строке в обеих частях рапорта.
Бинарный поиск по ответу
✓ 54✗ 7851 100средняяВойти и решать
Калитка в заборе#33139
Дядя Фёдор, кот Матроскин и Шарик решили обновить забор вокруг своего сада в Простоквашино. Матроскин и Шарик, недолго думая, вкопали N столбов вдоль одной из сторон участка. Это очень сильно расстроило Дядю Фёдора, так как его друзья забыли о самом главном — калитка должна находиться именно на этой стороне, и для неё необходимо было оставить проём шириной как минимум W. Теперь им придётся выкапывать некоторые столбы.
 
Чтобы работа не пропадала даром, выкопать надо как можно меньше столбов. Помогите Дяде Фёдору определить, какие именно столбы надо выкопать. После выкапывания столбов должен найтись промежуток (между двумя оставшимися столбами, или между оставшимся столбом и концом стороны участка, или между двумя концами стороны участка) ширины больше или равной W.
 
Входные данные
Первая строка содержит два целых числа N и W — количество вкопанных столбов и минимально необходимую ширину проёма для калитки соответственно. Гарантируется, что 0<=N<=30000 и что 0<=W<=60000.
 
Будем считать, что вдоль интересующей нас стороны участка введена ось координат. Во второй строке входного файла находятся два числа L и R — координаты левого и правого конца этой стороны (LR). Далее следуют N чисел — координаты вкопанных столбов. Все координаты (включая L и R) — различные целые числа, по модулю не превосходящие 30000. Гарантируется, что все столбы вкопаны между левым и правым концами стороны.
 
Выходные данные
В первой строке выходного файла должно быть минимальное число столбов, которые надо выкопать. Далее должны следовать номера этих столбов. Столбы нумеруются в том порядке, как они указаны во входном файле, начиная с 1.
 
Если решений несколько, то вы можете вывести любое. Если решения нет, то выведите в выходной файл одну строку, содержащую число -1.
 
Ввод Вывод
3 2
2 6
3 4 5
 1
2
3 2
1 6
4 3 5
 0
3 5
1 7
5 3 4
3
2
1
3
"Два указателя"Бинарный поиск в массиве
✓ 14✗ 2141 100средняяВойти и решать
Старая книга#33126
Группа юных археологов работает на раскопках здания древней библиотеки. Летом
они обнаружили остатки старой книги и, изучив их, сделали следующие выводы.
Книга содержит несколько страниц, каждая страница содержит либо текст, либо
иллюстрацию. Первые k страниц книги точно содержат иллюстрации. Все страницы книги
пронумерованы, но номер страницы написан только на страницах, содержащих текст. Сумма
номеров страниц с текстом равна s.
К сожалению, ни общее количество страниц в книге, ни количество иллюстраций
установить не удалось. Тем не менее, юных археологов заинтересовал вопрос, какое
минимальное количество иллюстраций могло быть в книге.
Например, если k = 1, а s = 8, то страницы книги могли иметь следующее содержание
(буквой «Т» обозначена страница, содержащая текст, а буквой «И» — страница, содержащая
иллюстрацию):
- И Т И И И Т, пронумерованы страницы 2 и 6, 4 иллюстрации;
- И И Т И Т, пронумерованы страницы 3 и 5, 3 иллюстрации;
- И И И И И И И Т, пронумерована страница 8, 7 иллюстраций.
Минимальное количество иллюстраций равно 3.
Требуется написать программу, которая по заданным целым числам k и s определяет
минимальное количество иллюстраций, которое могло быть в книге.

Формат входных данных
Первая строка входных данных содержит целое число k (0 ≤ k ≤ 109).
Вторая строка входных данных содержит целое число s (k + 1 ≤ s ≤ 1012).

Формат выходных данных
Требуется вывести одно целое число — минимальное количество иллюстраций в
книге.
Ввод Вывод
1
8		 3


 
"Два указателя"Бинарный поискВывод формулы
✓ 2✗ 531 100средняяВойти и решать
Улучшение успеваемости#33121
В лицее на уроках информатики ответы учеников оцениваются целым числом баллов от 2 до 5. Итоговая оценка по информатике выставляется как среднее арифметическое оценок на всех уроках, округленное до ближайшего целого числа. Если среднее значение находится ровно посередине между двумя целыми числами, то оценка округляется вверх.
Примеры округления оценок приведены в таблице.
 
Оценки на уроках Среднее арифметическое Итоговая оценка
2, 3, 5 \({ {2 + 3 + 5} \over 3 }= 3 {1 \over 3}\) 3
3, 3, 4, 4 \({ {3 + 3 + 4 + 4} \over 4 }= 3 {1 \over 2}\) 4
5, 5, 5, 3, 5 \({ {5 + 5 + 5 + 3 + 5} \over 5 }= 4 {3 \over 5}\) 5
 
Все ученики лицея стремятся получить итоговую оценку по информатике не ниже 4 баллов. К сожалению, один из учеников получил на уроках a двоек, b троек и c четверок.Теперь он планирует получить несколько пятерок, причем хочет, чтобы итоговая оценка была не меньше 4 баллов. Ему надо понять, какое минимальное количество пятерок ему необходимо получить, чтобы добиться своей цели.
Требуется написать программу, которая по заданным целым неотрицательные числам a, b и c определяет минимальное количество пятерок, которое необходимо получить ученику, чтобы его итоговая оценка по информатике была не меньше 4 баллов.

Входные данные
Входные данные содержат три строки. Первая строка содержит целое неотрицательное число a, вторая строка содержит целое неотрицательное число b, третья строка содержит целое неотрицательное число c (0 ≤ a, b, c ≤ 1015, a + b + c ≥ 1).

Выходные данные
Выходные данные должны содержать одно число: минимальное число пятерок, которое необходимо получить ученику, чтобы итоговая оценка была не меньше 4 баллов.
 
Ввод Вывод
2
0
0		 2






 
Бинарный поискВывод формулыЦелые числа
✓ 27✗ 226900средняяВойти и решать
Чет-нечет#33096
Дана возрастающая последовательность целых чисел 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ... Она сформирована следующим образом: берется одно нечетное число, затем два четных, затем три нечетных и так далее. Выведите N-й элемент этой последовательности.

Программа должна работать быстрее, чем за линейный поиск
 
Входные данные
Одно целое число N (1 <= N <= 109).
 
Выходные данные
Выведите одно целое число - N-й элемент последовательности.
 
Ввод Вывод
1 1
4 5
Бинарный поиск по ответу
✓ 26✗ 221 000средняяВойти и решать
Провода#33094
Дано N отрезков провода длиной L1, L2, ..., LN сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.
 
Ограничения: 1 <= N <= 10 000, 1 <= K <= 10 000, 100 <= Li <= 10 000 000, все числа целые.

Программа должна работать быстрее, чем за линейный поиск
 
Входные данные
В первой строке находятся числа N и К. В следующих N строках - L1, L2, ..., LN, по одному числу в строке.
 
Выходные данные
Вывести одно число - полученную длину отрезков.
 
Бинарный поиск по ответу
✓ 18✗ 92700средняяВойти и решать
Вырубка леса#33093
Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес, на месте которого должно быть кукурузное поле. В лесу растут X деревьев.
 
Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т.д.
 
Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2M-й, 3M-й день, и т.д.
 
Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A + B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.
 
Фермер Николай хочет понять, за сколько дней лесорубы срубят все деревья, и он сможет засеять кукурузное поле. 
 
Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

Программа должна работать быстрее, чем за линейный поиск
 
Входные данные
Входной файл содержит пять целых чисел, разделенных пробелами: A, K, B, M и X (1 ≤ A, B ≤ 109 , 2 ≤ K, M ≤ 1018, 1 ≤ X ≤ 1018).
 
Выходные данные
Выходной файл должен содержать одно целое число — искомое количество дней.

Ввод Вывод
2 4 3 3 25 7

Бинарный поиск по ответу
—Войти и решать
Очень легкая задача - 2#33092
Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще N копий. В его распоряжении имеются M ксероксов, каждый из которых копирует лист за х секунд. (Разрешается использовать все ксероксы одновременно. Можно копировать не только с оригинала, но и с копии.) Помогите ему выяснить, какое минимальное время для этого потребуется.

Программа должна работать быстрее, чем за линейный поиск


Формат входных данных
В первой строке записаны да натуральных числа N, M  разделенные пробелом (1 ≤ N, M ≤ 2•108), во второй строке записаны скорости всех ксероксов - x (1 ≤ x ≤ 10 )


Формат выходных данных
Выведите одно число – минимальное время в секундах, необходимое для получения N копий.
 
Ввод Вывод
8 3
2 3 7		 9
Бинарный поиск по ответу
✓ 25✗ 20800средняяВойти и решать
Поделиться
Класснуть