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

Результаты олимпиады#48944

В олимпиаде участвовало N человек. Каждый получил определенное количество баллов, при этом оказалось,что у всех участников — разное число баллов.

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

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

Формат входных данных
Выведите список участников (только фамилии) в порядке убывания набранных баллов.

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

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

Минимизируем число#48942

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

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

Формат выходных данных
Выведите минимальное натуральное четырехзначное число, состоящее из тех же цифр.

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

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

Первый уникальный#46033

Символ называется уникальным, если он встречается в строке один раз. Первый уникальный символ - это уникальный символ с наименьшим индексом.
Дана строка s. Найдите первый уникальный символ в данной строке. Выведите его индекс. Если в строке нет уникальных символов, выведите -1.

Входные данные
Программа получает на вход последовательность непробельных символов s.

Ограничения
'a' <= s[i] <= 'z'
0 <= i <= 255

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

Примеры

№	Входные данные	Выходные данные
1	silvertests	1
2	sstt	-1

Сортировка подсчетом Строки

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

Сортировка строк матрицы по половинам#46032

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

Входные данные
В первой строке записаны два целых числа N и M - количество строк и столбцов матрицы соответственно. Далее идет N строк, каждая из которых содержит по M чисел, разделенных одним пробелом - элементы массива (nums).

Ограничения
1 <= N, M <= 10³
-10⁹ <= nums_i,j <= 10⁹

Выходные данные
Выведите отсортированный массив.

Примеры

№	Входные данные	Выходные данные
1	3 5 4 0 2 1 3 1 3 2 0 0 1 1 2 1 1	1 1 2 1 1 1 3 2 0 0 4 0 2 1 3

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

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

Сортировка матрицы по сумме строк#46031

Напишите программу, которая сортирует строки двумерного массива целых чисел (nums) по возрастанию суммы элементов строк. В случае равенства суммы двух строк эти строки должны идти в порядке возрастания суммы первого и последнего элементов строки.

Входные данные
В первой строке записаны два целых числа N и M - количество строк и столбцов матрицы соответственно. Далее идет N строк, каждая из которых содержит по M чисел, разделенных одним пробелом - элементы массива (nums).

Ограничения
1 <= N, M <= 10³
-10⁹ <= nums_i,j <= 10⁹

Выходные данные
Выведите отсортированный массив.

Примеры

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

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

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

Сортировка двумерного массива#45719

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

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

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

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

Программа должна вывести отсортированный двумерный массив.

Примеры

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

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

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

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

Два массива (lite)#45459

Алиса со своим отцом профессором Селезневым записывают на листочке числа определенной последовательности. У Алисы каждый i-й член последовательности равен i², у профессора Селезнева i-й член последовательности равен i³. Они решили создать новую возрастающую последовательность путем объединения двух своих последовательностей. При этом, если в обоих последовательностях есть одинаковое число, то в новой последовательности оно присутствует только один раз.

Алиса и профессор просят вас угадать i-е число в новой объединенной последовательности.

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

В единственной строке входного файла дано натуральное число i (1 <= i <= 10⁷).

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

Выведите i-е число новой последовательности.

Примеры

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

Сортировка слиянием

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

Сортировка слиянием#45458

Отсортируйте данный массив, используя сортировку слиянием.

Входные данные
Первая строка входных данных содержит количество элементов в массиве N, N <= 10⁵. Далее идет N целых чисел, не превосходящих по абсолютной величине 10⁹.

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

Примеры

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

Сортировка слиянием

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

Относительная сортировка#45263

Даны два массива arr1 и arr2. Элементы массива arr2 различны, и при этом все элементы arr2 содержатся в arr1.

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

Входные данные
Первая строка входных данных содержит целое число n - количество элементов в массиве arr1, вторая строка содержит n целых чисел - элементы массива arr1. Третья строка содержит целое число m - количество элементов в массиве arr2, четвертая строка содержит m целых чисел - элементы массива arr2.

Ограничения на входные данные

1 <= n, m <= 10⁶
0 <= arr1[i], arr2[i] <= 1000
Все элементы массива arr2 различны.
Каждый элемент массива arr2[i] содержится в массиве arr1.

Выходные данные
Выведите, отсортированный по условию задачи, массив arr1.

Примеры

