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

Гимнастические ленты#39226

Для выступления гимнастки используют ленты, которые после выступления кладут на стол. Папа самой лучшей гимнастки Анны К., в ожидании награждения, решил записывать координаты начала и конца лент. Если лента свисала с левого края стола, то он ставил левую координату равной нулю, если лента свисала с правого конца стола, то он ставил правую координату равной нулю. Если лента свисала с двух сторон, то он записывал обе координаты равной нулю. У вас есть файл с данной информацией. Определите, в скольки точках стола получилась самая большая толщина покрытия и чему она равна. Стол имеет длину Lмм. По окончании выступления всех гимнасток, на столе оказалось N лент. У некоторых лент свисает со стола только один конец, у некоторых оба. Все ленты лежат горизонтально. Ленты складываются друг на друга.

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

В первой строке файла записаны два числа - L, N (1 <= L <= 10000, 1 <= N <= 10000). В слеующих N строках записаны по 2 числа - l, r (1 <= l <= r <= L) - левые и правые концы лент относительно левого края стола.

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

Примеры

№	Входные данные	Выходные данные
1	39 4 3 21 3 15 2 20 3 17	4 13

Файл к заданию

ЕГЭ_информатика ЕГЭ-26. Обработка массива целых чисел. Сортировка Сортировка подсчетом

1 500труднаяВойти и решать

Суперстадион#39225

На планете Блук находится самый большой суперстадион Галактики. На суперстадионе 10 000 рядов, пронумерованных начиная с 1. В каждом ряду 10 000 мест, пронумерованных начиная с 1. К текущему моменту, на концерт Суперзвезды продали N билетов. В файле указана информация о проданных билетах: номер ряда и номер места в данном ряду. Определите, в каком ряду больше всего свободных мест, находящихся рядом. Если таких мест одинаковое количество в нескольких рядах, то укажите минимальный номер ряда. А также укажите минимальный номер места, с которого начинаются такие свободные места.

Входные данные
Первая строка входного файла содержит целое число N – общее количество проданных билетов. Каждая из следующих N строк содержит 2 целых числа: номер ряда и номер места в данном ряду.

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

Пример организации исходных данных во входном файле (при 5 рядах и 5 местах в ряду):

17 1 2 2 3 2 4 3 1 3 2 4 1 4 2 4 3 5 1 5 5 5 4 5 2 5 3 3 4 3 5 4 5 1 5

Ответ: 1 3

Файл к заданию

ЕГЭ_информатика ЕГЭ-26. Обработка массива целых чисел. Сортировка Использование сортировки

1 300труднаяВойти и решать

Анализ файла - 08#39159

Текстовый файл состоит из символов M, A, R, S. Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых нет идущих подряд символов M. Для выполнения этого задания следует написать программу.

Файл к заданию

ЕГЭ_информатика ЕГЭ-24. Обработка символьных строк Обработка текста

1 200труднаяВойти и решать

Сломанный принтер#39062

Сломанный цветной принтер, печатая цифры, закрашивает все замкнутые области в красный цвет. Например, в цифрах 0, 4, 6, 9 одна замкнутая область. В цифре 8 - 2 замкнутых области. В других цифрах нет замкнутых областей, которые закрашиваются. В принтере красной краски осталось на покраску h замкнутых областей. Найдите минимальное неотрицательное число, напечатав которое в принтере закончится красная краска. Число не должно содержать ведущих нулей. Если в принтере отсутствует красная краска, то он не может напечатать цифру с замкнутой областью.

Входные данные
На вход подается число h (0 <= h <= 510).

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

Примеры

№	Входные данные	Выходные данные
1	15	48888888
2	70	88888888888888888888888888888888888

Задача на реализацию Конструктив Циклы

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

Экономическая грамотность#39056

Многие банки при оплате покупок их банковскими картами предлагают систему возврата части потраченных средств, называемую cashback .

Мама Алёны имеет три подобные карты с разными условиями возврата части потраченной суммы. На карту банка RR возвращается 5 рублей из каждых полных 100 рублей стоимости одной покупки. Например, 5 рублей возвращается и за покупку стоимостью 100 рублей, и 199 рублей. Банк BB возвращает 2 рубля с каждых 50 рублей покупки, и за покупку стоимостью 199 рублей он вернет уже 6 рублей. А банк ММ возвращает 3% с полной стоимости любой покупки (заметим, что при цене в целом числе рублей, 3% всегда будут составлять целое число копеек), поэтому за покупку в 199 рублей вернется 5 руб. 97 коп.

