Районная олимпиада по информатике. 2018-2019 учебный год. 8-11 классы


Задача 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 подзадач:
  1. $n = 1$. Оценивается в $13$ баллов.
  2. $0 \le a_i \le 2$. Оценивается в $5$ баллов.
  3. $1 \le n \le 15$. Оценивается в $40$ баллов.
  4. Ограничения из условий. Оценивается в $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 )
посмотреть в олимпиаде

Комментарий/решение:

  0
2019-01-08 19:20:29.0 #

показать/скрыть код

  0
2019-01-08 22:41:23.0 #

показать/скрыть код

  0
2019-01-08 23:06:27.0 #

В пояснении первого примера неправильно посчитано количество денег на депозите после третьего дня: вместо 132 должно быть 198.