№	Входные данные	Выходные данные
1	11 2 3 1 3 2 4 6 7 9 2 19 6 2 1 4 3 9 6	2 2 2 1 4 3 3 9 6 7 19
2	6 28 6 22 8 44 17 4 22 28 8 6	22 28 8 6 17 44

Сортировка подсчетом

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

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	4 1 43 12 10	43 12 10 1

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

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

Сортировка по квадратам чисел#45240

Дан массив целых чисел. Верните отсортированный по неубыванию массив квадратов исходных чисел.

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

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

Примеры

№	Входные данные	Выходные данные
1	5 -1 -4 3 0 10	0 1 9 16 100
2	3 3 -1 1	1 1 9

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

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

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

Радостная фигура#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средняяВойти и решать

Ресторан#39963

Ресторан получил n заказов на проведение банкета. Каждый заказ характеризуется двумя величинами: моментом начала банкета l_i и моментом конца r_i (l_i ≤ r_i).

Руководство ресторана может либо принять заказ, либо отвергнуть его. Какое наибольшее количество заказов может быть принято?

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

Входные данные:
В первой строке находится целое число n (1 ≤ n ≤ 200000) — количество заказов. В каждой из следующих n строк находится пара целых чисел l_i, r_i (0 ≤ l_i ≤ r_i ≤ 10⁹).

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

Примеры:

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

Бинарный поиск в массиве Динамическое программирование Использование сортировки

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

Гошина последовательность#39249

Любитель математики Гоша придумал свою собственную последовательность. Правила в его последовательности следующие:
1) все числа в последовательности имеют свой номер;
2) первый элемент последовательности имеет номер 1;
3) каждое число в последовательности должно делится на свой номер;
4) число с большим номером, должно быть больше, чем число с меньшим номером.

Пример Гошиной последовательности: 1 4 6 8 10 18 21.

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

Входные данные
В первой строке записано число N - количество чисел в файле (N <= 10⁵). Далее идет N натуральных чисел (не больше 10⁶), каждое - в отдельной строке.

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

Примеры

№	Входные данные	Выходные данные
1	12 25 17 20 15 6 9 10 12 5 3 4 1	5 25

ЕГЭ_информатика Использование сортировки

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

Любимый фрукт#38781

У всех жителей Цветочного города спросили его любимый фрукт. Определите самый любимый фрукт среди всех жителей Цветочного города.

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

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

Пример

№	Входные данные	Выходные данные
1	apple orange banana banana orange END!	banana

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

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

Гости#38678

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

Формат входных данных
В первой строке записаны целое число N (1 ≤ N ≤ 100000) - количество друзей Васи. В следующих N строках записано по два целых числа A_i и B_i (оба числа от 1 до 10⁹) - возможное время приезда i-го друга.

Формат выходных данных
Выведите N пар чисел L_i и R_i - номера дней, в которые приедет и уедет i-й друг соответственно (A_i ≤ L_i ≤ R_i ≤ B_i). Если i-го друга приглашать не нужно, выведите пару чисел -1 -1. Если правильных ответов несколько - выведите любой из них.

Примеры

№	Входные данные	Выходные данные
1	3 1 2 2 4 3 5	1 2 3 4 5 5
2	3 2 3 1 4 3 5	-1 -1 1 4 5 5

Жадный алгоритм Сортировка событий

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

Ироха любит строки#38481

У Ирохи есть последовательность из N строк s₁, s₂, .., s_N. Каждая строка длиной L. Ироха хочет объединить все строки, чтобы получить очень длинную строку. Среди всех строк, которые она может получить таким образом, найдите лексикографически наименьшую.

Будем считать, что строка s = s₁s₂...s_nлексикографически меньше строки t = t₁t₂...t_m, если выполняется одно из следующих условий:
- существует индекс i (\(1<=i<=min(n,m)\)), такой что \(s_j =t_j \), для всех индексов j (\(1<=j<=i\)), и \(s_i <t_i \);
- \(s_i=t_j\) для всех i (\(1<=i<=min(n,m)\)), и \(n<m\).

Входные данные
В первой строке задаются числа N и L. Далее идут строки s₁, s₂, .., s_N, каждая в отдельной строке.

Выходные данные
Выведите лексикографически наименьшую строку, которую может создать Ироха.

Примеры

№	Входные данные	Выходные данные
1	3 3 dxx axx cxx	axxcxxdxx

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

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