Алёна любит ходить вместе с мамой за покупками. Мама предложила Алёне определять, какую покупку какой картой оплачивать, чтобы сумма возврата была максимально возможной. Считайте, что оплата любой покупки возможна любой картой. Если какие-то две или все три карты дают лучшую сумму возврата с точностью до копеек, то Алёна выбирает ту из карт, которая ей больше нравится по оформлению. Больше всего Алёна любит карту банка MM, затем идёт карта банка BB, а меньше всего Алёне нравится карта банка RR.

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

Вводится одно целое число S ( 1 <= S <= 10 000 ) — стоимость покупки в рублях.

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

Выведите название банка RR , BB или MM в зависимости от того, картой какого банка выгоднее оплатить эту покупку. А при равенстве суммы возврата - название банка, определённого в условии задачи.

Примечание

В первом примере только банк MM вернёт часть суммы покупки. Второй пример разобран в условии задачи.

Примеры

№	Входные данные	Выходные данные
1	10	MM
2	199	BB
3	101	RR

Задачи на моделирование Условный оператор

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

Посетить все#39054

Громозека играет в одиночную игру, используя числовую прямую и N фишек. Каждая из фишек расположена в некоторой целочисленной координате. Заметьте, несколько фишек могут быть размещены в одной и той же координате.
Цель игры: посетить фишками все M координат X₁, X₂, ..., X_M, повторив следующий ход.
Ход: выберите фишку с координатой X. Поместите эту фишку в координату X+1 или X-1.
Обратите внимание, что координаты, где мы первоначально размещены фишки, уже считаются посещенными.
Найдите минимальное количество ходов, необходимое для достижения цели.

Входные данные
В первой строке программа получает на вход два целых числа: N и M (1 <= N, M <= 10⁵). Во второй строке записаны M целых чисел X₁, X₂, ..., X_M (-10⁵ <= X_i <= 10⁵). Все числа X_i различны.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 5 10 12 1 2 14	5	Цель может быть достигнута за пять ходов следующим образом, и это минимально необходимое количество ходов. Сначала поместите две фишки в координаты 1 и 10. Переместите фишку с координатой 1 на 2. Переместите фишку с координатой 10 на 11. Переместите фишку с координатами 11 на 12. Переместите фишку с координатами 12 на 13. Переместите фишку с координатами 13 на 14.
2	3 7 -10 -3 0 9 -100 2 17	19
3	100 1 -100000	0

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

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

Гимнастические ленты. Тренировочное задание - 3#39022

Для выступления гимнастки используют ленты, которые после выступления кладут на стол. Папа самой лучшей гимнастки Анны К. в ожидании награждения решил записывать координаты начала и конца лент. У вас есть файл с данной информацией. Определите в скольки точках стола получилась самая большая толщина покрытия и чему она равна. Стол имеет длину Lмм. По окончании выступления всех гимнасток, на столе оказалось N лент. Никакая лента не вылезает за границы стола. Все ленты лежат горизонтально. Ленты складываются друг на друга.

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

В первой строке файла записаны два числа - L, N (1 <= L <= 10000, 1 <= N <= 10000). В слеующих N строках записаны по 2 числа - l, r (1 <= l <= r <= L) - левые и правые концы лент относительно левого края стола.

Примеры

№	Входные данные	Выходные данные
1	39 4 3 21 3 15 2 20 3 17	4 13

Файл к заданию

ЕГЭ_информатика Сортировка подсчетом

1 300труднаяВойти и решать

Яркость гирлянды. Тренировочное задание - 2#39015

На фабрике Деда Мороза изготавливаются лампочки различного веса и яркости. Вес лампочки не превосходит 100 грамм, яркость лампочки не превосходит 10000 люменов.
Для изготовления новогодней гирлянды выбираются K самых ярких лампочек. Если яркость у двух лампочек одинаковая и они все не помещаются в гирлянду, то помещают лампочку с меньшим весом.
Известна информация о весе и яркости каждой лампочки, завезенной в мастерскую для формирования новогодней гирлянды.
Определите суммарный вес лампочек в гирлянде и среднюю яркость всей гирлянды.

Входные и выходные данные
В файле в первой строке через пробел записаны числа N - количество лампочек, завезенный в мастерскую (натуральное число, не превышающее 1000) и K – количество лампочек в гирлянде (натуральное число, не превосходящее 100). В каждой из последующих N строк через пробел записаны два числа – вес и яркость каждой лампочки.
Запишите в ответе два числа – сначала суммарный вес лампочек в гирлянде, затем среднюю яркость всей гирлянды (только целую часть).

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

