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

Сложность двоичного поиска#33009

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

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

Вводится одно число N

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

Выведите наименьшее количество вопросов, которого гарантированно хватит Пете, чтобы угадать Васино число.

Ввод	Вывод
5	3

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

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

Квадратный корень и квадратный квадрат#27292

Найдите такое число x, что \(x^2 + \sqrt{x} = C\) , с точностью не менее 6 знаков после точки.

Входные данные
В единственной строке содержится вещественное число \(1 <=C <=10^{10}\).

Выходные данные
Выведите одно число — искомый \(x\).

Примеры

№	Входные данные	Выходные данные
1	2.0000000000	1.000000000
2	18.0000000000	4.000000000

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

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

Приближенный двоичный поиск#27279

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

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

В первой строке входных данных содержатся числа N и K (\(0< N,\ K <100001\)). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию. В третьей строке вводится K чисел второго массива.
Каждое число в обоих массивах по модулю не превосходит \(2 \cdot 10^9\).

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

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

✓ 793✗ 2 039600лёгкаяВойти и решать

Двоичный поиск#25959

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

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

В первой строке входных данных содержатся натуральные числа N и K (\(0<N,\ K <= 100000\)). Во второй строке задаются N элементов первого массива, отсортированного по возрастанию. В третьей строке – K элементов второго массива.
Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит \(10^9\).

Формат выходных данных
Требуется для каждого из K чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае.

Алгоритмы поиска Бинарный поиск в массиве

✓ 1 473✗ 2 534400лёгкаяВойти и решать

65820#65820

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

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

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

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

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

Качели#60586

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

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

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

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

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

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

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

Поиск стартового и стоп-кодонов#58279

Кодоны — это триплеты нуклеотидов (три буквы), которые определяют аминокислоты в процессе трансляции (синтеза белка).

Старт-кодон — кодон, с которого начинается считывание белковой последовательности. В ДНК это всегда ATG.
Стоп-кодоны — кодоны, которые сигнализируют окончание считывания. В ДНК это:
- TAA
- TAG
- TGA

Надо написать программу, которая:

Находит все стартовые (ATG) и стоп-кодоны (TAA, TAG, TGA) в последовательности ДНК.
Возвращает их позиции (индексы).

Формат входных данных
Строка содержит последовательность ДНК

Формат выходных данных
В первой строке вывести позиции старт-кодонов в порядке возрастания, во второй строке вывести позиции стоп-кодонов в порядке возрастания.

Поиск подстроки в строке Строки

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

Подсчет определенных последовательностей#58277

В биоинформатике часто требуется искать и подсчитывать конкретные последовательности нуклеотидов в ДНК. В данной задаче необходимо подсчитать количество повторений триплета "ATG" в заданной последовательности ДНК. Триплет "ATG" является важным мотивом, связанным с началом кодирования белков. Напишите функцию, которая принимает строку, представляющую последовательность ДНК, и возвращает количество вхождений триплета "ATG" в этой последовательности.

Формат входных данных
В единственной строке дана последовательность ДНК
Формат выходных данных
Необходимо подсчитать количество раз, когда встречается триплет ATG.

Поиск подстроки в строке Строки

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

Поиск подстроки. Задание 10#57951

Напишите программу, которая:
1) в первой строке запрашивает ввод строки и сохраняет ее в переменной s;
2) во второй строке запрашивает ввод строки и сохраняет ее в переменную subs;
3) выводит на экран наименьший индекс, с которого начинается подстрока subs в строке s; если строка s не содержит подстроку subs, то программа должна вывести -1.

Поиск подстроки в строке Строки

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

Массивы#55203

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

Входные данные
Первая строка входных данных содержит одно число N (1 ≤ N ≤ 10⁵) – количество элементов в первом массиве. Далее идет N целых чисел, не превосходящих по модулю 10⁹ – элементы первого массива, Далее идет количество элементов M во втором массиве и M элементов второго массива с такими же ограничениями.

Выходные данные
Выведите M чисел: для каждого элемента второго массива выведите, сколько раз такое значение встречается в первом массиве.

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

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

Наиболее удаленная точка#53717

Выведите координаты наиболее удаленной от начала координат точки.

Входные данные
Программа получает на вход набор точек на плоскости. Сначала задано количество точек n, затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Величина n не превосходит 100, все исходные координаты – целые числа, не превосходящие 10³
по абсолютной величине.

Выходные данные
Выведите координаты точки, наиболее удаленной от начала координат.

Линейный поиск Элементарная геометрия

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

Цветочный магазин#50363

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

Определите, сколько букетов сможет собрать Петя, если потратит не более \(x\) рублей на покупку цветов на базе. Ответьте на \(q\) запросов с различными \(x_i\).

Формат входных данных
В первой строке входных данных находятся два целых числа \(n\) и \(q\) (\(1 \le n, q \le 10^5\)) — количество различных типов цветов и количество запросов.

Во второй строке находятся \(n\) целых чисел \(a_1, a_2, \cdots, a_n\) (\(0 \le a_i \le 10^9\)) — количество цветов каждого вида, имеющихся в магазине.

В третьей строке находятся \(q\) целых чисел \(x_1, x_2, \cdots, x_q\) (\(0 \le x_i \le 10^9\)) — запросы Пети.

Формат выходных данных
Выходной файл должен содержать \(q\) чисел, где \(i\)-е число это максимальное количество букетов, которое можно собрать потратив не более \(x_i\) рублей.

Примечание
В первом примере у Пети изначально есть 1 цветок первого типа и 0 цветов второго типа.

