По правилам безопасности максимальное неудобство в бригаде не должно превышать значения \(M\), а количество людей в бригаде может быть произвольным.
Определите максимальный размер бригады (чем больше людей в бригаде, тем легче носить брёвна!), неудобство которой не превышает \(M\).
Программа получает на вход числа \(N\) и \(M\) в первой строке (\(1\le N\le 10^5\), \(M\ge 0\)), во второй строке записано \(N\) натуральных чисел через пробел — значения роста.
Программа должна вывести одно целое число: максимальное число людей в бригаде, неудобство которой не превосходит \(M\).
Указание. Это типичная задача на метод двух указателей. Отсортируем массив и будем перебирать индекс члена бригады с наименьшим ростом. В другой переменной будем хранить индекс члена бригады с наибольшим ростом, которого можно поставить к выбранном члену бригады с наименьшим ростом. Когда индекс члена бригады с наименьшим ростом увеличивается, индекс члена бригады с наибольшим ростом также увеличивается. Решение имеет сложность сортировки + \(O(N)\).
| Ввод | Вывод |
|---|---|
6 3 |
3 |
Каждая бригада должна содержать ровно \(K\) человек, а неудобство бригады не должно превышать значения \(M\). Определите наибольшее число бригад, которое можно составить при таких условиях.
Программа получает на вход числа \(N\), \(K\) и \(M\) в первой строке (\(1\le K \le N\le 10^5\), \(M\ge 0\)), во второй строке записано \(N\) натуральных чисел через пробел — значения роста.
Программа должна вывести одно целое число: максимальное количество бригад, которое можно составить из данных людей.
| Ввод | Вывод |
|---|---|
10 3 3 |
2 |
Для того, чтобы повесить картину на стенку, нужно просверлить в стене дырку, вбить в неё дюбель и вкрутить в него саморез. Есть \(N\) сверел и \(M\) дюбелей, нужно найти среди них сверло и дюбель одинакового радиуса. Если таких нет, то нужно найти такое сверло и дюбель, чтобы разность их диаметров была как можно меньше (по модулю).
В первой строке входных данных заданы два числа \(N\) и \(M\) (\(1\le N, M\le 10^5\)). Во второй строке заданы \(N\) целых чисел — диаметры сверел. В третьей строке заданы \(M\) целых чисел — диаметры дюбелей. Диаметры заданы в неубывающем порядке, значения диаметров не превосходят \(10^9\).
Программа должна вывести одно целое число — минимальное значение модуля разности диаметров сверла и дюбеля.
| Ввод | Вывод |
|---|---|
3 2 |
2 |
3 3 |
0 |
Дано \(N\) грузов. Для их перевозки можно заказать \(M\) одинаковых грузовиков, причем на каждый грузовик можно погрузить не более 2 любых грузов. Определите минимально возможную грузоподъемность одного грузовика, при которой можно увезти все грузы на \(M\) грузовиках.
Первая строка входных данных содержит два числа \(N\) и \(M\) (\(1\le N, M\le 10^5\)). Во второй строке заданы \(N\) целых чисел — массы грузов (натуральные числа, не превосходящие \(10^9\)).
Программа должна вывести одно число — минимально возможную грузоподъемность грузовика. Если увезти данные грузы на \(M\) грузовиках невозможно, программа должна вывести число -1.
| Ввод | Вывод |
|---|---|
5 4 |
7 |
5 3 |
8 |
Дано \(N\) различных целых чисел и целое число \(Q\). Выберите среди данных чисел два числа таких, чтобы их сумма была как можно ближе к \(Q\).
Первая строка входных данных содержит числа \(N\) и \(Q\) (\(2\le N\le 10^5\), \(1\le Q\le 10^9\)). Во второй строке записано \(N\) натуральных чисел, не превосходящих \(10^9\), все числа различные.
Программа должна вывести два числа из данных.
| Ввод | Вывод |
|---|---|
5 10 |
2 8 |
3 10 |
6 5 |
Забор представляет собой отрезок прямой, левый конец которого имеет координату \(L\), правый конец — координату \(R\). На этом отрезке вкопано \(N\) столбов.
Необходимо выкопать наименьшее число столбов так, чтобы в заборе можно было сделать проход, шириной не менее, чем \(W\). После выкавывания столбов должен найтись промежуток между двумя какими-то оставшимися столбами, или между между оставшимся столбом и концом забора, или между двумя концами забора шириной не менее \(W\), не содержащий других столбов.
Первая строка содержит два целых числа \(N\) и \(W\) — количество вкопанных столбов и минимально необходимую ширину проёма для калитки соответственно. Гарантируется, что \(0\le N\le 30000\) и что \(1\le W\le 60000\).
Во второй строке даны два числа \(L\) и \(R\) — координаты левого и правого конца забора (\(-30000\le L\lt R\le 30000\)). Третья строка содержит \(N\) чисел — координаты вкопанных столбов, расположенные строго на отрезке \([L, R]\). Все координаты, включая \(L\) и \(R\) — различные целые числа.
Программа должна вывести минимальное число столбов, которые надо выкопать. Далее должны следовать номера этих столбов. Столбы нумеруются в том порядке, как они указаны во входном файле, начиная с 1.
Если решений несколько, то нужно вывести любое из них. Если решения нет, то нужно вывести одно число -1.
| Ввод | Вывод |
|---|---|
3 2 |
1 |
3 2 |
0 |
3 5 |
3 |