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

Древние цивилизации#54296

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

Петя предположил, что между цивилизациями A и B
происходил культурный обмен, если они сосуществовали в течение некоторого ненулевого промежутка времени. Например, если цивилизация A зародилась в 600 году до н.э. и существовала до 400 года до н.э., а цивилизация B зародилась в 450 году до н.э. и существовала до 300 года до н.э., то культура каждой из этих цивилизаций оказывала влияние на развитие другой цивилизации в течение 50 лет. В то же время, если цивилизация C зародилась в 400 году до н.э. и существовала до 50 года до н.э., то она не смогла осуществить культурного обмена с цивилизацией A, в то время как культурный обмен с цивилизацией B продолжался в течение 100 лет.

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

Входные данные
В первой строке вводится число N – количество цивилизаций, культура которых интересует Петю (1≤N≤100 000). Следующие N строк содержат описание цивилизаций – в каждой строке задаются два целых числа Si и E_i
– год зарождения и год гибели соответствующей цивилизации. Все числа не превосходят 10⁹
по абсолютной величине, S_i < E_i.

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

Быстрая сортировка Сканирующая прямая

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

Есть n стульев...#49857

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

В офисе есть \(n\) стульев, \(i\)-й из которых имеет высоту \(h_i\) и ширину \(w_i\). Влад планирует выбрать любой набор офисных стульев \([i_1, i_2, \ldots, i_k]\) и расположить в ряд, чтобы на них можно было лечь. Рост Влада равен \(H\), поэтому, чтобы он мог удобно лежать, необходимо, чтобы суммарная ширина выбранных стульев была не меньше \(H\), то есть \[\sum\limits_{j=1}^k w_{i_j} \ge H \text{.}\]

Очевидно, что спать на стульях разной высоты неудобно. Назовем неудобностью выбранного набора максимальную разность высот двух соседних стульев в ряду, то есть \(\max\limits_{j=2}^k |h_{i_j} - h_{i_{j-1}}|\). Если набор состоит из одного стула, его неудобность равна \(0\).

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

Формат входных данных
В первой строке ввода через пробел даны два целых числа \(n\) и \(H\) — количество стульев и рост Влада (\(1 \le n \le 2 \cdot 10^5\); \(1 \le H \le 10^9\)).

Во второй строке ввода через пробел перечислены \(n\) целых чисел \(h_i\) — высоты стульев (\(1 \le h_i \le 10^9\)). В третьей строке в том же формате перечислены \(n\) целых чисел \(w_i\), равных ширине стульев (\(1 \le w_i \le 10^9\)).

Гарантируется, что \(H\) не превосходит суммы всех \(w_i\).

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

Замечание

В первом примере нужно выставить стулья \(2\) и \(4\) в любом порядке.

Во втором примере можно выбрать, например, следующие наборы: \([1, 5]\), \([2, 4, 3]\). Обратите внимание, что порядок стульев в наборе важен: неудобность набора \([2, 3, 4]\) равна \(\max(|5 - 3|, |4 - 5|) = \max(2, 1) = 2\), что больше, чем для набора \([2, 4, 3]\).

Бинарный поиск по ответу Использование сортировки Сортировка событий

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

Наибольший отрезок, не содержащий точек#49417

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

Формат входных данных
В первой строке записано натуральное число N - количество отмеченных точек (2 <= N <= 10³). Во второй строке записано N целых чисел - координаты точек (каждое число по модулю не больше 10⁹).

Формат выходных данных
В первой строке выведите максимальную длину искомого отрезка. Во второй строке выведите координаты его концов (сначала левую координату, затем через пробел правую). Если таких отрезков несколько, то выведите тот отрезок, у которого наименьшая левая координата.

Использование сортировки Квадратичные сортировки

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

Сортировка времени#18731

Сортировка времени

Во входном файле записано сначала число N (1<=N<=100), а затем

N моментов времени. Каждый момент времени задается 3 целыми числами -

часы (от 0 до 23), минуты (от 0 до 60) и секунды (от 0 до 60).

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

неубывания (момент времени также выводится в виде трех чисел, ведущие нули

выводить не обязательно)

Пример входного файла:

10 20 30

7 30 00

23 59 59

13 30 30

Пример выходного файла:

7 30 0

10 20 30

13 30 30

23 59 59

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

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

Слова по длине#92157

Пользователь вводит количество слов, а затем сами слова — каждое на отдельной строке. Сохраните все слова в список.

Выведите две строки:

Исходный список — слова через пробел в порядке ввода.
Отсортированный список — слова через пробел по возрастанию длины. Если длины равны, сохраните порядок ввода.

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

Первая строка — целое число \(N\) (\(1 \le N \le 15\)).

Следующие \(N\) строк — по одному слову (строчные русские буквы, без пробелов).

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

Две строки: исходный список и отсортированный по возрастанию длины, слова через пробел.

Примечание

Подсказка: используйте key=len в функции sorted().

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

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

Числа по модулю#92156

Пользователь вводит количество чисел, а затем сами числа — каждое на отдельной строке. Сохраните все числа в список.

Выведите две строки:

