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

Самая частая сумма#33480

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

Напишите эффективную по времени и по памяти программу для решения этой задачи.

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

Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.

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

В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.

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

Выведите одно число - искомый ответ.

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

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

Обувной магазин#33474

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

Формат входных данных
Сначала вводится размер ноги покупателя (обувь меньшего размера он надеть не сможет), затем количество пар обуви в магазине и размер каждой пары. Размер — натуральное число, не превосходящее 100, количество пар обуви в магазине - неотрицательное число, не превосходит 1000.

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

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

✓ 465✗ 2 276700средняяВойти и решать

Сортировка по сумме цифр#33470

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

Входные данные
Первая строка содержит размер массива N . Во второй строке через пробел задаются N чисел – элементы массива. Гарантируется, что 0 < N ≤ 10000 .

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

Ввод	Вывод
6 9 21 32 55 81 11	55 9 81 32 21 11

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

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

Файловый менеджер#33310

Петя работает над очень большим проектом. Проект содержит N файлов. В процессе работы Пете часто приходится просматривать и редактировать файлы. Для ускорения работы Петя использует файловый менеджер Fur Manager, который отображает список имен файлов проекта в некотором порядке.

В текущей версии Fur Manager’a для перемещения по списку имен файлов есть следующие возможности:

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

можно нажать клавишу вверх, при этом курсор перемещается на предыдущий файл в списке, для первого файла предыдущим считается последний;

можно нажать клавишу Alt и, удерживая ее, набрать последовательность латинских букв. После этого клавишу Alt следует отпустить, и в этот момент курсор переместится на ближайший файл, имя которого начинается c заданной последовательности символов. Ближайший файл — это файл, на который можно переместиться за наименьшее количество нажатий клавиши вниз. Если заданная последовательность является началом имени текущего файла, или файла, имя которого начинается с этой последовательности, не существует, то курсор останется на месте.

Первая и вторая из описанных возможностей файлового менеджера требуют по одному нажатию клавиши, а третья — одного нажатия (нажатие клавиши Alt) плюс количество нажатий, равное длине набранной последовательности латинских букв.

Файлы пронумерованы от 1 до N в порядке их следования. После загрузки Fur Manager’а курсор находится на первом файле.

Петя знает, что ему сначала придется редактировать файл с номером a₁, затем с номером a₂ и так далее, а последним — файл с номером a_k. В последовательности a₁, a₂, ..., a_k один и тот же номер может встречаться несколько раз. При каждом перемещении от одного файла к другому Петя хочет нажимать как можно меньше клавиш.

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

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

В первой строке входных данных содержится целое число N (1 ≤ N ≤ 1000) — количество файлов в проекте.

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

Далее в следующей строке записано целое число k (1 ≤ k ≤ 10).

Последняя строка входных данных содержит k целых чисел a₁, a₂, ..., a_k (1 ≤ a_i ≤ N) — номера редактируемых файлов. Редактирование файлов выполняется в том порядке, в котором они встречаются в последовательности a₁, a₂, ..., a_k.

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

Выведите описание искомой последовательности нажатий клавиш в виде k блоков информации:

первый блок информации описывает перемещение от файла с номером 1 к файлу с номером a₁;

второй блок информации описывает перемещение от файла с номером a1 к файлу с номером a₂;

…

k-ый блок информации описывает перемещение от файла с номером a_k–1 к файлу с номером a_k.

Каждый блок информации выглядит следующим образом.

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

Следующие L строк блока описывают нажимаемые клавиши. Каждая из строк содержит описание одной клавиши:

если нажимается клавиша вниз, то в строке записывается слово down;

если нажимается клавиша вверх, то в строке записывается слово up;

если нажимается клавиша Alt, то в строке записывается слово Alt;

при нажатии клавиши с латинской буквой выводится соответствующая ей латинская буква.

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

Ввод	Вывод
6 a b c d e f 4 4 3 1 6	2 Alt d 1 up 2 Alt a 1 up

Алгоритм Дейкстры Быстрая сортировка Способы задания графа

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

Сортировка по цифрам числа 2#33207

Дано N трехзначных чисел (1<=N<=1000). Необходимо вывести их в порядке возрастания.

Нельзя использовать встроенную сортировку

Пример
Входные данные

639 265 915 993 436 202 573 906 490

Выходные данные
202 265 436 490 573 639 906 915 993

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

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

Сортировка по цифрам числа 1#33206

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

Формат входных данных
В первой строке записано натуральное число N (1<=N<=1000). Вторая строка содержит n двузначных положительных чисел nums_i (1 ≤ i ≤ n, 10 ≤ nums_i ≤ 99).

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

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

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