В первом запросе у него есть 1 рубль, он покупает цветок второго типа и делает 1 букет.

Во втором запросе у него есть 2 рубля, он не может сделать два букета за 2 рубля, поэтому ответ по прежнему 1.

В третьем запросе у него есть 5 рублей, он покупает 2 цветка первого типа и 3 цветка второго типа и делает 3 букета.

Бинарный поиск по ответу Использование сортировки Префиксные суммы(минимумы, ...)

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

Есть n стульев...#49857

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

В офисе есть \(n\) стульев, \(i\)-й из которых имеет высоту \(h_i\) и ширину \(w_i\). Влад планирует выбрать любой набор офисных стульев \([i_1, i_2, \ldots, i_k]\) и расположить в ряд, чтобы на них можно было лечь. Рост Влада равен \(H\), поэтому, чтобы он мог удобно лежать, необходимо, чтобы суммарная ширина выбранных стульев была не меньше \(H\), то есть \[\sum\limits_{j=1}^k w_{i_j} \ge H \text{.}\]

Очевидно, что спать на стульях разной высоты неудобно. Назовем неудобностью выбранного набора максимальную разность высот двух соседних стульев в ряду, то есть \(\max\limits_{j=2}^k |h_{i_j} - h_{i_{j-1}}|\). Если набор состоит из одного стула, его неудобность равна \(0\).

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

Формат входных данных
В первой строке ввода через пробел даны два целых числа \(n\) и \(H\) — количество стульев и рост Влада (\(1 \le n \le 2 \cdot 10^5\); \(1 \le H \le 10^9\)).

Во второй строке ввода через пробел перечислены \(n\) целых чисел \(h_i\) — высоты стульев (\(1 \le h_i \le 10^9\)). В третьей строке в том же формате перечислены \(n\) целых чисел \(w_i\), равных ширине стульев (\(1 \le w_i \le 10^9\)).

Гарантируется, что \(H\) не превосходит суммы всех \(w_i\).

Формат выходных данных
Выведите единственное число — минимальное возможное неудобство среди всех подходящих наборов.

Замечание

В первом примере нужно выставить стулья \(2\) и \(4\) в любом порядке.

Во втором примере можно выбрать, например, следующие наборы: \([1, 5]\), \([2, 4, 3]\). Обратите внимание, что порядок стульев в наборе важен: неудобность набора \([2, 3, 4]\) равна \(\max(|5 - 3|, |4 - 5|) = \max(2, 1) = 2\), что больше, чем для набора \([2, 4, 3]\).

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

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

Двоичный поиск для монотонной функции (Python)#49750

Дано натуральное число x. Вычислите кубический корень из числа.

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

Число x – натуральное, не превосходящее \(10^6\).

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

Программа должна вывести единственное число: ответ на задачу с точностью не менее 6 знаков после запятой.

Примеры

№	Входные данные	Выходные данные
1	2	1.259921

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

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

Тайлер украшает площадь#49743

Мэр Цветочного города попросил лучшего плиточника Тайлера замостить квадратную зону площади плиткой. Тайлеру были выданы коробки, в каждой из которых содержится a_i квадратных плиток размером 1х1. Тайлеру поставили условие, что он должен обязательно использовать все плитки, которые ему были выданы.
Помогите Тайлеру определить, сможет ли он использовать все плитки, чтобы замостить из всех них квадрат какого-либо размера или ему придется идти к мэру и просить еще плиток?
Считайте, что на площади можно замостить квадрат любого размера.

Формат входных данных
В первой строке вводится натуральное число n (1 ≤ n ≤ 2·10⁵)- количество коробок, выданных Тайлеру. Во второй строке записаны n чисел a_i (1 ≤ a_i ≤ 10⁹)- количество плиток в i-й коробке.

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

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

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

Лестница#49636

Вы хотите построить лестницу и приготовили n блоков. Лестница строится путем наложения блоков друг на друга. В i-м ряду лестницы размещается ровно i блоков.
Определите количество полных рядов лестницы, которую вы сможете построить.

Решите задачу двоичным поиском.

Формат входных данных
Программа получает на вход натуральное число n (1 <= n <= 2³¹ - 1) - количество блоков.

Формат выходных данных
Выведите ответ на задачу.

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

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

Полный квадрат#49542

Для заданного целого положительного числа num, выведите 1, если num является полным квадратом, или 0 в противном случае.
Полный квадрат - это целое число, которое является квадратом целого числа. Другими словами, это произведение некоторого целого числа на само себя.

Решите задачу с помощью бинарного поиска.

Формат входных данных
Программа получает на вход одно целое положительное число num (1 <= num <= 2³¹ - 1).

Формат выходных данных
Выведите 1, если num является полным квадратом, или 0 в противном случае

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

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

Бинарный (двоичный) поиск по ответу (Python)#49461

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

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

Руководитель отдела качества очень хорошо к вам относится и написал для вас функцию isBadVersion(version), которая определяет является ли версия релиза плохой (возвращает True, если версия плохая, и False если хорошая).

Теперь вам необходимо реализовать функцию для поиска первой плохой версии. Вы должны как можно быстрее определить с какой версии пошел плохой релиз, поэтому количество использования функции isBadVersion(version) должно быть минимальным.

Ваша функция должна вернуть номер первого плохого релиза.

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

✓ 326✗ 1 428600лёгкаяВойти и решать

Бинарный поиск в невозрастающем массиве - 6#49457

Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс первого элемента равного key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.

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

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

Бинарный поиск в невозрастающем массиве - 5#49456

Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс первого элемента меньшего или равного key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.

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

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