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

Две кнопки#38583

Алиса и Боб управляют роботом. У каждого из них есть по одной кнопке, которая управляет роботом. Алиса начала удерживать кнопку через A секунд после запуска робота и отпустила кнопку через B секунд после запуска. Боб начал удерживать кнопку через C секунд после запуска и отпустил кнопку через D секунд после запуска. Сколько секунд Алиса и Боб удерживали свои кнопки одновременно?

Входные данные
На вход 4 целых числа: A, B, C и D (\(1<=A<B<=100\), \(1<=C<D<=100\)).

Выходные данные
Выведите продолжительность времени (в секундах), в течение которого Алиса и Боб удерживали свои кнопки одновременно.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	0 75 25 100	50	Алиса начала удерживать кнопку через 0 секунд после запуска робота и отпустила ее через 75 секунд после запуска. Боб начал удерживать кнопку через 25 секунд после запуска и отпустил ее через 100 секунд после запуска. Следовательно, время, когда они оба удерживали свои кнопки, составляет 50 секунд от 25 секунд после запуска до 75 секунд после запуска.
2	0 33 66 99	0	Алиса и Боб не удерживали кнопки одновременно, поэтому ответ - ноль секунд.
3	10 90 20 80	60

Отрезки Пересечение множеств

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

Мерлин#21817

Однажды, вернувшись в свою башню, Мерлин обнаружил, что Моргана наложила проклятие на

все его сосуды с эликсиром мудрости.

Мерлин знает, как снять проклятие, но соответствующее заклинание требует, чтобы во всех

сосудах, к которым оно применяется, было равное количество эликсира.

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

сосудов и переливает весь эликсир из выбранных сосудов в оставшиеся. Он может распределить

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

эликсир из выбранных сосудов перелит, Мерлин разбивает опустошенные сосуды (с них проклятие

уже не снять), выбрасывает осколки и применяет заклинание снятия проклятия к оставшимся

сосудам.

Помогите волшебнику узнать, какое наименьшее количество сосудов ему придется разбить,

чтобы снять проклятие Морганы.

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

В первой строке входного файла находится число n (2 ≤ n ≤ 10⁵) — количество сосудов. Во

второй строке содержатся n чисел a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10⁹) — количество литров эликсира

мудрости в каждом сосуде.

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

Выведите в выходной файл минимальное количество сосудов, которые Мерлину придется

разбить.

Пример
Ввод

2 3 2
Вывод
1

Ввод:

4 4 4 4
Вывод
0

Ввод

1 2 3 4 5
Вывод
2

В первом примере можно, например, перелить 0.5 литра эликсира из первого сосуда во второй

и 1.5 литра в третий, после чего разбить первый сосуд.

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

В третьем примере можно, например, перелить 1 литр эликсира из первого сосуда во второй, по

2 литра из пятого во второй и третий, 1 литр из пятого в четвертый, после чего разбить первый и

пятый сосуды.

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

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

Шахматы#21811

Кроме школы и математического кружка, Вася ходит на шахматный кружок. Но играть в шахматы на обычной доске 8 × 8 ему кажется не очень интересным. Недавно он придумал свою версию шахмат, в которой игра происходит на доске, имеющей другую форму. Васина доска состоит из n столбцов, i-й из которых содержит ai клеток. Нижние клетки всех столбцов образуют один горизонтальный ряд, причем длины столбцов упорядочены слева направо по невозрастанию. На рисунке ниже приведен пример доски, в которой три столбца, содержащих 5, 2 и 1 клетку, соответственно.

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

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

В первой строке входного файла задано целое число n — количество столбцов доски

(1 ≤ n ≤ 1000). Следущая строка содержит n чисел a1, a2, . . . , an — количество клеток в столбцах

(1 ≤ ai ≤ 1000, a1 ≥ a2 ≥ . . . ≥ an).

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

В первой строке выведите число k — минимальное число ладей, которое можно расставить на доске так, чтобы каждую клетку доски била хотя бы одна ладья. Следующие k строк должны содержать описание позиций ладей, по одной на каждой строке. Позиция ладьи задается двумя числами: номером столбца, в котором стоит ладья, и номером клетки в столбце. Столбцы нумеруются, начиная с 1, слева направо, клетки в столбцах нумеруются снизу вверх, также начиная с 1.

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

Примеры
Ввод

5 2 1

Вывод

1 5

2 1

Отрезки Разбор случаев реализация

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