Пятый самый легкий#33205

Формат входных данных
В первой строке записано натуральное число n (n < 100). Вторая строка содержит n положительных целых чисел m_i - вес i-го предмета (1 ≤ i ≤ n, 1 ≤ ai ≤ 10⁵).

Формат выходных данных
Напечатайте массу предмета, являющегося "пятым самым легким предметом".

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

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

Средние в шеренге#33203

Формат входных данных
В первой строке записано натуральное число n (n < 100, n - четное). Вторая строка содержит n положительных целых чисел m_i - рост i-го учащегося (1 ≤ i ≤ n, 1 ≤ ai ≤ 10⁵).

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

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

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

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

В каждом из двух классов учатся по n человек (10 <= n <= 30). Известны средний балл каждого ученика каждого класса, подсчитанные по ряду предметов (все значения целые). Определить, в каком классе у "третьего из самых успевающих учеников" средняя оценка больше. Вывести цифру "1" - для первого класса, "2" - для второго. Если оценки равны, вывести эту оценку.

Формат входных данных
В первой строке записано натуральное число n (n < 100) - количество учеников в каждом классе . Вторая строка содержит n положительных целых чисел class1_i - средний балл i-го ученика первого класса (1 ≤ i ≤ n, 1 ≤ class1_i ≤ 10⁵). Третья строка содержит n положительных целых чисел class2_i - средний балл i-го ученика первого класса (1 ≤ i ≤ n, 1 ≤ class2_i ≤ 10⁵).

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

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

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

33100#33100

На вход программы подаются произвольные алфавитно-цифровые символы. Ввод этих символов заканчивается точкой. Требуется написать программу, которая будет печатать последовательность строчных английских букв ('a' 'b'... 'z') из входной последовательности и частот их повторения. Печать должна происходить в алфавитном порядке.

Например, пусть на вход подаются следующие символы:

fhb5kbfыshfm.

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

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

—Войти и решать

П №52#33098

Дед Мороз и Снегурочка приходят на детские утренники с мешком конфет. Дед Мороз делит конфеты поровну между всеми присутствующими детьми (детей на утреннике никогда не бывает больше 100), а оставшиеся конфеты отдает Снегурочке. Снегурочка каждый раз записывает в блокнот количество полученных конфет. Если конфеты разделились между всеми детьми без остатка, Снегурочка ничего не получает и ничего не записывает. Когда утренники закончились, Деду Морозу стало интересно, какое число чаще всего записывала Снегурочка. Дед Мороз и Снегурочка – волшебные, поэтому число утренников N, на которых они побывали, может быть очень большим. Напишите программу, которая будет решать эту задачу. Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию. Желательно, чтобы программа была эффективной как по времени работы, так и по используемой памяти. Программу будем считать эффективной по памяти, если используемая память не зависит от размера входных данных (то есть числа утренников). Программу будем считать эффективной по времени, если при увеличении размера входных данных N в t раз (t – любое число) время её работы увеличивается не более чем в t раз.

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

В первой строке вводится одно целое положительное число – количество утренников N. Каждая из следующих N строк содержит два целых числа: сначала D – количество пришедших на очередной утренник детей, а затем K – количество конфет в мешке Деда Мороза на этом утреннике. Гарантируется выполнение следующих соотношений: 1 ≤ N ≤ 10000, 1 ≤ D ≤ 100 (для каждого D), D ≤ K ≤ 1000 (для каждой пары D, K)

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

Программа должна вывести одно число – то, которое Снегурочка записывала чаще всего. Если несколько чисел записывались одинаково часто, надо вывести большее из них. Если Снегурочка ни разу ничего не записывала, надо вывести ноль.

Ввод	Вывод
7 10 58 15 315 20 408 100 1000 32 63 32 63 11 121	31

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

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

Объединение прямоугольников#32983

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

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

В первой строке входного файла указано число N (0≤N≤1500). В следующих N строках заданы по 4 целых числа x1, y1, x2, y2 — сначала координаты левого нижнего угла прямоугольника, потом правого верхнего (0≤x1≤x2≤10⁹, 0≤y1≤y2≤10⁹). Обратите внимание, что прямоугольники могут вырождаться в отрезки и даже в точки.

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

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

Ввод	Вывод
3 1 1 3 5 5 2 7 4 2 4 6 7	23
2 0 0 2 2 1 3 2 4	5

Сканирующая прямая

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

Минимальное покрытие#32982

На прямой задано некоторое множество отрезков с целочисленными координатами концов \([L_i, R_i]\). Выберите среди данного множества подмножество отрезков, целиком покрывающее отрезок \([0, M]\), (M — натуральное число), содержащее наименьшее число отрезков.

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

