Дано \(n\) чисел. Для каждого числа из этого массива укажите, сколько среди данных чисел меньших его.
Программа получает на вход число \(n\). В следующей строке записаны \(n\) чисел \(a_i\), \(1\le a_i\le 10^9\).
Программа должна вывести \(n\) чисел. \(i\)-е число должно быть равно количеству чисел среди данных, которые меньше \(a_i\).
| Ввод | Вывод |
|---|---|
5 |
0 2 4 2 0 |
Дано \(n\) чисел. Для каждого числа из этого массива укажите, сколько среди данных чисел меньше или равны его.
Программа получает на вход число \(n\). В следующей строке записаны \(n\) чисел \(a_i\), \(1\le a_i\le 10^9\).
Программа должна вывести \(n\) чисел. \(i\)-е число должно быть равно количеству чисел среди данных, которые меньше или равны \(a_i\).
| Ввод | Вывод |
|---|---|
5 |
2 4 5 4 2 |
В собрании сочинений Дарьи Донцовой \(N\) томов. В \(i\)-м томе содержится \(a_i\) романов в порядке их написания, то есть в первом томе содержатся романы с номерами от 1 до \(a_1\), во втором томе — романы с номерами от \(a_1+1\) до \(a_1+a_2\) и т.д.
Научитесь быстро определять, в каком томе находится роман с данным номером.
Первая строка входных данных содержит число \(N\), \(1\le N\le 10^5\) — количество томов в собрании сочинений. Следующая строка содержит \(N\) целых положительных чисел \(a_i\) — количества романов в каждом томе.
Третья строка содержит количество запросов \(M\), \(1\le M\le 10^5\). Следующая строка содержит \(M\) целых положительных чисел — запросы с номерами романов.
Для каждого запроса выведите номер тома, в котором содержится роман с таким номером. Если Дарья Донцова не написала столько романов, то выведите число 0.
| Ввод | Вывод |
|---|---|
4 |
2 3 0 4 |
Напомним, что пара из мальчика и девочки будет красиво смотреться, если величины их ростов отличаются не более чем на 1. Для каждого мальчика определите, с каким количеством девочек он сможет составить красивую пару. Сделайте это и для каждой девочки.
Программа получает на вход число \(n\), \(1\le n \le 10^5\). В следующей строке записаны через пробел \(n\) положительных чисел \(a_i\), не превосходящих \(10^9\), — значения роста мальчиков. Затем дано число \(m\), \(1\le m \le 10^5\). В следующей строке записаны через пробел \(m\) положительных чисел \(b_i\), не превосходящих \(10^9\), — значения роста девочек.
Программа должна вывести \(n+m\) чисел. Сначала для каждого мальчика выведите сколько девочек образует с ним красивую пару. Затем для каждой девочки выведите, сколько мальчиков образует с ней красивую пару.
| Ввод | Вывод |
|---|---|
3 |
0 1 2 |
Дано \(n\) палочек. Определите количество способов выбрать три палочки так, чтобы из них можно было составить невырожденный треугольник.
Программа получает на вход число \(n\le5000\) — количество палочек. Следующая строка содержит \(n\) чисел — длины палочек.
Программа должна вывести одно число — количество троек палочек, образующих треугольник.
| Ввод | Вывод |
|---|---|
4 |
3 |
В примере из условия можно составить такие тройки: (2, 3, 2), (2, 3, 4), (3, 2, 4).
Указание. Отсортируем палочки по возрастанию. Двумя вложенными циклами будем перебирать значения двух меньших палочек, которые будем использовать в треугольнике. Определим максимально возможный размер третьей палочки. Двоичным поиском найдём индекс максимального элемента, который может быть третьей палочкой, тем самым определим, сколькими способами можно подобрать третью палочку к двум данным. Сложность решения будет \(O(n^2\log n)\). Также эту задачу можно решить при помощи двух указателей за \(O(n^2)\).
Дарья Донцова написала \(N\) романов. В \(i\)-м романе \(a_i\) страниц. Необходимо издать собрание сочинений Дарьи Донцовой в \(K\) томах так, чтобы число страниц в самом большом томе было минимальным. Романы должны идти в порядке номеров, каждый роман должен целиком быть в одном томе.
Первая строка входных данных содержит числа \(N\) и \(K\), \(1\le K\le N\le 10^5\). Вторая строка содержит \(N\) чисел \(a_i\), \(1\le a_i\le 10^4\).
Программа должна вывести одно число — минимально возможное количество страниц в самом большом томе собрания сочинений,
| Ввод | Вывод |
|---|---|
3 2 |
3 |
4 3 |
2 |
Поликарп очень любит гамбургеры, особенно приготовленные собственноручно. Поликарп считает, что существует только три достойных ингредиента для приготовления гамбургера: хлеб, колбаса и сыр. Рецепт своего знаменитого «гамбургера от Поликарпа» он записывает в виде строки из букв «B» (хлеб), «S» (колбаса) и «C» (сыр). Например, рецепт «ВSCBS» обозначает гамбургер в котором снизу вверх идут: хлеб, колбаса, сыр, хлеб и снова колбаса.
На кухне у Поликарпа в наличии \(n_p\) кусочков хлеба, \(n_s\) кусочков колбасы и \(n_c\) кусочков сыра. Кроме того, в магазине неподалеку есть в продаже все три ингредиента по цене: \(p_b\) рублей за кусок хлеба, \(p_s\) — за кусок колбасы и \(p_c\) — за кусочек сыра.
У Поликарпа есть \(r\) рублей, которые он готов потратить в магазине. Какое наибольшее количество гамбургеров он сможет приготовить?
В первой строке входных данных содержится непустая строка, описывающая рецепт «гамбургера от Поликарпа». Длина строки не превосходит 100, строка содержит только буквы «B», «S» и «C».
Вторая строка содержит три целых числа \(n_b\), \(n_s\), \(n_c\) (\(1 \le n_b, n_s, n_c \le 100\)) — количество кусочков хлеба, колбасы и сыра на кухне Поликарпа. Третья строка содержит три целых числа \(p_b\), \(p_s\), \(p_c\) (\(1 \le p_b, p_s, p_c \le 100\)) — цена одного кусочка хлеба, колбасы и сыра в магазине. Наконец, четвертая строка содержит целое число \(r\) (\(1 \le r \le 10^{12}\)) — количество рублей у Поликарпа.
Выведите наибольшее количество гамбургеров, которое Поликарп может приготовить.
| Ввод | Вывод |
|---|---|
BBBSSC |
2 |
BBC |
7 |
BSC |
200000000001 |
Дизайнеры разработали проект новогоднего украшения центрального проспекта города. На \(i\)-м доме должно висеть \(a_i\) гирлянд, при этом число гирлянд на следующем доме \(a_{i+1}\) должно выражаться (как решили дизайнеры) конкретной формулой, которая может быть равна либо \(a_{i} \cdot c_{i}\), либо \(a_{i}+c_{i}\), либо \(a_{i}-с_{i}\), то есть равно количеству гирлянд на предыдущем доме либо умноженному на некоторую константу, либо увеличенному на константу, либо уменьшенному на константу. При этом операция и константа — разные для разных домов.
Единственное, что может сделать мэр города — это выбрать количество гирлянд на первом доме. Он хочет сделать это так, чтобы стоимость украшения города была минимальной. При этом на каждом доме должна быть хотя бы одна гирлянда. Помогите ему с этим.
Первая строка входных данных содержит число домов \(n\), \(1\le n\le 1000\). Следующие \(n-1\) строк содержат по два целых положительных числа \(z_i\) и \(с_{i}\). Значение \(z_i\) обозначает операцию и может быть 1, 2 или 3, \(1\le c_i\le 10^6\). Если \(z_i=1\), то \(a_{i+1}=a_{i} \cdot c_{i}\). Если \(z_i=2\), то \(a_{i+1}=a_{i}+c_{i}\). Если \(z_i=3\), то \(a_{i+1}=a_{i}- c_{i}\).
Программа должна вывести минимально возможное значение \(a_1\).
| Ввод | Вывод |
|---|---|
2 |
2 |
3 |
1 |
4 |
2 |
Вам даны целые положительные числа \(A\) и \(n\). Найдите такое наибольшее целое число \(x\) такое, что \(x^n\le A\).
Первая строка входных данных содержит число \(A\). Вторая строка входных данных содержит число \(n\). Числа положительные и не превосходят \(10^{100}\) каждое.
| Ввод | Вывод |
|---|---|
100 |
4 |
Вам дано число \(s\) и нечётное число \(n\). Необходимо получить массив из различных положительных чисел такой, чтобы сумма чисел была равна \(s\), а медиана чисел в этом массиве была бы как можно больше. Определите значение этой медианы.
Первая строка входных данных содержит число \(s\). Вторая строка входных данных содержит нечётное число \(n\). Числа положительные и не превосходят \(10^{100}\) каждое.
Программа должна вывести одно число — максимально возможное значение медианы числового массива из \(n\) различных целых положительных чисел, сумма которых равна \(s\). Если такого массива не существует, программа должна вывести \(-1\).
| Ввод | Вывод |
|---|---|
10 |
4 |
5 |
-1 |
Дано кубическое уравнение \(ax^3 + bx^2 + cx + d = 0 \), где \(a \ne 0\). Известно, что у этого уравнения ровно один корень. Найдите его.
Программа получает на вход четыре целых числа \(a\), \(b\), \(c\), \(d\), не превосходящих по модулю 1000.
Выведите единственный корень уравнения, ваш ответ должен отличаться от
правильного не более, чем на \(10^{-6}\). Просто поставьте
cout.precision(20).
| Ввод | Вывод |
|---|---|
1 -3 3 -1 |
0.999999598818135 |
-1 -6 -12 -7 |
-0.999999999990564 |
Дано кубическое уравнение \(ax^3 + bx^2 + cx + d = 0 \). Известно, что все корни этого уравнения не превосходят по модулю 1000. Известно, что два любых корня отличаются не более, чем на \(10^{-6}\).
Программа получает на вход четыре действительных числа \(a\), \(b\), \(c\), \(d\). Любые из этих чисел, но не все одновременно, могут быть равны 0.
Программа должна вывести от 0 до 3 действительных чисел: корни данного уравнения в порядке возрастания. Кратные корни должны быть выведены только один раз. Значения корней необходимо выводить с точностью не менее 6 знаков после точки.
| Ввод | Вывод |
|---|---|
0 0 1000 -1 |
0.001 |