Исходный список — числа через пробел в порядке ввода.
Отсортированный список — числа через пробел по возрастанию их модуля (абсолютного значения). Если модули равны, сохраните порядок ввода.

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

Первая строка — целое число \(N\) (\(1 \le N \le 20\)).

Следующие \(N\) строк — по одному целому числу (от \(-1000\) до \(1000\)).

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

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

Примечание

Модуль числа — это число без знака. Например, модуль числа \(-7\) равен \(7\), модуль числа \(3\) равен \(3\).

Подсказка: используйте key=abs в функции sorted().

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

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

Минимум, максимум и сортировка#92146

Пользователь вводит несколько целых чисел в одной строке через пробел. Выведите три строки: минимальное число, максимальное число и все числа в отсортированном порядке (по возрастанию).

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

Одна строка — целые числа через пробел (от 2 до 20 чисел, каждое от \(-1000\) до \(1000\)).

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

Три строки:

Минимальное число.
Максимальное число.
Все числа в порядке возрастания через пробел.

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

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

Имена по алфавиту#92145

Пользователь вводит несколько имён через пробел в одной строке. Выведите их в алфавитном порядке.

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

Одна строка — имена через пробел (от 2 до 15 имён). Все имена начинаются с заглавной буквы, остальные строчные. Имена состоят только из русских букв.

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

Одна строка — имена в алфавитном порядке через пробел.

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

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

Сортировка по убыванию#92144

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

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

Одна строка — целые числа через пробел (от 2 до 20 чисел, каждое от \(-1000\) до \(1000\)).

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

Одна строка — те же числа, отсортированные по убыванию, через пробел.

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

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

Словарь длин слов#92138

Пользователь вводит несколько слов через пробел. Постройте словарь, где ключ — слово, значение — его длина. Выведите пары в формате слово: длина, отсортированные по длине в порядке возрастания. Если длины одинаковые, сортируйте по алфавиту.

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

Одна строка — слова через пробел (от 2 до 15 слов). Все слова различны.

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

Строки в формате слово: длина, отсортированные по длине (по возрастанию), при равенстве — по алфавиту.

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

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

Миссия Пиксель. 6. Рейтинг Героев#91323

🏆

Шаг 6: Рейтинг героев

Средне

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

Условие задачи

Дана строка из N целых чисел — рейтинги героев. Выведи три строки:

все числа, отсортированные по возрастанию, через пробел;
три наибольших числа через пробел (от меньшего к большему);
среднее арифметическое, округлённое вниз (целочисленное деление).

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

Одна строка: N целых чисел через пробел (3 ≤ N ≤ 100, значения от 0 до 10000).

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

Три строки.

Алгоритмы обработки Использование сортировки

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

65813#65813

В школе в очередной раз заболел преподаватель физкультуры Виктор Дмитриевич. Поэтому директор принял решение, что кто-то из свободных учителей проведёт занятие. После долгих размышлений, самым свободным оказался учитель информатики Анатолий Иванович, который очень любит алгоритмы сортировки, что вызвало сразу проблему у учеников. Ведь Анатолий Иванович первым делом сказал ребятам построиться в шеренгу, но не как обычно (по убыванию роста, ), а так, чтобы каждое нечётное место было отсортировано по росту по убыванию (первое место - самый высокий ученик, третье место выше пятого, пятое выше седьмого и так далее)), а каждое чётное по возрастанию (второе место - самый низкий ученик, четвёртый второй по росту среди всех, шестой - третий по росту среди всех и так далее) (учеников Анатолий Иванович нумеровал с 1).
Помогите ученикам получить правильный порядок, как встать им в шеренгу так, чтобы Анатолий Иванович оказался доволен.
Формат входных данных
На первой строке подаётся число N (1 <= N <= 121)– количество учеников в классе.
На N последующих строках подаются строки вида имя-рост (например, «Ivan 175»), где на первом месте указывается имя ученика – оно всегда одним словом на английском языке, без пробелов, а в конце указывается рост ученика (целое число от 100 до 220).
Формат выходных данных
Выведите имена учеников в одну строку через пробел, как они должны встать на уроке физкультуры.
Примечание:
Имена учеников у всех уникальны, рост ни у кого не повторяется.

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

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

Подсчет пар#50778

Вам дан массив A из N чисел. Найдите количество различных пар (i, j), таких, что j>=i и A[i] = A[j].

Формат входных данных
Первая строка входных данных содержит количество тестовых случаев T. Каждый тестовый случай состоит из двух строк, первая строка - число N, за ней следует строка, состоящая из N целых чисел, которые являются элементами массива A.

Ограничения

1 <= T <= 10

1 <= N <= 10⁶ 

-10⁶ <= A[i] <= 10⁶

0 <= i < N

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

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

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

Урок физкультуры#50574

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

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

Формат входных данных
Первая строка содержит целое число \(n\) — число учеников в классе (\(2 \le n \le 50\)). Следующие \(n\) строк содержат по два целых числа каждая: \(a_i\) и \(h_i\) — пол и рост в сантиметрах \(i\)-го ученика (\(a_i\) равно 0 или 1, \(100 \le h_i \le 200\)). Значение \(a_i = 0\) означает, что \(i\)-й ученик — мальчик, а значение \(a_i = 1\) означает, что \(i\)-й ученик — девочка.

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