В первой строке указана константа M (\(1<=M<=5000\)). В каждой последующей строке записана пара чисел L_i и R_i (\(|L_i|,|R_i| < 50000\)), задающая координаты левого и правого концов отрезков. Список завершается парой нулей. Общее число отрезков не превышает 100 000.

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

В первой строке выходного файла выведите минимальное число отрезков, необходимое для покрытия отрезка \([0; M]\). Далее выведите список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe. Завершающие два нуля выводить не нужно. Если покрытие отрезка \([0; M]\) исходным множеством отрезков \([L_i, R_i]\) невозможно, то следует вывести единственную фразу “No solution”.

Примеры

№	Входные данные	Выходные данные
1	1 -1 0 -5 -3 2 5 0 0	No solution
2	1 -1 0 0 1 0 0	1 0 1

Сканирующая прямая

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

Лучшее место#32967

В зале ожидания на вокзале стоят N рядов из M кресел. Чтобы ожидающие не скучали, вместо некоторых кресел установлено K мощных Wi-Fi роутеров. Ожидающие стараются занять места ближе к роутерам, так как тогда они смогут смотреть ролики с Youtube или VK с более высоким разрешением, без задержек. Если пассажир сидит на месте с номером c в ряде r, а i-й роутер расположен на месте C_i в ряде R_i, то расстояние до i-го роутера вычисляется как max(|r−R_i|,|c−C_i|), где |x| – абсолютное значение x. Креслам в зале ожидания был присвоен приоритет от 1 до N⋅M−K, меньшие номера получили кресла с меньшим расстоянием до ближайшего роутера, среди кресел с одинаковым расстоянием до роутеров более удобными считаются кресла, стоящие в ряду с меньшим номером, а среди них — с меньшим номером места в ряду. На рисунке показан приоритет кресел в зале ожидания с 4 рядами из 7 кресел, в котором установлены 2 роутера (их позиции помечены черным цветом). Темно-серым цветом выделены кресла, стоящие на расстоянии 1 от роутеров, светло-серым — на расстоянии 2, белым — 3.

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

Первая строка ввода содержит четыре целых чисел — количество рядов N (2 ≤ N ≤ 10⁹) и мест в ряду M (2 ≤ M ≤ 10⁹), количество роутеров K (1 ≤ K ≤ 100, K < N⋅M), количество запросов Q (1 ≤ Q ≤ 100). Далее следует K строк, содержащих два целых числа — местонахождение роутеров: номер ряда Ri (1 ≤ R_i ≤ N) и номер места в ряду C_i (1 ≤ С_i ≤ M). Среди них нет совпадающих. Далее следует строка, содержащая Q целых чисел в диапазоне от 1 до N⋅M−K – приоритеты кресел.

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

Ввод	Вывод
4 7 2 4 2 5 4 4 1 6 16 26	1 1 2 3

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

✓ 1✗ 131 300средняяВойти и решать

Классификация снежинок#31926

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

Напишите программу, которая поможет Стелле провести классификацию снежинок.

Первая строка ввода содержит одно целое число N (2 ≤ N ≤ 100000). Далее следует N строк, содержащих по 6 целых чисел a₁ a₂ a₃ a₄ a₅ a₆ от 1 до 10⁹, разделенных пробелами – длины лучей снежинок в порядке обхода по часовой стрелке.

Вывести одно целое число – количество различных снежинок, обнаруженных Стеллой.

Ввод	Вывод
5 1 2 3 4 5 6 3 4 5 6 1 2 3 2 1 4 5 6 6 5 4 3 2 1 2 3 6 5 4 1	2

Примечание
Совпадают снежинки 1 и 2 и 4 после поворота или после переворачивания и снежинки 3 и 5 после переворачивания и поворота.

Быстрая сортировка

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

Покраска забора#31880

Однажды, в наказание за шалости и обман, тетя Полли заставила Тома красить забор длиной L ярдов. Все вы прекрасно помните, что Том продавал (за различные ништячки) свою работу другим мальчишкам, которые хотели побелить забор.
К тому моменту, когда у Тома закончилась известка, забор успели покрасить N мальчишек. И так как за мальчишками Том не особо следил, то каждый красил ту часть забора, которая ему больше нравилась.
Каждый i-й мальчишка начинал красить забор с вертикальной дощечки с координатой Left_i и красил до дощечки с координатой Right_i(длину дощечки считать равной 1).
Определите длину забора, которую необходимо будет докрасить Тому самостоятельно.

