На эту неделю подготовили тренировочный контест по бинарному поиску.

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

В контест вошли задачи:

• Целый квадратный корень — https://judje.olprog.ru/problem/isqrt
• Целый кубический корень — https://judje.olprog.ru/problem/icbrt
• Поиск индекса — https://judje.olprog.ru/problem/searchindex
• Количество чисел в диапазоне — https://judje.olprog.ru/problem/countinrange
• Агрессивные коровы — https://judje.olprog.ru/problem/aggressivecows
• Разбиение массива — https://judje.olprog.ru/problem/splitarray
• Коко ест бананы — https://judje.olprog.ru/problem/koko
• Доставка за несколько дней — https://judje.olprog.ru/problem/shipdays
• Распил древесины — https://judje.olprog.ru/problem/woodcutting
• Наименьший делитель — https://judje.olprog.ru/problem/smallestdivisor
• Время производства — https://judje.olprog.ru/problem/productiontime
• Максимальное число кусков — https://judje.olprog.ru/problem/maxpieces
• Букеты — https://judje.olprog.ru/problem/bouquets
• Треугольные числа — https://judje.olprog.ru/problem/triangular
• Разделить шоколад — https://judje.olprog.ru/problem/dividechocolate
• Вещественный квадратный корень — https://judje.olprog.ru/problem/sqrtreal

Этот контест подойдёт тем, кто хочет:

• закрепить классический бинарный поиск по массиву;
• научиться искать левую и правую границу;
• потренировать задачи на «бинарный поиск по ответу»;
• научиться формулировать проверку can(x);
• разобраться, когда нужно искать минимум, а когда максимум;
• аккуратно поработать с вещественными числами.

Во время решения полезно каждый раз отдельно проговаривать:

• по чему именно идёт бинарный поиск;
• какая величина является ответом;
• монотонна ли проверка;
• что означает true и false в функции can;
• какую границу нужно сдвигать;
• что выводить в конце: l, r, left, right или сохранённый ответ.

Рекомендуем решать задачи по порядку. Сначала идут более прямые задачи на поиск и корни, затем задачи на массивы и диапазоны, а после них — классические задачи на бинарный поиск по ответу: коровы, разбиение массива, доставка, производство, букеты и шоколад.

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

Удачи в решении!

Ждём ваши результаты, вопросы и впечатления от задач.