9 4 50 600 60 480 45 540 30 300 15 180 70 560 30 360 91 910 40 320

Ответ: 256 652

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

1 300труднаяВойти и решать

Бонус за результат. Тренировочное задание - 1#39014

В quizzz "Сдай ЕГЭ на 100 баллов" можно набрать до 10 000 очков. По окончании игры, первые K участников, набравшие наибольшее количество баллов, получают бонус к своим очкам в виде +30% от набранных. Вам известна информация о том, сколько очков набрал каждый участник игры. Определите максимальное количество очков, на которое не распространился бонус, а также целую часть от общей суммы бонуса, полученную игроками.

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

Пример входного файла:
12 4 370 580 3000 1310 1700 2810 1660 1250 1870 1340 1400 1260

При таких исходных данных ответ должен содержать два числа – 1660 2814.

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

1 200труднаяВойти и решать

Демо-2022. Разбор задачи#38997

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

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

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

Пример

№	Входные данные	Выходные данные
1	100 4 80 30 50 40	2 50

При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера: 2 50

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

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

Замена чисел#38996

В наборе чисел N замените одно число на число из набора чисел M таким образом, чтобы сумма чисел в наборе N была как можно ближе к числу S. Выведите три числа, каждое в отдельной строке:
1 строка - число, которое заменили из набора N;
2 строка - число из набора M, которым заменили;
3 строка - полученную сумму чисел из набора N.
Гарантируется, что такую замену сделать можно. Если возможных замен несколько, то выбрать ту, в которой число из набора N меньше.

Входные данные
В первой строке вводится через пробел 3 числа: n (10<=N<=10⁵) - количество чисел в наборе N, m (10<=M<=10⁵) - количество чисел в наборе M, S (10<=S<=10⁹) S>sum(N), где sum(N) - сумма всех чисел набора N.
Во второй строке записан набор чисел N: n чисел, разделенных одним пробелом (каждое число по модулю не превышает 10⁵).
Во третьей строке записан набор чисел M: m чисел, разделенных одним пробелом (каждое число по модулю не превышает 10⁵).

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

Примеры

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

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

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

Количество чисел с суммой не больше S#38995

В файле записаны целые положительные числа. В первой строке файла записано число N - количество чисел, и натуральное число S. В следующих N строках записаны сами числа.
Укажите в ответе два числа через пробел: сначала максимальное количество чисел, которые необходимо сложить, чтобы сумма была не больше числа S, затем, значение полученной суммы.

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

1 100труднаяВойти и решать

Хранение данных и сортировка#38994

В файле записаны целые положительные числа. В первой строке файла записано число N - количество чисел. В следующих N строках записаны сами числа. В ответе укажите в столбик 10 самых больших трехзначных чисел.

Файл к заданию

Алгоритмы сортировки ЕГЭ_информатика

1 000средняяВойти и решать

Поиск подотрезка массива с максимальной суммой#38942

Дана последовательность из N целых чисел. Рассматриваются все её непрерывные подпоследовательности. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. В ответе укажите количество элементов в этой подпоследовательности.

Динамическое программирование: один параметр Префиксные суммы(минимумы, ...)

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

До Нового года - 1#38928

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

Входные данные
Входная строка содержит два целых числа N и K (\(1<=N<=1000\), \(2<=K<=1000\)).

Выходные данные
Выведите на экран ответ на задачу. Гарантируется, что верный ответ не превышает \(2^{31}-1\).

Примеры

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

Комбинаторика Циклы

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

До Нового года - 2!#38923

В каком-то другом мире сегодня 30 декабря. В саду деда Коковани посажено N деревьев. Высота i-го дерева (1 <= i <= N) равна h_i метров. Он решает выбрать из этих деревьев K деревьев и украсить их гирляндой. Чтобы декорации были красивее, высота украшенных деревьев должна быть как можно ближе друг к другу. Более конкретно, пусть высота самого высокого украшенного дерева будет h_max метров, а высота самого низкого декорированного дерева будет h_min метров. Чем меньше значение h_max-h_min, тем лучше. Определите минимально возможное значение h_max-h_min?

Входные данные
В первой строке записаны через пробел два числа N и K (2 <= N, K <= 10⁵). В следующих N строках записаны целые числа h_i (1 <= h_i <= 10⁹), по одному в строке.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 3 10 15 11 14 12	2	Если украсить первое, третье и пятое деревья, `h_max=12, h_min=10, h_max-h_min=2`.
2	5 3 5 7 5 7 7	0

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

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