Входные данные
В первой строке находится число L - длина забора тети Полли. Во второй строке находится число N, в следующих N строках - пары Left_i и Right_i. Все числа - целые
Ограничения:
\(0 <= L <= 2 \cdot 10^9\);
\(-10^9 <= Left_i <= Right_i <= 10^9\);
\(1 <= N <= 15 000\).

Выходные данные
Вывести одно число - длину забора, которую необходимо докрасить Тому.

Примеры

№	Входные данные	Выходные данные
1	20 1 10 20	10
2	10 1 10 10	10
3	100 2 10 30 20 40	70

Быстрая сортировка

✓ 223✗ 1 124900средняяВойти и решать

Анти-QuickSort#31879

Дано число N (1<=N<=1000), а затем N натуральных чисел из диапазона от 1 до 100.
Вывести перестановку элементов массива, на которой быстрая сортировка выполнит максимальное число сравнений, при условии, что "опорным" будет элемент посередине.

Входные данные: в первой строке задаётся число N
Во второй строке идут N чисел - элементы массива
Выходные данные: выведите требуемую перестановку элементов исходного массива

Примеры

№	Входные данные	Выходные данные
1	5 3 10 1 20 7	3 20 7 1 10

Быстрая сортировка

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

Перетягивание каната#30717

В 2086 году в программу зимней олимпиады решено было добавить соревнования по перетягиванию каната на льду. Для проведения финала соревнования организаторы нашли n кусков каната. Для повышения зрелищности соревнования решено было сделать связать некоторые из этих кусков в один как можно более длинный канат.

Когда начались работы по связыванию, выяснилось, что на узел, связывающий два куска каната между собой, уходит по d сантиметров каната с каждого из связываемых концов. Также, оказалось, что связывать так, что получающиеся узлы находятся близко друг к другу, невозможно: расстояние между соседними узлами должно быть хотя бы d сантиметров. Например, если d = 10, то после связывания кусков каната длиной 25 и 50 сантиметров, получается канат длиной 55 сантиметров, в 15 сантиметрах от одного из краев которого находится узел.

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

Формат входных данных
В первой строке заданы числа n (1 ≤ n ≤ 100 000) и d (1 ≤ d ≤ 1000) — количество кусков каната и длина каната, уходящая на завязывание узла. Во второй строке заданы n чисел ai (1 ≤ a_i ≤ 1000) — длины имеющихся кусков каната.

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

Ввод	Вывод
2 10 25 50	55
5 2 4 5 6 7 8	14

Алгоритмы сортировки Задача на реализацию

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

Покраска забора#30713

Том Сойер уговорил n своих друзей помочь ему в нелегком деле покраски забора, окружающего дом тетушки Полли. Забор представляет собой k последовательных досок, пронумерованных от 1 до k, причем после k-й доски опять идет первая.

Друзья Тома очень привередливы, i-й друг согласен участвовать в покраске только в том случае, если ему дадут покрасить участок из ровно ai последовательных досок. Кисточка у Тома только одна, поэтому друзья будут красить по очереди и сразу весь отведенный им отрезок. Тому остается лишь выбрать порядок, в котором приглашать друзей, а также выбрать для каждого желаемое количество последовательных досок.

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

Помогите Тому понять, сколько радости он сможет доставить своим друзьям.

Формат входных данных
Первая строка входного файла содержит два целых числа n (1 ≤ n ≤ 10⁵ ) и k (1 ≤ k ≤ 10⁹ ). Следующая строка содержит n целых чисел — значения a_i (1 ≤ a_i ≤ k).

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

Ввод	Вывод
2 100 5 10	5
4 10 7 8 3 5	2

Пояснение
В первом примере x = 5, так как один из друзей просто не хочет красить больше пяти досок. Он придет первым, покрасит свои пять, после чего еще 10 неокрашенных досок достанется второму другу Тома. Оставшиеся 85 досок Тому придется красить самому.
Во втором примере достичь x = 2 можно, например, так. Сначала третий друг красит доски с 4 по 6 (3 неокрашенных доски). Затем четвертый друг красит доски с 1 по 5 (3 неокрашенных доски). Затем второй друг красит доски с 1 по 8 (2 неокрашенных доски). Наконец, первый друг красит доски с 6 по 10 и с 1 по 2 (2 неокрашенных доски, заметим, что забор идет по циклу и эти доски образуют последовательный отрезок).

Сканирующая прямая

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

Сложная сортировка массива структур#30690

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

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

Сначала задано число N - количество людей в списке (1<= N <= 100). Далее через пробел записаны N фамилий и мен.

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

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

Примеры

№	Входные данные	Выходные данные
1	3 Sidorov Petr Ivanov Ivan Ivanov Anton	Ivanov Anton Ivanov Ivan Sidorov Petr

Сортировка записей

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