e-olymp 682. Сумма на отрезке

Задача

Задан набор чисел $a_{1}, …, a_{n}$. Для заданных индексов $l$ и $r$ найдите $$S_{l,r}=a_{l}+a_{l+1}+..+a_{r}$$

Входные данные

В первой строке записано количество чисел $n$ $\left(1 \leq n \leq 10^{6}\right)$. Во второй строке записаны числа $a_{i}$ $\left(1 \leq a_{i} \leq 1000\right)$, разделенные пробелом. На третьей строке записано число $m$ $\left(1 \leq m \leq 10^{6}\right)$ — количество запросов. Далее на отдельных строках записаны сами запросы $l_{i}$ и $r_{i}$ $\left(1 \leq l_{i} \leq r_{i} \leq n\right)$.

Выходные данные

Выведите в отдельных строках $m$ чисел $S_{l_i,r_i}$.

Тесты

# Входные данные Выходные данные
1 5
1 2 3 4 5
5
1 5
2 3
3 4
2 5
1 4
15
5
7
14
10
2 10
10 10 10 10 10 10 10 10 10 10
5
1 3
3 5
5 7
7 9
3 7
30
30
30
30
50
3 10
57 42 24 73 98 71 65 76 12 33
7
1 2
4 5
8 10
1 10
7 10
2 5
3 8
99
171
121
551
186
237
407
4 3
10 15 20
2
1 2
1 3
25
45
5 7
299 38924 2388 4399 7549 79475 57947
10
1 3
2 3
3 3
4 7
6 7
3 5
5 5
6 6
1 6
1 7
41611
41312
2388
149370
137422
14336
7549
79475
133034
190981

Решение

Сначала читаем с клавиатуры набор $n$ чисел и добавляем их в массив $a\left[n\right]$. Далее создаем массив $summ$ из $n+1$ элементов, $i$-ый элемент которого равен сумме всех элементов $a$ до $i-1$ включительно. Затем $m$ раз считываем $l$ и $r$ с клавиатуры, и отнимаем от $summ\left[r\right]$ «хвост» в виде суммы элементов до $l-1$ элемента.

Условие задачи можно найти на e-olymp
Код решения — ideone

e-olymp 913. Используй подпрограмму

Задача

Вычислить сумму и произведение $n$ пар заданных вещественных чисел, воспользовавшись подпрограммой $SumDob$ для вычисления суммы и произведения двух вещественных чисел.

Входные данные

В первой строке задано натуральное число $n$ — количество пар чисел. В последующих $n$ строках через пробел задано по $2$ вещественных числа. Все входные данные по модулю не превышают $100$.

Выходные данные

В $n$ строках вывести через пробел по два числа: сначала сумму, а потом произведение очередной пары чисел. Результат выводить с точностью $4$ знака после десятичной точки.

Тесты

# Входные данные Выходные данные
1 2
6 7.5
2.1 2.0
13.5000 45.0000
4.1000 4.2000
2 4
2 5
3 5
4 5
5 5
7.0000 10.0000
8.0000 15.0000
9.0000 20.0000
10.0000 25.0000
3 2
100 100
56 65
200.0000 10000.0000
121.0000 3640.0000
4 6
10 10
20 20
40 40
50 50
70 70
80 80
20.0000 100.0000
40.0000 400.0000
80.0000 1600.0000
100.0000 2500.0000
140.0000 4900.0000
160.0000 6400.0000
5 1
2 2
4 4

Решение

Как и было указано в условии задачи, при решении задачи использовалась подпрограмма $SumDob$, которая возвращает сумму и произведение двух вещественных чисел $a$ и $b$. Потом мы с помощью цикла выводим пару чисел, полученных из подпрограммы $SumDob$ $n$ раз с $n$ пар введенных значений.

Условие задачи можно найти на e-olymp
Код решения — ideone

e-olymp 2814. Быстрое возведение в степень.

Задача

Быстрое возведение в степень

Быстрое возведение в степень

Очень часто возникает задача эффективного вычисления $x^{n}$ по данным $x$ и $n$, где $n$ — положительное целое число.
Предположим, например, что необходимо вычислить $x^{16}$. Можно просто начать с $x$ и 15 раз умножить его на $x$. Но тот же ответ можно получить всего за четыре умножения, если несколько раз возвести в квадрат получающийся результат, последовательно вычисляя $x^{2}$, $x^{4}$, $x^{8}$, $x^{16}$.
Эта же идея, в целом, применима к любому значению $n$ следующим образом. Запишем $n$ в виде числа в двоичной системе счисления (убирая нули слева). Затем заменим каждую «1» парой символов SX, а каждый «0» — символом S и вычеркнем крайнюю слева пару символов SX. Результат представляет собой правило вычисления $x^{n}$, в котором «S» трактуется как операция возведения в квадрат, а «X» — как операция умножения на $x$. Например, $n = 23$ имеет двоичное представление $10111$. Таким образом, мы формируем последовательность SXSSXSXSX, из которой удаляем начальную пару SX для получения окончательного правила SSXSXSX. Это правило гласит, что необходимо «возвести в квадрат, возвести в квадрат, умножить на $x$, возвести в квадрат, умножить на $x$, возвести в квадрат и умножить на $x$», т.е. последовательно вычислить значения $x^{2}$, $x^{4}$, $x^{5}$, $x^{10}$, $x^{11}$, $x^{22}$, $x^{23}$.

