| Условие задачи | | |
ID 38128: Acowdemia
Темы:
Бинарный поиск по ответу
Алгоритмы сортировки
Беси опубликовала N статей (1≤N≤105). i-ая статья процитирована ci раз (0≤ci≤105).
h-индекс это наибольшее число h такое, что имеется не менее h статей, каждая из которых цитируется не менее чем h раз. Например, есть 4 статьи с количествами цитат (1,100,2,3), тогда h-индекс равен 2, а при количествах цитат (1,100,3,3) h-индекс равен 3.
Чтобы повысить свой h-индекс, Беси планирует написать K обзорных статей (0≤K≤105), каждая из которых цитирует несколько ей прошлых статей. Беси имеет право цитировать не более L статей в каждом обзоре (0≤L≤105). Конечно, никакая статья не может цитироваться более одного раза в одном обзоре (однако статья может цитироваться в нескольких обзорах).
Помогите Беси определить максимальный h-индекс, который она может достичь после написания этих обзорных статей. Беси не может цитировать обзор в любом из её обзоров.
ФОРМАТ ВВОДА
Первая строка содержит N, K, L.
Вторая строка содержит N разделённых пробелом целых чисел c1,…,cN.
ФОРМАТ ВЫВОДА
Максимальный h-индекс.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
4 4 1
1 100 1 1 |
3 |
В этом примере Беси может написать 4 обзорные статьи, в каждой из которых можно процитировать не более 1 статьи. Если процитировать первую и третью статьи по 2 раза, её h-индекс станет 3. |
| 2 |
4 1 4
1 100 1 1 |
2 |
В этом втором примере Беси может написать не более одной статьи. Если Беси процитирует любую из её 1,2 или 4 статью хоть раз, её h-индекс станет 2. |
| |
![]()
|
ID 38335: Рассадка участников
Темы:
Алгоритмы сортировки
Задачи на моделирование
На олимпиаду по информатике пришло N участников. Известно, в каких школах учатся участники олимпиады. В компьютерном классе имеется N компьютеров, стоящих в линию вдоль стены. Вам необходимо рассадить участников олимпиады так, чтобы никакие два участника из одной школы не сидели рядом.
Входные данные
Программа получает на вход целое положительное число участников олимпиады N1000. Далее в N строках записаны номера школ, в которых учатся участники олимпиады. Номера школ — целые числа от 1 до 3000.
Выходные данные
Программа должна вывести N чисел — номера школ участников олимпиады в том порядке, в котором их необходимо рассадить в компьютерном классе. Выведенная последовательность номеров школ должна быть перестановкой данных номеров школ. В выведенном ответе не должно быть двух одинаковых номеров школ, идущих подряд.
Если задача не имеет решения, необходимо вывести одно число 0.
Числа можно выводить как в отдельных строках, так и в одной строке через пробел. Если есть несколько вариантов рассадки, то необходимо вывести любой из них (но только один).
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
1005
1005
5
2005 |
1005 5 1005 2005 |
| 2 |
4
1005
1005
2005
1005 |
0 |
| |
![]()
|
ID 38473: Взвешивание камней
Темы:
Алгоритмы сортировки
Дерево отрезков, RSQ, RMQ
Жадный алгоритм
Джек нашел N камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий ≤ 2 и так далее, самый тяжелый получил номер N.
У Джека есть чашечные весы и он решил положить все камни на них в каком-то порядке. Известен порядок, в котором он будет класть камни, и какой камень на какую чашу попадет.
Ваша задача — определить состояние весов после добавления каждого камня. Точные массы камней не известны — даются только их номера.
Входные данные
Первая строка содержит целое число N (1 N ≤ 100000).
Каждая из следующих N строк содержит по два целых числа: R (1 ≤ R ≤ N) и S (1 ≤ S ≤ 2). R - номер камня, который будет положен на чашу S. Все R будут различны.
Выходные данные
Выведите N строк - по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
1 2
3 1
2 1
4 2
5 1 |
<
>
>
?
>
|
| |
![]()
|
ID 38481: Ироха любит строки
Темы:
Строки
Алгоритмы сортировки
У Ирохи есть последовательность из N строк s1, s2, .., sN. Каждая строка длиной L. Ироха хочет объединить все строки, чтобы получить очень длинную строку. Среди всех строк, которые она может получить таким образом, найдите лексикографически наименьшую.
Будем считать, что строка s = s1s2...sn лексикографически меньше строки t = t1t2...tm, если выполняется одно из следующих условий:
- существует индекс i (\(1<=i<=min(n,m)\)), такой что \(s_j =t_j \), для всех индексов j (\(1<=j<=i\)), и \(s_i <t_i \);
- \(s_i=t_j\) для всех i (\(1<=i<=min(n,m)\)), и \(n<m\).
Входные данные
В первой строке задаются числа N и L. Далее идут строки s1, s2, .., sN, каждая в отдельной строке.
Выходные данные
Выведите лексикографически наименьшую строку, которую может создать Ироха.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 3
dxx
axx
cxx |
axxcxxdxx |
| |
![]()
|
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 38923: До Нового года - 2!
Темы:
Алгоритмы сортировки
В каком-то другом мире сегодня 30 декабря. В саду деда Коковани посажено N деревьев. Высота i-го дерева (1 <= i <= N) равна hi метров. Он решает выбрать из этих деревьев K деревьев и украсить их гирляндой. Чтобы декорации были красивее, высота украшенных деревьев должна быть как можно ближе друг к другу. Более конкретно, пусть высота самого высокого украшенного дерева будет hmax метров, а высота самого низкого декорированного дерева будет hmin метров. Чем меньше значение hmax-hmin, тем лучше. Определите минимально возможное значение hmax-hmin?
Входные данные
В первой строке записаны через пробел два числа N и K (2 <= N, K <= 105). В следующих N строках записаны целые числа hi (1 <= hi <= 109), по одному в строке.
Выходные данные
Выведите на экран ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
5 3
10
15
11
14
12 |
2 |
Если украсить первое, третье и пятое деревья, hmax=12, hmin=10, hmax-hmin=2. |
| 2 |
5 3
5
7
5
7
7 |
0 |
|
| |
![]()
|
ID 38994: Хранение данных и сортировка
Темы:
ЕГЭ
Алгоритмы сортировки
В файле записаны целые положительные числа. В первой строке файла записано число N - количество чисел. В следующих N строках записаны сами числа. В ответе укажите в столбик 10 самых больших трехзначных чисел.
| |
![]()
|