Сортировка "пузырьком"

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

Решение задач#50541

В этой задаче Вася готовится к олимпиаде. Учитель дал ему \(N\) (\(1 \le N \le 100\)) задач для тренировки. Для каждой из этих задач известно, каким умением \(a_i\) нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения \(i\)-й задачи Васино умение увеличивается на число \(b_i\).

Исходное умение Васи равно \(A\). Решать данные учителем задачи он может в произвольном порядке. Какое максимальное количество задач он сможет решить, если выберет самый лучший порядок их решения?

Формат входных данных
Сначала вводятся два целых числа \(N\), \(A\) (\(1 \le N \le 100\), \(0 \le A \le 100\)) — количество задач и исходное умение. Далее идут \(N\) пар целых чисел \(a_i\), \(b_i\) (\(1 \le a_i \le 100\), \(1 \le b_i \le 100\)) — соответственно сколько умения нужно для решения \(i\)-й задачи и сколько умения прибавится после её решения.

Формат выходных данных
Выведите одно число — максимальное количество задач, которое Вася может решить.

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

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

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

Цветочный магазин#50363

Петя открыл цветочный магазин. Магазин Пети занимается изготовлением и продажей букетов. Всего существует \(n\) видов цветов, занумерованных от 1 до \(n\). Каждый букет, чтобы быть гармоничным и красивым, должен состоять из цветов всех видов, по одной штуке каждого вида. В магазине уже есть \(a_i\) штук цветов вида \(i\). На цветочной базе можно купить цветок любого вида за 1 рубль.

Определите, сколько букетов сможет собрать Петя, если потратит не более \(x\) рублей на покупку цветов на базе. Ответьте на \(q\) запросов с различными \(x_i\).

Формат входных данных
В первой строке входных данных находятся два целых числа \(n\) и \(q\) (\(1 \le n, q \le 10^5\)) — количество различных типов цветов и количество запросов.

Во второй строке находятся \(n\) целых чисел \(a_1, a_2, \cdots, a_n\) (\(0 \le a_i \le 10^9\)) — количество цветов каждого вида, имеющихся в магазине.

В третьей строке находятся \(q\) целых чисел \(x_1, x_2, \cdots, x_q\) (\(0 \le x_i \le 10^9\)) — запросы Пети.

Формат выходных данных
Выходной файл должен содержать \(q\) чисел, где \(i\)-е число это максимальное количество букетов, которое можно собрать потратив не более \(x_i\) рублей.

Примечание
В первом примере у Пети изначально есть 1 цветок первого типа и 0 цветов второго типа.

В первом запросе у него есть 1 рубль, он покупает цветок второго типа и делает 1 букет.

Во втором запросе у него есть 2 рубля, он не может сделать два букета за 2 рубля, поэтому ответ по прежнему 1.

В третьем запросе у него есть 5 рублей, он покупает 2 цветка первого типа и 3 цветка второго типа и делает 3 букета.

Бинарный поиск по ответу Использование сортировки Префиксные суммы(минимумы, ...)

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

Радиация#50339

Космический аппарат "Звезда" выполняет задачу по фиксации показаний уровня космической радиации. Каждое показание записывается в виде целого числа. В процессе первоначальной обработки данных, для устранения потенциально неточных результатов, убирают из списка K наибольших и K наименьших показаний.
Исходя из списка полученных показаний и количестве исключаемых показаний, определите самое высокое точное показание и целую часть среднего арифметического всех точных показаний.

Формат входных данных
В первой строке записаны два числа через пробел: N – общее количество показаний (натуральное число, не превышающее 10 000) и K – количество исключаемых минимальных и максимальных показаний. В следующих N строках находятся значений каждого показания (все числа натуральные, не превышающие 10000), каждое в отдельной строке.

Формат выходных данных
Запишите в ответе два числа: сначала наибольшего точного показания, а затем целую часть среднего арифметического всех точных показаний.

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

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

Спортивная акция - 2#50144

В магазине спортивных товаров проходит акция. На K товаров с самой высокой ценой установлена скидка в размере d%. Причем, от каждой цены, после применения скидки, отбрасываются копейки. Администрация магазина хочет узнать, какую сумму они получат от продажи всех товаров по акции.

Входные данные
В первой строке вводят три числа, записанные через пробел: N – общее количество товаров (натуральное число, не превышающее 100 000), K – количество товаров (1 < K < N), d - размер скидки в процентах (5 < d < 50). В следующих N строках находятся значения цены каждого из товаров (все числа натуральные, не превышающие 10 000), каждое в отдельной строке. Гарантируется, что ответ не превышает 10⁹.

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

Примечание
Стоимость товара со скидкой выисляется по следующей формуле:
Цена со скидкой = Исходная цена - Исходная цена * (Процент скидки / 100).

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

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

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

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

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

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

Сортировка по сумме элементов в столбце - 1#49711

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

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

Формат выходных данных
Программа должна вывести получившуюся матрицу.

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

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