Вам нужно для заданного n сформулировать соответствующее правило быстрого возведения числа $x$ в степень $x^{n}$

Входные данные

Одно натуральное число $n$, не превышающее $2 \cdot 10^{9}$.

Выходные данные

Выведите строку для правила возведения числа $x$ в степень $n$ для получения $x^{n}$.

Тесты

# Входные данные Выходные данные
1 23 SSXSXSX
2 1
3 16 SSSS
4 1000000 SXSXSXSSXSSSSSXSSSXSSSSSS
5 2018 SXSXSXSXSXSSSSXS

Решение

С помощью первого цикла while в переменную $k$ записываем перевернутый двоичный код числа $n$. Переменную $c$ используем как счётчик кол-ва бит в $n$. Во втором цикле while выводим S или SX если правый бит $0$ или $1$ соответственно, теряя при это последнюю $1$ как и сказано по условию задачи.

Условие задачи можно найти на e-olymp
Код решения — ideone

e-olymp 219. Центральное отопление

Задача

Кар Карыч с Пином восемнадцать часов подряд распивали холодные молочные коктейли и закусывали их мороженым. После этого Кар Карыч свалился со страшной простудой, а Пин решил провести в домик своему другу центральное отопление. Расчет количества отопительных приборов необходимо производить строго по ГОСТу 800333-90-06*. Для простоты Пин решил купить простые батареи. Согласно таблице 14.1.3 этого ГОСТа, каждая батарея обогревает определённый объём воздуха — ровно [latex]d[/latex] кубометров. Комната, которую собирается для своего друга обогреть Пин, имеет следующие размеры:

• высота [latex]a[/latex],

• ширина [latex]b[/latex],

• длина [latex]c[/latex].

Определите минимальное количество батарей, которое необходимо купить Пину. Учтите только, что если в домике у Кар Карыча температура будет ниже, чем по ГОСТу, Кар Карыч никогда не поправится.

Входные данные

Четыре целых числа [latex]a, b, c, d (a, b, c \leq 10^{5}, d \leq 2 \cdot 10^{9})[/latex].

Выходные данные

Выведите минимальное количество батарей, которое необходимо купить Пину.

Тесты

# Входные данные Выходные данные
1 2 3 4 2 12
2 4 5 7 3 47
3 75 61 88 50 8052
4 986 764 390 54 5440529
5 1 1 1 2000000 1

Алгортм решения

  1. Находим объём комнаты по заданным сторонам по формуле [latex]V=a \cdot b \cdot c[/latex].
  2. Делим полученный объём на объём, обогреваемый одной батареей.
  3. Округляем при необходимости полученный ответ вверх, чтобы найти минимальное количество батарей.

Округление

Если разделить объём [latex]V[/latex] на [latex]d[/latex] нацело, то в остатке у нас может получиться [latex]0, 1, 2, \ldots , d-1[/latex]. Добавив [latex]d-1[/latex] к объёму [latex]V[/latex] мы получим в делении нацело остатки [latex]d-1, d, d+1, \ldots , 2d-2[/latex]. Первое число [latex]d-1<d[/latex], поэтому при делении нацело оно даёт [latex]0[/latex]. Остальные числа больше либо равны [latex]d[/latex], но меньше [latex]2d[/latex], значит любое из них при делении нацело на [latex]d[/latex] даст [latex]1[/latex].

Условие задачи можно найти на e-olymp
Код решения — ideone

e-olymp 920. Использование функций min и max

Задача

Задано три вещественных числа [latex]x, y[/latex] и [latex]z[/latex]. Определить [latex]\min\left(\max\left(x,y\right), \max\left(y,z\right), x+y+z\right)[/latex], воспользовавшись вспомогательными функциями для вычисления минимального и максимального элементов из двух заданных.

Входные данные

В одной строке задано три вещественных числа [latex]x, y[/latex] и [latex]z[/latex]. Значения чисел не превышают по модулю [latex]100[/latex].

Выходные данные

Вывести ответ с двумя десятичными знаками.

Тесты

# Входные данные Выходные данные
1  5 6 7  7.00
2  1.05 2.25 -2.15  1.15
3  3 3 3  3
4  8.85 5.67 7.33  7.33
5  12 -15 13  10

 

Алгоритм решения

  1. Находим максимум из [latex]x[/latex] и [latex]y[/latex].
  2. Находим максимум из [latex]y[/latex] и [latex]z[/latex].
  3. Находим минимум из найденных максимумов.
  4. Находим минимум из найденного минимума и суммы данных чисел.

Условие задачи можно найти на e-olymp
Код решения — ideone