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

Квадратный корень и квадратный квадрат#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лёгкаяВойти и решать

Кубическое уравнение#27291

Даны четыре действительных числа: A, B, C, D. Найдите все корни уравнения Ax³+Bx²+Cx+D=0. Известно, что все корни этого уравнения не превосходят по абсолютной величине 1000. Известно, что любые два корня этого уравнения различаются не менее, чем на 10^-6.

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

Программа получает на вход четыре действительных числа: A, B, C, D. Любые из этих четырех чисел, но не все одновременно, могут быть равны 0.

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

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

Ввод	Вывод
0 0 1000 -1	0.001

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

✓ 30✗ 3381 000средняяВойти и решать

Транспортировка#27126

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

Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала школы. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. Нато, чтобы довезти кружки от завода-изготовителя до ЛКШ,остаётся всего 24 часа.

Заказ на 10000000 экземпляров кружек (а именно столько заказали организаторы), конечно же, за один рейс не увезти. Однако, за первый рейс хочется привезти максимальное количество кружек. Для перевозки был заказан один большегрузный автомобиль. Но есть один нюанс: на некоторых дорогах установлено ограничение на вес автомобиля. Поэтому если автомобиль нагрузить кружками под завязку, то, возможно, не удастся воспользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случиться даже так, что из-за этого грузовик не успеет доехать до лагеря вовремя, а этого допустить никак нельзя. Итак, сколько же кружек можно погрузить в автомобиль, чтобы успеть привезти этот ценный груз вовремя, и не нарушая правил дорожного движения?

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

В первой строке находятся числа n (1≤n≤500) и m - количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих m строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой, потом время, которое тратится на проезд по этой дороге, и, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причем для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами.

Узловые пункты нумеруются числами от 1 до n. При этом завод по производству кружек имеет номер 1, а ЛКШ - номер n. Время проезда по дороге задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит 100 грамм, а пустой грузовик - 3 тонны.

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

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

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

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

*Лапта#25963

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

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

- в первой строке входных данных содержатся два числа: D — максимальное расстояние удара и N — количество соперников на поле (D и N натуральные числа, \(D <= 1000\), \(N <= 200\));
- в следующих N строках задается по три числа – начальные координаты x_i и y_i и максимальная скорость v_i соответствующего игрока (скорости и координаты — целые числа, \(–1000 <= x_i <= 1000\), \(0 <= y_i <= 1000\), \(0 < v_i <= 1000\)).
Никакие два игрока не находятся изначально в одной точке. Игрок, бьющий мяч, находится в точке с координатами (0,0). Мяч выбивается в точку с неотрицательной ординатой (\(y >= 0\)).

Выходные данные: выведите сначала время, которое потребуется игрокам, чтобы добежать до мяча, а затем координаты точки, в которую нужно выбить мяч. Если таких точек несколько, выведите координаты любой из них. Время и координаты нужно вывести с точностью \(10^{–3}\).

Примеры

№	Входные данные	Выходные данные
1	10 2 1 1 1 -1 1 1	9.05539 0.00000 10.00000

Бинарный поиск по ответу Квадродерево Элементарная геометрия

✓ 7✗ 781 400средняяВойти и решать

Дипломы#25961

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

Входные данные: на вход подаются три целых числа: w, h, n (\(1<=w,\ h,\ n <= 10^9\) ).

Выходные данные: необходимо вывести ответ на поставленную задачу.

Примеры

№	Входные данные	Выходные данные
1	2 3 10	9
2	1 1 1	1

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

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

Совсем другие штурмовики#23366

Вы управляете армией штурмовиков, сражающейся против армии повстанцев. Армия повстанцев состоит из n солдат, здоровье i-го солдата составляет ai единиц. Сила атаки каждого вражеского солдата равна de единиц. В Вашем распоряжении есть m штурмовиков. Сила атаки каждого из них — d_t, здоровье — h единиц.

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

Ваша задача — уничтожить армию неприятеля, задействовав минимальное число штурмовиков, вне зависимости от действий противника, либо определить, что уничтожить вражескую армию не получится.

Формат входных данных
В первой строке входного файла заданы натуральные числа n, m, ( n,m <= 2*10⁵), d_e, d_t , h — число солдат в армии противника, число штурмовиков в вашем распоряжении, сила атаки каждого солдата неприятеля, сила атаки и число единиц здоровья каждого из штурмовиков соответственно ( d_e, d_t , h <= 10⁹). В следующей строке задано n натуральных чисел a_i — число единиц здоровья i-го солдата армии противника (a_i <= 10⁹).
Формат выходных данных
Выведите единственное число — минимальное количество штурмовиков, необходимое для уни чтожения армии противника, либо -1, если миссия невыполнима.

Ввод	Вывод
3 3 1 1 2 1 2 3	3
4 10 2 1 2 1 2 1 2	5
3 1 1 2 5 1 2 3	-1

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

✓ 1✗ 31 200средняяВойти и решать

Вырубка леса#21901

Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес, на месте которого должно быть кукурузное поле. В лесу растут 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 <= 10^9\) , \(2 <= K,\ M <= 10^{18}\), \(1 <= X <= 10^{18}\)).

Входные данные: выведите одно целое число — искомое количество дней.

Примеры

№	Входные данные	Выходные данные
1	2 4 3 3 25	7

Пояснение к примеру
В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим образом:
- 1-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 5 деревьев;
- 2-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 10 деревьев;
- 3-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 12 деревьев;
- 4-й день: Дмитрий отдыхает, Федор срубает 3 дерева, итого 15 деревьев;
- 5-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 20 деревьев;
- 6-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 22 дерева;
- 7-й день: Дмитрий срубает 2 дерева, Федор срубает оставшееся 1 дерево, итого все 25 деревьев срублены.

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

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