2025/26, Кружок для начинающих, Бинарный поиск 😎

Вася загадал число от 1 до \(N\). За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино число?

2

1

3

2

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

10 5
1 1 3 3 5 7 9 18 18 57
57 3 9 1 179

10 10
3 4
7 7
1 2
0

Реализуйте алгоритм приближенного бинарного поиска.

5 5
1 3 5 7 9 
2 4 8 1 6

1
3
7
1
5

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось \(n\) дипломов, причём, как оказалось, все они имели одинаковые размеры: \(w\) — в ширину и \(h\) — в высоту. Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером \(w\) на \(h\). Дипломы запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек. Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.

2 3 10

9

Дано \(N\) отрезков провода длиной \(L_{1},\, L_{2},\, \ldots,\, L_{N}\) сантиметров. Требуется с помощью разрезания получить из них \(K\) равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить \(K\) отрезков длиной даже \(1\) см, вывести \(0\).

Ограничения: \(1 \leq N \leq 10^{4},\; 1 \leq K \leq 10^{4},\; 10^{2} \leq L_{i} \leq 10^{7}\), все числа целые.

4 11
802
743
457
539

200

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

6 3
2 5 7 11 15 20

9

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

4 1 1

3

5 1 2

4

Дано действительное число \(a\) и натуральное \(n\). Вычислите корень \(n\)-й степени из числа \(a\).

Для решения используйте метод деления отрезка пополам.

2
2

1.41421356237

4
2

2.0

Дано кубическое уравнение \(ax^{3} + bx^{2} + cx + d = 0 \;(a \ne 0)\). Известно, что у этого уравнения ровно один корень. Требуется его найти.

1 -3 3 -1

0.999999598818135

-1 -6 -12 -7

-0.999999999990564

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

Каждый модуль представляет собой жилой отсек, который имеет форму прямоугольника размером \(a \times b\) метров. Для повышения надежности модулей инженеры могут добавить вокруг каждого модуля слой дополнительной защиты. Толщина этого слоя должна составлять целое число метров, и все модули должны иметь одинаковую толщину дополнительной защиты. Модуль с защитой, толщина которой равна \(d\) метрам, будет иметь форму прямоугольника размером \((a + 2d) \times (b + 2d)\) метров.

Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером \(w \times h\) метров. При этом они должны быть организованы в виде регулярной сетки: их стороны должны быть параллельны сторонам поля, и модули должны быть ориентированы одинаково.

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

1 1 1 1 1

0

1 1 1 3 3

1

Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес, на месте которого должно быть кукурузное поле. В лесу растут \(X\) деревьев. Дмитрий срубает по A деревьев в день, но каждый \(K\)-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в \(K\)-й, 2\(K\)-й, 3\(K\)-й день, и т.д. Федор срубает по B деревьев в день, но каждый \(M\)-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в \(M\)-й, 2\(M\)-й, 3\(M\)-й день, и т.д. Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают \(A\) + \(B\) деревьев, в дни, когда отдыхает только Федор — \(A\) деревьев, а в дни, когда отдыхает только Дмитрий — \(B\) деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается. Фермер Николай хочет понять, за сколько дней лесорубы срубят все деревья, и он сможет засеять кукурузное поле. Требуется написать программу, которая по заданным целым числам \(A\), \(K\), \(B\), \(M\) и \(X\) определяет, за сколько дней все деревья в лесу будут вырублены.

1 2 1 3 10

8

1 2 1 3 11

9

В классе учатся \(N\) человек. Классный руководитель получил указание направить на субботник \(R\)  бригад по \(С\) человек в каждой.

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

\(Числом неудобства\) бригады будем называть разность между ростом самого высокого и ростом самого низкого членов этой бригады (если в бригаде только один человек, то эта разница равна 0). Классный руководитель решил сформировать бригады так, чтобы максимальное из чисел неудобства сформированных бригад было минимально. Помогите ему в этом!

Рассмотрим следующий пример. Пусть в классе 8 человек, рост которых в сантиметрах равен 170, 205, 225, 190, 260, 130, 225, 160, и необходимо сформировать две бригады по три человека в каждой. Тогда одним из вариантов является такой:

1 бригада: люди с ростом 225, 205, 225

2 бригада: люди с ростом 160, 190, 170

При этом число неудобства первой бригады будет равно 20, а число неудобства второй — 30. Максимальное из чисел неудобств будет 30, и это будет наилучший возможный результат.

8 2 3
170
205
225
190
260
130
225
160

30

Словарь задан массивом отсортированных в лексикографическом порядке строк. Напишите программу эффективного поиска слова в словаре.

abba
4
a
ab
aba
baba

NO

На день рождения Пете подарили коробку кубиков. На каждом кубике написано некоторое целое число. Петя выложил все \(n\) своих кубиков в ряд, так что числа на кубиках оказались расположены в некотором порядке \(a_{1}, \, a_{2}, \, \ldots, \, a_{n}\). Теперь он хочет раскрасить кубики в разные цвета таким образом, чтобы для каждого цвета последовательность чисел на кубиках этого цвета была строго возрастающей. То есть, если кубики с номерами \(i_{1}, \, i_{2}, \, \ldots, \, i_{k}\) покрашены в один цвет, то \(a_{i_1} \lt a_{i_2}\lt ... \lt a_{i_k}\). Петя хочет использовать как можно меньше цветов. Помогите ему!

10
2 3 1 3 2 1 2 2 4 3

5
1 1 2 2 3 4 4 5 1 3