Aisultan Kali

Задача №1.

Задача G. Депозит

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

У Жарасхана есть депозит в банке дураков. Сумма денег может быть отрицательной. Каждый день депозит пополняется на заранее известный процент. А также, Жарасхан может частично изымать деньги из этого депозита в любой момент когда ему будут нужны деньги. Но система банка работает таким образом, что можно изымать только определенный процент от денег в депозите. У Жарасхана есть история операций по депозиту за каждый день в виде процентов. Изначально у Жарасхана есть

$s$ денег на депозите. Если Жарасхан изымал деньги то процент отрицательный, если банк пополнял то положительный соответственно. Жарасхану стало интересно, на какой день у него была максимально возможная сумма и на какой минимальная. Так как Жарасхан очень занят работой, он попросил вас найти те самые дни.

Формат входного файла

В первой строке входного файла заданы два целых числа

$n$

$(1 \le n \le 25)$ - количество дней в истории,

$s$

$(-100 \le s \le 100)$ - изначальная сумма у Жарасхана на депозите. Во второй строке входного файла заданы

$n$ чисел

$a_i$

$(-2 \le a_i \le 2)$ - коэффициент процента на

$i$ -й день. Каждое

$a_i$ задано с не более двумя знаками после запятой.

Формат выходного файла

Выведите два целых числа - день в котором у Жарасхана была максимально возможная сумма и день в котором у Жарасхана была минимально возможная сумма на депозите. Если соответствующих дней несколько - выведите самый ранний.

Система оценки

Данная задача состоит из 4 подзадач:

$n = 1$ . Оценивается в $13$ баллов.
$0 \le a_i \le 2$ . Оценивается в $5$ баллов.
$1 \le n \le 15$ . Оценивается в $40$ баллов.
Ограничения из условий. Оценивается в $42$ баллов.

Примеры:

Вход

3 100
0.1 -0.4 2

Ответ

2 3

Вход

3 100
0.5 1 2

Ответ

0 3

Вход

2 100
1 -0.5

Ответ

0 1

Замечание

В первом тестовом примере сумма после каждого дня:

$110, 66, 132$ . Соответственно на второй день имеется минимально возможная сумма и на последнем максимальная. Во втором тестовом примере, так как сумма только возрастает изначальная сумма является минимальной. ( Aisultan Kali )
комментарий/решение(10) олимпиада

Задача №2.

Задача A. Волшебство на последовательностях

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Юный волшебник Асхат научился новому заклинанию - теперь он умеет заменять любую последовательность ее префиксной суммой!
Дабы закрепить новые знания, он решил немного попрактиковаться. Он раздобыл последовательность очень большого размера, каждый элемент которой равен

$1$ , и очень много раз применил к ней вышеописанное заклинание.
В этой задаче, вам предстоит показать, что ваши навыки программирования ничем не уступают магии. На каждый соответствующий запрос, а их будет очень много, найдите чему было равно число в

$i$ -м ряду после

$k$ применений заклинания. Поскольку эти числа могут быть довольно большими, выведите остаток от деления этих чисел на 1000000007.

Формат входного файла

Первая строка ввода содержит целое число

$Q$ — количество запросов к вашей программе.
Каждая из следующих

$Q$ строк описывает очередной запрос и содержит два целых положительных числа — номер столбца и количество предварительных применений заклинания соответственно.

Формат выходного файла

Выведите $Q

$целых чисел, по одному в строке — значение в ячейке в$ i

$-м ряду после$ k$ применений заклинания по модулю 1000000007.

Система оценки

Подзадача 1 (10 баллов) —

$1 <= Q <= 10^5, 1 <= i, k <= 5$
Подзадача 2 (10 баллов) —

$1 <= Q <= 10^5, 1 <= i <= 10^5, k=1$
Подзадача 3 (20 баллов) —

$1 <= Q <= 10^5, 1 <= i,k <= 100$
Подзадача 4 (20 баллов) —

$1 <= Q <= 10^5, 1 <= i,k <= 10^3$
Подзадача 5 (40 баллов) —

$1 <= Q <= 10^5, 1 <= i,k <= 10^5$

Пример:

Вход

2
2 1
1 3

Ответ

2
1

Замечание

Напомним, что последовательность - это одномерный массив содержащий целочисленные значения. Один из возможных примеров последовательности размерностью 4 приведен ниже:

Префиксной суммой называется последовательность, где каждый элемент заменен на сумму чисел в соответствующем ему подпоследовательности, с противоположной вершиной в ячейке

$(1, 1)$ . Формально, определим префиксную сумму последовательности

$A$ как последовательность

$B$ такую, что для любых

$i > 0$ выполняется

$B_i = A_i + B_{i - 1}$
В то время как значения в ячейках

$B$ с

$i = 0$ равны нулю.
Например префиксной суммой данной последовательности

Будет следующая последовательность:

( Aisultan Kali )
комментарий/решение(4) олимпиада