Районная олимпиада по информатике. 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 )

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

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

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{

int n;
float s;
cin >> n >> s;
double max_m = s, min_m = s, max_d = 0, min_d = 0;

for(int i = 0; i < n; i++){

    float percent;
    cin >> percent;

    s = s + (abs(s) * percent);
    if(s > max_m) {max_m = s; max_d = i + 1;}
    if(s < min_m) {min_m = s; min_d = i + 1;}

}

cout << min_d << " " << max_d;

    return 0;
}

C++

Copy

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    double s;
    cin >> s;
    ll minimum_index=0, maximum_index=0, minimum = s, maximum = s;
    for (int i=1; i<=n; i++) {
        double cur;
        cin >> cur;
        s += abs(s)*cur;
        if (minimum > s) {
            minimum = s;
            minimum_index = i;
        }
        if (maximum < s) {
            maximum = s;
            maximum_index = i;
        }
    }
    cout << minimum_index << ' ' << maximum_index << '\n';
    return 0;
}

C++

Copy

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

и как понимать 0 в результате второго и третьего теста или 3 в результате первого и второго ?

уже не важно

Помогите, что не так?

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

#include <iostream>
#include <cmath>
using namespace std;

int f(double a){
    return round(a*100)/100;
}
int main()
{
    int n,s,minimum=0,maximum=0;
    cin>>n>>s;
    if(n>25||n<0||s<-100||s>100){
        return 0;
    }
    double mi=s,mx=s;;

    for(int i=0;i<n;i++){
        float p;
        cin>>p;
        f(p);
        if(p<-2||p>2){
            return 0;
        }
        s=(s*p)+s;
        if(s>mx){
            mx=s;
            maximum=i+1;
        }
        if(s<mi){
            mi=s;
            minimum=i+1;
        }
    }
    cout<<minimum<<" "<<maximum;
    return 0;
}

C++

Copy

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

with open('input') as file:

    inner, data = file.readlines(), list()

    for line in inner: data.append(line.split('\n')[0])

d, s, k, b = int(data[0].split()[0]), int(data[0].split()[1]), data[1].split(), list()

b = [int(s)]

for day in range(0,d):

    if str(float(k[day])).split('.')[0] == '0' or str(float(k[day])).split('.')[0] == '-0':
        p = int(b[len(b)-1]) + (int(b[len(b)-1]) * int(float(k[day]) * 100) / 100)

    elif int(k[day]) == 0: p = int(b[len(b)-1])

    else: p = int(b[len(b)-1]) * float(k[day])

    b.append(p)

max, min, billing = [0, 0], [b[0], 0], dict()

for num in range(0, len(b)):
    billing.update({int(num): b[num]})

for key in range(0, len(billing.values())):

    if billing[key] > max[0] and key != max[1]: max[0], max[1] = int(billing[key]), int(key)

    if billing[key] <= min[0]: min[0], min[1] = int(billing[key]), int(key)

with open('output', 'w') as file: file.write(str(min[1]) + ' ' + str(max[1]))

C++

Copy

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

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  double s;
  cin >> n >> s;
  double mx_f = s, mx_s = 0, mn_f = s, mn_s = 0;
  for(int i = 1; i <= n; i++){
    double p;
    cin >> p;
    s = s + (abs(s) * p);
    if(s > mx_f) mx_f = s, mx_s = i;
    if(s < mn_f) mn_f = s, mn_s = i;
  }
  cout << mn_s << " " << mx_s;
}

C++

Copy