| Условие задачи | | |
ID 38123: Acowdemia I
Темы:
Использование сортировки
Беси учится на PhD в компьютерных науках. Она опубликовала N статей (1≤N≤105) и её i-ую статью цитировали ci раз (0≤ci≤105).
Беси слышала что академические успехи измеряются h-индексом. h-индекс - это наибольшее число h такое, что ученый имеет не менее h статей, каждая из которых цитируется не менее h раз. Например, учёный у которого четрые статьи с количествами цитат (1,100,2,3) имеет h-индекс равный 2, а ученый с количествами цитат (1,100,3,3) имеет h-индекс равный 3.
Чтобы повысить свой h-индекс Беси планирует написать обзорную статью, цитирующую некоторые из её прошлых статей. В связи с ограничением на количество страниц, она может включить не более L цитат в свой обзор (0≤L≤105), т конечно она может процитировать каждую из своих статей не более одного раза.
Помогите Беси определить максимальный h-индекс, который она может достичь написанием своей обзорной статьи.
Заметим, что научный руководитель должен был предупредить Беси, что написание статьи исключительно с целью увеличения своего h-индекса сомнительно с этической точки зрения.
ФОРМАТ ВВОДА
Первая строка ввода содержит N и L.
Вторая строка ввода содержит N разделённых одиночными пробелами целых чисел c1,…,cN.
ФОРМАТ ВЫВОДА
Максимальный h-индекс, который Беси может получить написанием обзорной статьи.
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
4 0
1 100 2 3 |
2 |
Беси не может цитировать свои статьи. Как указано ранее её h-индекс для (1,100,2,3) равен 2. |
| 2 |
4 1
1 100 2 3 |
3 |
Если Беси процитирует третью статью, её количества цитирований станут (1,100,3,3). Как отмечено ранее, h в этом случае равен 3.
|
| |
![]()
|
ID 38283: Маша и матрёшки
Темы:
Использование сортировки
Маше на день рождения подарили набор матрёшек!
Теперь Маша сидит и вкладывает их одна в другую. Она заметила, что матрёшки отличаются по размеру, и одна помещается внутри другой, только если ее размеры строго меньше. Так, если есть две матрёшки i и j , а их размеры ai и aj соответственно, то матрёшка i вкладывается внутрь матрёшки j тогда и только тогда, когда ai < aj . Разумеется, непосредственно внутрь матрёшки можно вложить только одну другую матрёшку, иначе получится неаккуратно, а Маша — очень аккуратная девочка.
Маше особенно нравится, если она может, вкладывая матрёшки друг в друга, добиться того, что все они оказываются внутри одной самой большой матрёшки. Но, к сожалению, это не всегда возможно. Поэтому Маша решила убрать часть матрёшек в шкаф, оставив такой набор, чтобы их все можно было вложить друг в друга. Помогите Маше понять, какое максимальное количество матрёшек может быть в таком наборе.
Входные данные
В первой строке находится число n — количество матрёшек, подаренных Маше ( 1 ≤ n ≤ 1000 ). В следующей строке через пробел находятся n чисел — размеры матрёшек. Число ai , стоящее на месте i , задает размер матрёшки с номером i ( 1 ≤ ai ≤ 10 000 ).
Выходные данные
Выведите одно число — максимальное количество матрёшек, которые можно вложить друг в друга.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
2 10 2 |
2 |
| 2 |
6
2 1 2 1 3 4 |
4 |
| 3 |
4
3 1 4 2 |
4 |
| |
![]()
|
ID 38298: Нужно больше конфет!
Темы:
Одномерные массивы
Использование сортировки
У Карлсона дома есть набор из n банок с конфетами. Банки пронумерованы от 1 до n , в i -й из них лежит a i конфет. Карлсон считает набор банок симпатичным , если в этом наборе нет трех банок с разным числом конфет.
У Карлсона есть неограниченный запас конфет в карманах, поэтому он может добавить в любую банку произвольное число конфет. Помогите ему определить, какое минимальное общее число конфет ему придется добавить, чтобы набор банок с конфетами стал симпатичным.
Входные данные
Первая строка входных данных содержит натуральное число n ( 1 ≤ n ≤ 105 ) — количество банок в наборе Карлсона.
Вторая строка входных данных содержит n целых чисел a i ( 0 ≤ ai ≤ 109 ) — число конфет в банках. Соседние числа отделены друг от друга одним пробелом.
Выходные данные
Выведите одно число — минимальное общее количество конфет, которое придется добавить, чтобы Карлсон считал набор банок симпатичным.
Примечание
В первом тесте из примера Карлсон может добавить в первую банку две конфеты, а во вторую банку — одну конфету. Тогда в первой и четвертой банках будет лежать по 7 конфет, а во второй и третьей — по 2 конфеты.
Во втором тесте из примера набор банок исходно является симпатичным, добавлять конфеты не требуется.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
5 1 2 7 |
3 |
| 2 |
3
1 1 1 |
0 |
| |
![]()
|
ID 38312: Минимальное число
Темы:
Использование сортировки
Дано натуральное четырехзначное число. Найдите минимальное натуральное четырехзначное число, состоящее из тех же цифр, что и заданное. Заметим, что четырехзначные числа не могут начинаться с нуля.
Входные данные
Вводится натуральное четырехзначное число.
Выходные данные
Выведите минимальное натуральное четырехзначное число, состоящее из тех же цифр.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1513 |
1135 |
| |
![]()
|
ID 38689: Сортировка точек
Темы:
Структуры
Использование сортировки
Элементарная геометрия
Выведите все исходные точки в порядке возрастания их расстояний от начала координат.
Создайте структуру Point и сохраните исходные данные в массиве структур Point.
Входные данные
Программа получает на вход набор точек на плоскости. Сначала задано количество точек n, затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Величина n не превосходит 100, все исходные координаты – целые числа, не превосходящие 103.
Выходные данные
Необходимо вывести все исходные точки в порядке возрастания их расстояний от начала координат. Программа выводит только координаты точек, их количество выводить не надо.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2
1 2
2 3 |
1 2
2 3 |
| |
![]()
|
ID 38715: Печаль Громозеки
Темы:
Одномерные массивы
Использование сортировки
Алгоритмы сортировки
Громозека имеет последовательность целых чисел A длины N. Он свободно выбирает целое число b. Здесь ему станет грустно, если Ai и b+i находятся далеко друг от друга. Точнее, печаль Громозеки рассчитывается следующим образом:
\(abs(A_1-(b+1))+abs(A_2-(b+2))+...+abs(A_N-(b+N))\).
Здесь \(abs(x) \)- это функция, которая возвращает абсолютное значение x. Найдите минимально возможную печаль Громозеки.
Входные данные
В первой строке записано целое число N (\(1<=N<=2 \cdot 10^5\)). Во второй строке записано N целых чисел Ai (\(1<=A_i<=10^9\)).
Выходные данные
Выведите на экран минимально возможную печаль Громозеки.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
5
2 2 3 5 5 |
2 |
Если мы выберем b = 0, печаль Громозеки будет \( abs (2- (0 + 1)) + abs (2-(0 + 2)) + abs (3-(0 + 3)) + abs (5- (0 + 4)) + abs(5-(0 + 5)) = 2\).
Любой другой выбор b не делает печаль Громозеки меньше 2, поэтому ответ - 2. |
| 2 |
9
1 2 3 4 5 6 7 8 9 |
0 |
|
| 3 |
6
6 5 4 3 2 1 |
18 |
|
| 4 |
7
1 1 1 1 2 3 4 |
6 |
|
| |
![]()
|
ID 38848: Число
Темы:
Использование сортировки
Алгоритмы на строках
Вася написал на длинной полоске бумаги большое число и решил похвастаться своему старшему брату Пете этим достижением. Но только он вышел из комнаты, чтобы позвать брата, как его сестра Катя вбежала в комнату и разрезала полоску бумаги на несколько частей. В результате на каждой части оказалось одна или несколько идущих подряд цифр.
Теперь Вася не может вспомнить, какое именно число он написал. Только помнит, что оно было очень большое. Чтобы утешить младшего брата, Петя решил выяснить, какое максимальное число могло быть написано на полоске бумаги перед разрезанием. Помогите ему!
Входные данные
Входные данные состоят из одной или более строк, каждая из которых содержит последовательность цифр. Количество строк не превышает 100, каждая строка содержит от 1 до 100 цифр. Гарантируется, что хотя бы в одной строке первая цифра отлична от нуля.
Выходные данные
Выведите одну строку – максимальное число, которое могло быть написано на полоске перед разрезанием.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2
20
004
66 |
66220004 |
| 2 |
3 |
3 |
| |
![]()
|
ID 38995: Количество чисел с суммой не больше S
Темы:
ЕГЭ
Использование сортировки
В файле записаны целые положительные числа. В первой строке файла записано число N - количество чисел, и натуральное число S. В следующих N строках записаны сами числа.
Укажите в ответе два числа через пробел: сначала максимальное количество чисел, которые необходимо сложить, чтобы сумма была не больше числа S, затем, значение полученной суммы.
| |
![]()
|
ID 38996: Замена чисел
Темы:
Использование сортировки
ЕГЭ
В наборе чисел N замените одно число на число из набора чисел M таким образом, чтобы сумма чисел в наборе N была как можно ближи к числу S. Выведите три числа, каждое в отдельной строке:
1 строка - число, которое заменили из набора N;
2 строка - число из набора M, которым заменили;
3 строка - полученную сумму чисел набора N.
Входные данные
В первой строке вводится через пробел 3 числа: N (10<=N<=105), M (10<=M<=105), S (10<=S<=109).
Во второй строке записан набор чисел N: N чисел, разделенных одним пробелом (каждое число по модулю не превышает 105).
Во третьей строке записан набор чисел M: M чисел, разделенных одним пробелом (каждое число по модулю не превышает 105).
Выходные данные
Выведите на экран ответ на задачу, как указано в условии.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 2 10
2 4
1 3 |
2
3
7 |
| |
![]()
|