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

Сортировка побочной диагонали#45717

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

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	5 12 4 8 13 13 1 12 1 4 15 2 3 5 2 3 6 5 13 12 14 14 9 15 4 12	12 4 8 13 14 1 12 1 13 15 2 3 5 2 3 6 5 13 12 14 4 9 15 4 12

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

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

Сортировка главной диагонали#45716

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	5 1 11 11 5 10 2 9 2 10 2 12 9 10 9 15 6 15 14 1 11 11 12 4 9 3	1 11 11 5 10 2 1 2 10 2 12 9 3 9 15 6 15 14 9 11 11 12 4 9 10

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

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

Доля в сумме#44941

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

Входные данные
В первой строке входных данных записаны через один пробел два натуральных числа N и M ( 0 < N, M <= 25). Далее идут N строк по M положительных целых чисел в каждой - элементы матрицы A (каждый элемент матрицы не превышает 10⁵).

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

Примеры

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

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

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

Ветки дерева#44774

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

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

Вводится последовательность целых чисел,оканчивающаяся нулем. Построить по ней дерево.

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

Выведите список требуемых вершин.

Примеры

№	Входные данные	Выходные данные
1	7 3 2 1 9 5 4 6 8 0	2 9

Двоичное дерево поиска Деревья

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

Обход дерева#44773

Выведите все элементы полученного дерева в порядке возрастания.

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

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

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

Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	7 3 2 1 9 5 4 6 8 0	1 2 3 4 5 6 7 8 9

Двоичное дерево поиска Деревья

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

Второй максимум в дереве#44772

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

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

Дана последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.

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

Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	7 3 2 1 9 5 4 6 8 0	8

Двоичное дерево поиска Деревья

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

МОШ и числа#44659

На заключительный этап МОШ по информатике в 2023 году пришло N участников. Так получилось, что у каждого ребенка на каком либо из предметов одежды было записано одно число. При регистрации, один из организаторов решил записать все эти числа. Позже выяснилось, что каким-то чудесным образом, все участники зарегистрировались в порядке неубывания этих чисел на одежде.

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

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

В первой строке входного файла содержится единственное число N (0 <= N <= 10⁵) — количество участников заключительного этапа. В следующей строке находятся N упорядоченных по неубыванию неотрицательных целых чисел, не превосходящих 10⁹ и разделенных пробелами — числа, записанные у участников на одежде. В третьей строке файла записано число M (1<=M<=100000) — количество чисел, информацию о которых хотят узнать судьи. В четвертой строке через пробел записаны M целых неотрицательных чисел (не превышающих 10⁹+1).

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

Выведите M чисел, каждое в отдельной строке. Для каждого заданного в четвертой строке числа выведите количество участников с таким числом на одежде.

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

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

Сбалансированность#44649

Дерево называется сбалансированным, если для любой его вершины высота левого и правого поддерева для этой вершины различаются не более чем на 1.

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

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

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

Определите, является ли дерево сбалансированным, выведите слово YES или NO.

Примеры

№	Входные данные	Выходные данные
1	7 3 2 1 9 5 4 6 8 0	YES

Двоичное дерево поиска Деревья

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

Выведи развилки#44648

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

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

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит. Постройте по этой последовательности дерево.

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

Выведите ответ задачи.

Примеры

№	Входные данные	Выходные данные
1	7 3 2 1 9 5 4 6 8 0	3 5 7

Двоичное дерево поиска Деревья

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

Выведи листья#44647

Для полученного дерева выведите список всех листьев (вершин, не имеющих потомков) в порядке возрастания.

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

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.

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

Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	7 3 2 1 9 5 4 6 8 0	1 4 6 8

Двоичное дерево поиска Деревья

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

Количество элементов в дереве#44646

Подсчитайте количество элементов в получившемся дереве и выведите это количество.

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

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.

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

Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	7 3 2 1 9 5 4 6 8 0	9

Двоичное дерево поиска Деревья

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

Высота дерева#44645

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

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

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

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

Выведите единственное число – высоту получившегося дерева.

Пример соответствует следующему дереву:

Примеры

№	Входные данные	Выходные данные
1	7 3 2 1 9 5 4 6 8 0	4

Двоичное дерево поиска Деревья

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

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

Напишите программу, которая переставляет строки матрицы так, чтобы значения в столбце 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

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

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

