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

Гармоничная последовательность lite - 1#39386

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел \(a_1, a_2, ..., a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Например, последовательность [1,2,1,–1] является гармоничной, поскольку 2=1+1, и 1=2+(–1) .

Рассмотрим последовательности равной длины: \(A=[a_1,a_2, ... a_n]\) и \(B=[b_1,b_2, ... b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\) . Например, \(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2|++|1–0|+|–1–0|=0+0+1+1=2 \)

В конце лекции профессор написал на доске последовательность из n целых чисел \(B=[b_1,b_2, ... b_n]\)и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A=[a_1,a_2, ... a_n]\), такую, что \(d(A, B)\) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A,B)\) .

Требуется написать программу, которая по заданной последовательности B определяет, на каком минимальном расстоянии от последовательности B найдется гармоничная последовательность A.

Входные данные
Первая строка содержит целое число n – количество элементов в последовательности ( \(3 \le n \le 100\)).
Вторая строка содержит n целых чисел \(b_1, b_2, …, b_n (–100 \le b_i \le 100 )\) .

Выходные данные
Выведите одно целое число: минимальное возможное расстояние от исходной до гармоничной последовательности.

Примеры

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

Перебор

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

Гармоничная последовательность#39381

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел \(a_1, a_2, ..., a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Например, последовательность [1,2,1,–1] является гармоничной, поскольку 2=1+1, и 1=2+(–1) .

Рассмотрим последовательности равной длины: \(A=[a_1,a_2, ... a_n]\) и \(B=[b_1,b_2, ... b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\) . Например, \(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2|++|1–0|+|–1–0|=0+0+1+1=2 \)

В конце лекции профессор написал на доске последовательность из n целых чисел \(B=[b_1,b_2, ... b_n]\)и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A=[a_1,a_2, ... a_n]\), такую, что \(d(A, B)\) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A,B)\) .

Требуется написать программу, которая по заданной последовательности B определяет, на каком минимальном расстоянии от последовательности B найдется гармоничная последовательность A.

Входные данные
Первая строка входного файла содержит целое число n – количество элементов в последовательности ( \(3 \le n \le 300 000\)).

Вторая строка содержит n целых чисел \(b_1, b_2, …, b_n (–10^9 \le b_i \le 10^9 )\) .

Выходные данные
Выходной файл должна содержать одно целое число: минимальное возможное расстояние от последовательности во входном файле до гармоничной последовательности.

Примеры

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

Бинарный поиск Префиксные суммы(минимумы, ...)

✓ 3✗ 5—Войти и решать

Социальное дистанцирование#39380

Болеющие коровы решили помочь Фермеру Джону.
Для того, чтобы ограничить передачу болезни, N (2 ≤ N ≤ 10⁵) коров ФД решили попрактиковаться в "социальном дистанцировании" и "распределились" по ферме. Ферма представлена в виде прямой линии, с M взаимно не имеющими общих точек интервалами (1 ≤ M ≤ 10⁵), на которых растёт трава. Коровы хотят расставиться в точках с различными координатами, каждая точка покрыта травой, так, чтобы максимизировать значение D. Где D представляет расстояние между ближайшей парой коров. Помогите коровам определить наибольшее значение D.

Входные данные
Первая строка ввода содержит N и M. Каждая из следующих M строк описывает интервал двумя целыми числами a и b, где 0 ≤ a ≤ b ≤10¹⁸. Никакие два интервала не перекрываются и не касаются своими конечными точками. Корова, стоящая на конечной точке интервала считается стоящей на траве.
Выходные данные
Выведите наибольшее возможное значение D такое, что все пары коров не менее чем на D единиц друг от друга. Гарантируется, что существует решение с D>0.

Примеры

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

Бинарный поиск по ответу

✓ 6✗ 871 200средняяВойти и решать

Частица Му#39377

Углубившись на карантине в изучение физики, коровы открыли "му-частицы"
В настоящий момент они проводят эксперимент с N "му-частицами" (1 ≤N ≤ 10⁵). Частица i имеет "спин", описываемый двумя целыми числами x_i и y_i в диапазоне −10⁹…10⁹ включительно. Иногда две "му-частицы" взаимодействуют. Это может случиться только с такими частицами со спинами (x_i,y_i) и (x_j,y_j) у которых x_i≤x_j и y_i≤y_j. При этих условиях ровно одна из этих частиц исчезает (а с другой ничего не случится). В каждый момент времени может случиться не более одного взаимодействия.

