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

Аркадий Аркадьевич делает грядки#97011

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

Для того чтобы собрать прямоугольную грядку, нужны 4 доски. В идеале это должны быть две пары досок равной длины, тогда из них можно сложить ровный прямоугольник. Но если доски имеют неравную длину, то в одном из углов полученной грядки можно разместить пластиковый уголок: две планки длины \(r\), скреплённые под прямым углом. Уголок со стороной \(r\) позволит увеличить длины двух досок на величину, не превосходящую \(r\). Если противоположными сторонами грядки будут доски длины \(a\) и \(b\), а также \(c\) и \(d\) соответственно, то для того чтобы сделать прямоугольную грядку из этих досок, понадобится уголок размера \(\max(|a-b|, |c-d|)\) . Например, чтобы сделать грядку из досок длины 5, 7, 3, 2, понадобится уголок размера 2. На рисунке чёрным цветом изображены доски и красным цветом изображён уголок.

В сарае у Аркадия Аркадьевича нашлись \(n\) досок, \(i\)-я из которых имеет длину \(l_i\). Теперь он хочет выбрать из них четыре и сложить из них грядку таким образом, чтобы использовать уголок наименьшего размера. Помогите ему.

Первая строка входных данных содержит число \(n\) (\(4 \leq n \leq 10^5\)) — количество досок в сарае у Аркадия Аркадьевича.

Следующие \(n\) строк содержат числа \(l_1, \dots, l_n\) (\(1 \leq l_i \leq 10^9\)) — длины досок.

Программа должна сначала вывести число \(r\) — минимально возможный размер уголка.

Во второй строке выведите 4 числа \(a\), \(b\), \(c\), \(d\) — длины досок, которые необходимо выбрать для грядки. При этом противоположными сторонами прямоугольника будут доски \(a\) и \(b\), а также \(c\) и \(d\). Если есть разные варианты выбора досок для грядки с одной и той же величиной уголка, можно вывести любой из них.

Решения, правильно работающие, когда \(n \leq 30\), будут оцениваться в 20 баллов.

Решения, правильно работающие, когда \(n \leq 100\), будут оцениваться в 45 баллов.

Решения, правильно работающие, когда \(n \leq 500\), будут оцениваться в 65 баллов.

Решения, правильно работающие, когда все \(l_i \leq 30\), будут оцениваться в 10 баллов.

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

✓ 1✗ 8—Войти и решать

План эвакуации#97010

Этаж здания представляет собой прямоугольник из \(n\times m\) квадратных комнат. Из каждой комнаты есть проходы в соседние комнаты. В двух комнатах находятся лестницы. Необходимо разработать план эвакуации — указать для каждой комнаты направление движения в одну из соседних комнат так, чтобы, передвигаясь по комнатам только в указанных направлениях, можно было бы достичь одной из двух лестниц, пройдя минимальное расстояние.

На рисунке изображён возможный план эвакуации для примера из условия. Комнаты с лестницами обозначены звёздочками.

Первая строка входных данных содержит число \(n\) — количество строк в плане эвакуации, \(1\le n\le 100\). Вторая строка входных данных содержит число \(m\) — количество столбцов в плане эвакуации, \(2\le m\le 100\). Следующие две строки содержат числа \(r_1\) и \(c_1\) — номера строки и столбца комнаты, в которой находится первая лестница, \(1\le r_1\le n\), \(1\le c_1\le m\). Следующие две строки содержат числа \(r_2\) и \(c_2\) — номера строки и столбца комнаты, в которой находится вторая лестница, \(1\le r_2\le n\), \(1\le c_2\le m\). Гарантируется, что \(r_1\ne r_2\) или \(c_1\ne c_2\). Строки нумеруются сверху вниз числами от 1 до \(n\), столбцы нумеруются слева направо числами от 1 до \(m\).

Программа должна вывести \(n\) строк, каждая строка должна содержать \(m\) символов. Каждый символ соответствует одной комнате. В двух комнатах с лестницами должен находиться символ <<S>> (прописная английская буква). В остальных комнатах находятся символы, указывающие направление движения:

<<<>> (символ <<меньше>>) — налево.

<<>>> (символ <<больше>>) — направо.

<<^>> (символ находится на клавише <<6>>) — вверх.

<<v>> (строчная английская буква) — вниз.

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

Решения, правильно работающие, когда \(n=1\), будут оцениваться в 20 баллов.

Решения, правильно работающие, когда \(c_1=c_2\), будут оцениваться в 20 баллов.

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

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

✓ 1✗ 0—Войти и решать

Большой квадрат#97009

Даны два прямоугольника размера \(a\times b\) и \(c\times d\). Можно соединить их вместе, приложив сторону одного прямоугольника к стороне другого и склеив место соединения. Прямоугольники можно поворачивать перед склеиванием. После этого из полученной фигуры нужно вырезать квадрат со сторонами, параллельными сторонам прямоугольника. Определите максимальное возможное значение стороны квадрата.

На рисунке изображены два прямоугольника со сторонами \(8\times 3\) и \(6\times 2\), из которых можно вырезать квадрат со стороной 5 (заштрихован).

Программа получает на вход натуральные числа \(a\), \(b\), \(c\), \(d\), каждое в отдельной строке — стороны первого и второго прямоугольников. Все числа не превосходят \(10^9\).

Программа должна вывести одно целое число — максимальную возможную сторону квадрата.

Вывод формулы

✓ 3✗ 42—Войти и решать

Счёт строк по условию#96830

В первой строке — число N, дальше N строк по шесть чисел через пробел.

Выведите, сколько строк удовлетворяют обоим условиям:

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

Это условие взято из демоверсии ЕГЭ 2025 года. Для решения задачи напишите программу, считав входные данные с калвиатуры (а не с файла как в основном задании). Цель задания - проверить правильность написания программы.

Алгоритмы обработки

✓ 2✗ 1—Войти и решать

Кодирование графики: макс. число кадров анимации#95221

Для хранения покадровой анимации, состоящей из \(N\) кадров одинакового размера \(640 \times 480\) пикселей, отведено 4800 Кбайт памяти без учёта заголовка файла. Изображение использует 16 цветов, для каждого пикселя также выделяется 4 бита для хранения степени прозрачности. Коды пикселей записываются один за другим без промежутков.

Определите максимально возможное значение \(N\).