Шахматный конь#44615

Шахматный конь, расположенный в центре доски держит под ударом 8 полей. В углу только лишь 2 поля.
Вам задано расположение коня на шахматной доске. Выведите на экран шахматную доску, с расположенным на ней конем, а также отметьте все поля, которые конь держит под ударом. Поле, где расположен конь, отметьте английской буквой «K». Поля, которые он держит под ударом, отметьте символами «*». Остальные клетки заполните точками.

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

Программа получает на вход два числа - координаты коня на шахматной доске (доска размером 8х8). Координаты вводятся на одной строке через пробел. Первое число обозначает номер строки, а второе — номер столбца. Все числа принимают значения от 1 до 8.

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

Выведите на экран изображение доски так, как это показано в примере. Обратите внимание, что символы в одной строке разделены пробелом.

Примеры

№	Входные данные	Выходные данные
1	4 5	. . . . . . . . . . . * . * . . . . * . . . * . . . . . K . . . . . * . . . * . . . . * . * . . . . . . . . . . . . . . . . . .

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

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

Престижный номер#44311

В одной очень влиятельной организации для упрощения контроля въезда автотранспорта сотрудников на территорию решили, что автомобильные номера у всех сотрудников должны иметь одинаковое произведение цифр, равное числу N.
Номера в этой стране могут быть любыми натуральными числами, а жители страны очень любят «маленькие» номера — чем меньше число в номере автомобиля, тем более престижным он считается.
Директор организации хочет, чтобы ни у кого из сотрудников не было более престижного номера, чем у него. Поскольку организация очень влиятельная, директор может получить любой номер по своему желанию.

Входные данные
Программа получает на вход одно натуральное число N, не превосходящее 10¹⁸, — произведение
цифр автомобильных номеров сотрудников очень влиятельной организации.
Обратите внимание, значение N может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип long long в языке C++, тип int64 в Pascal, тип long в Java и C#).

Выходные данные
Выведите одно целое число — минимальное значение номера автомобиля директора очень влиятельной организации.
Если ни одного подходящего номера не существует, программа должна вывести число «−1».

Примеры

№	Входные данные	Выходные данные
1	70	257
2	101	-1

Арифметические алгоритмы (Теория чисел)Жадный алгоритм

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

Самолёт#44309

В салоне самолёта в одном ряду находится n кресел. Для удобства прохода и обсуживания пассажиров вдоль салона делается один или два прохода. Например, в салоне самолёта Sukhoi Superjet 100 в ряду 5 кресел и один проход (с одной стороны прохода два кресла, с другой стороны — три), а в самых больших современных самолётах — 10 кресел и два прохода (по три кресла по бокам салона у иллюминаторов и четыре кресла между проходами).

Предположим, что в будущем появятся самолёты большего размера, поэтому количество проходов придётся увеличить. Определите, какое минимальное число проходов должно быть в самолёте, в одном ряду салона которого находится n кресел. По бокам салона (у иллюминаторов) может находиться не более 3 кресел, а между двумя проходами — не более 4 кресел. При этом в салоне должен
быть хотя бы один проход.
Входные данные
Программа получает на вход одно натуральное число n, не превосходящее 2 · 10⁹ , — количество кресел в одном ряду салона.
Выходные данные
Программа должна вывести единственное целое число — минимальное количество проходов, которое должно быть в салоне самолёта с n креслами в одном ряду.

Примеры

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

Вывод формулы Задачи на моделирование

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

Лягушка и кузнечик#44250

В крайних клетках полоски шириной в одну клетку и длиной в N клеток сидят лягушка и кузнечик: лягушка в клетке № 1, кузнечик в клетке № N. Каждую секунду лягушка прыгает в сторону кузнечика, и одновременно кузнечик прыгает в сторону лягушки. Лягушка может прыгать только на две или на три клетки, кузнечик — только на одну или на две клетки. За какое наименьшее время они смогут оказаться в одной клетке?

Входные данные
Единственная строка входных данных содержит целое число N — длину клетчатой полосы (2 ≤ N ≤ 2 · 10⁹ ).
Выходные данные
Если лягушка и кузнечик могут оказаться в одной клетке, требуется вывести одно целое число — минимальное количество секунд, через которое они встретятся. Если они не смогут оказаться в одной клетке, требуется вывести число «-1» (без кавычек).