Эквивалентные строки#38878

Рассмотрим строки, состоящие из первых k букв английского алфавита. Некоторые пары букв называются коммутирующими: если они стоят рядом в строке, их разрешается поменять местами.
Даны пары коммутирующих букв и две строки равной длины s и t. Требуется выяснить, можно ли получить t из s, выполнив произвольное количество операций: поменять местами две рядом стоящие коммутирующие буквы.

Входные данные
Первая строка содержит два целых числа k и n — количество используемых букв и количество пар коммутирующих букв (2 ≤ k ≤ 10, 0 ≤ n ≤ k(k − 1)/2).
Следующие n строк содержат по две буквы, не разделенные пробелом: пары коммутирующих букв. Гарантируется, что каждая пара приведена во вводе не более одного раза.
Следующие две строки содержат строки s и t, они имеют равную длину L (1 ≤ L ≤ 100 000) и состоят из первых k букв латинского алфавита.

Выходные данные
Выведите «YES», если строку t можно получить из строки s описанными операциями.
В противном случае выведите «NO».

Примеры

№	Входные данные	Выходные данные
1	3 2 ab bc abbcabc abcacbb	YES
2	3 2 ab bc abbcabc aabbbcc	NO

Алгоритмы на строках графы

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

НОД на множестве чисел#38877

Наибольшим общим делителем непустого набора натуральных чисел A называется максимальное натуральное число d, такое что оно является одновременно делителем всех чисел множества A.
Задан массив натуральных чисел [a₁, a₂, . . . , a_n] и число k. Требуется выбрать в нем подмассив из k подряд идущих элементов [a_l, a_l+1, . . . , a_l+k−1], чтобы их наибольший общий делитель был как можно больше, и вывести этот наибольший общий делитель.

Входные данные
Первая строка ввода содержит два целых числа n и k (2 ≤ n ≤ 500 000, 2 ≤ k ≤ n).
Вторая строка содержит n натуральных чисел a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10¹⁸).

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

Примеры

№	Входные данные	Выходные данные
1	10 4 2 3 4 8 12 6 12 18 4 3	6

НОД и алгоритм Евклида

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

Без неподвижных точек#38876

Перестановкой n элементов называется массив из различных натуральных n чисел, каждое из которых от 1 до n. Например, все перестановки 3 элементов: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].
Элементы перестановки пронумерованы от 1 до n, например для перестановки a = [3, 1, 2] выполнено a[1] = 3, a[2] = 1, a[3] = 2. Элемент с номером i называется неподвижной точкой, если a[i] = i. Так, в перестановке [3, 1, 2] нет неподвижный точек, а в перестановке [1, 3, 2] элемент a[1] = 1 является неподвижной точкой.
Упорядочим все перестановки лексикографически — сначала по первому элементу, потом по второму, и так далее. В начале условия все перестановки трех элементов приведены в лексикографическом порядке. Оставим только те перестановки, которые не содержат неподвижных точек. Для n = 3 останутся перестановки [2, 3, 1] и [3, 1, 2].
По заданным n и t требуется вывести первые t в лексикографическом порядке перестановок n элементов без неподвижных точек. Перестановки следует выводить в лексикографическом порядке.

Входные данные
На ввод подаются два целых числа n и t (2 ≤ n ≤ 1000, 1 ≤ t ≤ 10⁴, nt ≤ 10⁵ ). Гарантируется, что существует хотя бы t перестановок n элементов без неподвижных точек.

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

Примеры

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

Перестановки

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

Спираль#38875

Робот перемещается по клетчатой плоскости и рисует спираль. Исходно он находится в клетке (0, 0) и направлен в сторону увеличения первой координаты.
Далее он действует по следующему алгоритму: совершает d перемещений вперед, затем поворачивает налево и снова делает d перемещений вперед. После этого он поворачивает налево и умножает значение d на k. Затем робот повторяет описанный процесс. Робот останавливается, сделав суммарно ровно n перемещений.
Требуется вывести картинку, на которой отмечены клетки, на которых побывал робот.

Входные данные
На вход подаются целые числа n, d и k (1 ≤ n ≤ 1000, 1 ≤ d ≤ 100, 2 ≤ k ≤ 5).

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

Примеры

№	Входные данные	Выходные данные
1	13 2 2	5 5 ***** ... .** .... *...

Двумерные массивы Задачи на моделирование

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