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

Даны два целых положительны числа \(a\) и \(b\).

Найдите количество различных целых положительных чисел \(c\), таких, что существует невырожденный треугольник с длинами сторон \(a\), \(b\) и \(c\).

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

Формат входных данных
На первой строке ввода находится целое число \(a\), на второй строке ввода находится целое число \(b\) (\(1 \le a, b \le 10^9\)).

Формат выходных данных
Выведите одно целое число \(k\) — количество различных целых положительных чисел \(c\), таких, что существует невырожденный треугольник с длинами сторон \(a\), \(b\) и \(c\).

Элементарная геометрия

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

Спортивная акция - 2#50144

В магазине спортивных товаров проходит акция. На K товаров с самой высокой ценой установлена скидка в размере d%. Причем, от каждой цены, после применения скидки, отбрасываются копейки. Администрация магазина хочет узнать, какую сумму они получат от продажи всех товаров по акции.

Входные данные
В первой строке вводят три числа, записанные через пробел: N – общее количество товаров (натуральное число, не превышающее 100 000), K – количество товаров (1 < K < N), d - размер скидки в процентах (5 < d < 50). В следующих N строках находятся значения цены каждого из товаров (все числа натуральные, не превышающие 10 000), каждое в отдельной строке. Гарантируется, что ответ не превышает 10⁹.

Выходные данные
Выведите одно число - ответ на задачу.

Примечание
Стоимость товара со скидкой выисляется по следующей формуле:
Цена со скидкой = Исходная цена - Исходная цена * (Процент скидки / 100).

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

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

Двоичный поиск для монотонной функции (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лёгкаяВойти и решать

Сортировка строк#49712

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

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

В первой строке записаны через пробел размеры матрицы: количество строк N и количество столбцов M ( 1 <= N , M <= 100 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами. В последней строке вводится номер столбца K .

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

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

Примеры

№	Входные данные	Выходные данные
1	4 5 21 22 23 24 25 26 12 18 29 33 11 37 31 14 39 16 17 18 5 20 1	26 12 18 29 33 21 22 23 24 25 16 17 18 5 20 11 37 31 14 39

Алгоритмы сортировки Двумерные массивы

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

Сортировка по сумме элементов в столбце - 1#49711

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

Формат входных данных
В первой строке записаны два числа N и M - количество строк и столбцов матрицы соответственно (1 <= N, M <= 50 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами.

Формат выходных данных
Программа должна вывести получившуюся матрицу.

Алгоритмы сортировки

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

Сортировка по максимальному элементу в строке - 2#49710

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

Формат входных данных
В первой строке записаны два числа N и M - количество строк и столбцов матрицы соответственно (1 <= N, M <= 50 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами.

Формат выходных данных
Программа должна вывести получившуюся матрицу.

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

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

Сортировка по сумме строк - 2#49708

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

Формат входных данных
В первой строке записаны два числа N и M - количество строк и столбцов матрицы соответственно (1 <= N, M <= 50 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами.

Формат выходных данных
Программа должна вывести получившуюся матрицу.

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

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

Открыть все комнаты#49671

Магистр Максимус отправился в опасное путешествие в горы Ордена Магов. Внутри гор великими магами прошлого созданы комнаты, в каждой из которых хранятся магические артефакты. Максимус желает пройти через все n комнат, но, как оказалось, все комнаты заперты, за исключением комнаты 0, в которую Максимус уже вошел.
В каждой комнате имеется набор уникальных заклинаний, открывающих двери других комнат. Магистр Максимус познал язык великих магов, поэтому он может легко прочитать эти заклинания и отпирать другие комнаты.

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

По известному набору заклинаний, определите сможет ли Максимум получить все артефакты или нет.

Формат входных данных
В первой строке записано число n (2 <= n <= 1000), количество комнат. Далее идет n строк. В i-й строке описываются заклинания, хранящиеся в этой комнате. В каждой из этих строк первое число (m, 0 <= m <= 1000) обозначает количество уникальных заклинаний, которые открывают комнаты, далее записаны m уникальных чисел rooms[i](0 <= rooms[i][j] < n) - номера комнат, которые открывают эти заклинания (0<=i<n, 1 <= общее количество заклинаний во всех комнатах <= 10000).

Формат выходных данных
Выведите True, если Максимус может посетить все комнаты и найти все магические артефакты, или False в противном случае.

Обход в ширину

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

Лестница#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лёгкаяВойти и решать

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сортировка массива (сложная) - 4#49414

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

Формат входных данных
Программа получает на вход в первой строке натуральное число n - размер массива. Вторая строка содержит n целых чисел a_i- элементы массива (1 <= n <= 10³, -10⁴ <= a_i <= 10⁴).

Формат выходных данных
Выведите результирующий массив.

Квадратичные сортировки

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