Примеры

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

Замечание
В первом примере лягушка может прыгнуть из клетки 1 в клетки 3 и 4, а кузнечик может прыгнуть из клетки 5 в клетки 3 и 4. Поэтому через 1 секунду они могут оказаться в одной клетке.
Во втором примере лягушка и кузнечик могут встретиться через 2 секунды. Например, лягушка прыгает в клетку 3, затем в клетку 6, а кузнечик прыгает в клетку 8, затем в клетку 6.

Вывод формулы Разбор случаев

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

Когда же Новый год?#44032

Томми очень любит Новый год! 31 декабря в этом году приходится на субботу. Томми захотел узнать, сколько дней осталось до 31 декабря. Мы знаем, что сегодня будний день S (по-английски) и 31 декабря уже на этой неделе в субботу. Помогите Томми определить сколько дней оставалось до 31 декабря после сегодня (считая день 31 декабря, но не считая сегодняшний день S)?

Входные данные
На вход подается строка S (S может быть Monday(понедельник), Tuesday(вторник), Wednesday(среда), Thursday(четверг) или Friday(пятница)).

Выходные данные
Выведите на экран ответ на задачу

Используйте вложенные условия (конструкцию elif для языка Python и else if для других языков).

Примеры

№	Входные данные	Выходные данные
1	Wednesday	3

Строки Условный оператор

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

Радостная фигура#43714

Маленький Миша любит играть счетными палочками. Счетные палочки он берет у своей сестры первоклассницы. Так как он редко возвращает их назад, маме приходится часто покупать новые палочки. Поэтому не все палочки у Миши одинаковые, но все палочки имеют целочисленную длину.
Сегодня Миша строит из палочек следующую фигуру. Он начал из угла комнаты. Мы с вами обозначим, условно, этот угол координатой (0, 0). Дальше Миша выкладывает палочку параллельно одной из двух стен, исходящей из данного угла. Будем считать, что стены ровные и образуют друг с другом в точке (0, 0) угол 90 градусов. При этом, Миша никогда не выкладывает две подряд палочки одновременно параллельно одной и той же стене (другими словами, он всегда чередует направление палочек).
Миша, хоть и маленький и не знает геометрии, но все же всегда радуется, если конец его фигуры находится как можно дальше от стартового угла. Помогите Мише выложить фигуру, которая его обрадует. Любые две палочки, которые выкладывает Миша всегда имеют минимум одну точку касания или пересечения.

Входные данные
Программа получает на вход несколько строк. Первая строка содержит целое число n (1<= n <= 100000) — количество палочек, которые есть у Миши. Вторая строка содержит n целых чисел a₁,...,a_n (1 <= a_i<= 10000) - длины Мишиных палочек.

Выходные данные
Выведите одно целое число — квадрат максимального расстояния от угла с координатой (0,0) до конечной точки фигуры, которую построил Миша.

Примеры

№	Входные данные	Выходные данные
1	3 1 2 3	26
2	4 1 1 2 2	20

Жадный алгоритм Использование сортировки

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

Пробежка#42944

Выходя на пробежку Рита берёт с собой телефон для прослушивания музыки и беспроводные наушники. Перед каждой пробежкой Рита заряжает наушники, и этой зарядки хватает на A минут прослушивания музыки. Рита решила, что каждый день она будет тренироваться на минуту дольше, чем в предыдущий день. То есть если в первый день Рита бегала и слушала музыку в течение B минут, во второй день она будет бегать B + 1 минуту, в третий день — B + 2 минуты и т.д.
Если заряда наушников хватает на большее время, чем продолжительность пробежки, то неиспользованный заряд накапливается и может быть использован в последующие дни. Емкость аккумулятора наушников можно считать неограниченной.
Определите, в какой день Рите впервые не хватит заряда для прослушивания музыки во время всей пробежки.

Входные данные
Первая строка входных данных содержит целое число A (1 <= A <= 10⁹ ) — величина ежедневного заряда аккумулятора (в минутах прослушивания музыки). Вторая строка входных данных содержит целое число B (1 <= B <= 10⁹ ) — продолжительность пробежки в первый день.

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

Примеры

№	Входные данные	Выходные данные
1	42 40	6

Вывод формулы Линейные алгоритмы

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