Коровы хотят узнать минимальное количество "му-частиц", которые могут остаться после некоторой произвольной последовательности взаимодействий.

Входные данные
Первая строка содержит одно целое число N, начальное число "му-частиц". Каждая из последующих N строк содержит два разделённых пробелом целых числа, определяющих спин этой частицы. Все спины различны.
Выходные данные
Одно целое число, минимальное количество "му-частиц", которые могут остаться после некоторой произвольной последовательности взаимодействий.

Примеры

№	Входные данные	Выходные данные	Примечание
1	4 1 0 0 1 -1 0 0 -1	1	Одна из возможных последовательностей взаимодействий: Частицы 1 и 4 взаимодействуют, частица 1 исчезает. Частицы 2 и 4 взаимодействуют, частица 4 исчезает. Частицы 2 и 3 взаимодействуют, частица 3 исчезает. Только частица 2 остаётся.
2	3 0 0 1 1 -1 3	2	Частица 3 не может взаимодействовать ни с одной из других частиц, поэтому она должна остаться. Одна из частиц 1 и 2 тоже должна остаться.

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

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

Бельвита и пифагоровы тройки#39366

Сегодня Бельвита узнала про пифагоровы тройки. Если вы вдруг не знали, то это тройка целых чисел (a, b, c) таких, что можно образовать прямоугольный треугольник с длинами первого катета, второго катета и гипотенузы, равными a, b и c соответственно. Более формально, должно выполняться, что a² + b² = c².

Вечером она решила поискать существующие пифагоровы тройки, но забыла формулу. В итоге вместо правильного критерия она использовала следующий: c = a² - b.
Вскоре Бельвита опознала ошибку, однако по ее критерию нашлись такие тройки чисел, что они действительно являлись пифагоровыми.
Это заинтересовало Бельвиту и она решила посчитать количество троек целых чисел (a, b, c) таких, что 1 <= a, b, c <= n и они подходят и под настоящую формулу пифагоровых троек, и под ошибочную.
Посчитайте и вы.

Входные данные
Первая строка содержит одно целое число n (1 <= n <= 10⁹).

Выходные данные
Выведите одно число - количество троек целых чисел (a, b, c) таких, что они подходят под оба критерия.

Примеры

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

Перебор

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

Бельвита и вывеска для пекарни#39365

Завтра Бельвита открывает свою пекарню, однако она до сих пор не подготовила вывеску для своего заведения.

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

Входные данные
Первая строка содержит две строчные латинские буквы - строка s, которую Бельвита хочет видеть в названии пекарни. Вторая строка содержит одно целое число n (1 <= n <= 100) - количество наборов табличек в чулане. Следующие n строк содержат по две строчные латинские буквы каждая, описывающие надписи на табличках в наборах.

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	`ya 4 ah oy to ha`	`YES`	Можно использовать третий, второй и первый набор, составив слово "tooyah", в котором есть подстрока "ya".
2	`hp 2 ht tp`	`NO`	Получить слово с подстрокой "hp" никак нельзя.
3	`ah 1 ha`	`YES`	Можно использовать две из трех табличек первого набора, составив слово "haha", где есть подстрока "ah".

Перебор

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

Количество четных цифр#39362

Среди чисел от 1 до N определите сколько чисел с максимальным количеством четных цифр в системе счисления с основанием r. Четными цифрами в любой системе счисления будем считать цифры 0, 2, 4, 6, 8.

Входные данные
Программа получает на вход 2 числа: N (1< N <= 10⁵) и r (2 <= r <= 9).

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

Примеры

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

Вложенные циклы Разные системы счисления

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

Гошина последовательность#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средняяВойти и решать

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

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

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

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

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

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

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

Ответ: 5 25

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

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

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

Шоколад полезный#39245

Услышав, что шоколад полезен для мозга и нервной системы, ученик Василий решает закупить шоколад на весь учебный год. Василий решил закупить шоколада на R рублей. Он обошел в городе все N магазинов, которые продают различный шоколад. Василий сохранил в файл информацию о том, что в i-м магазине он может купить не более B_iплиток шоколада по A_i рублей каждая.
Запасливый ученик хочет потратить как можно больше своих денег (лучше даже сразу все) и купить на них как можно больше шоколада. Помогите Василию понять, сколько плиток шоколада он сможет купить на свои деньги и сколько будет стоить самая дорогая плитка, которую он сможет купить.

Входные данные
Первая строка в файле содержит два числа: N и R. В следующих N строках записана пара чисел: A_i и В_i.

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

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

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

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

Гимнастические ленты#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средняяВойти и решать