Торговля акциями

@massa431 · Регистрация: 26.05.2020

Author24 — интернет-сервис помощи студентам

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

Разумеется, основным критерием, по которому такие системы оцениваются, является прибыль, которую приносит торговля с их применением. Для того, чтобы ее повысить при построении этих систем применяются различные математические методы и модели, такие, как, например, квадратичное программирование, нейронные сети, генетические алгоритмы и т. д.

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

Кроме этого, будем считать, что продажа и покупка будет осуществляться только с акциями одного типа. На начало этого периода вы располагаете суммой в x рублей. Для каждого из дней известна цена ai (от ask — цена предложения), по которой можно купить одну акцию, и цена bi (от bid — цена спроса), по которой можно одну акцию продать. При этом в соответствии с действующими правилами торгов на бирже разрешается продавать и покупать только целое число акций (например, если у вас есть 5 рублей, а акция стоит 2 рубля, то вы можете купить не более двух акций).

Требуется написать программу, которая по имеющимся данным о стоимости акций в каждый из дней, найдет оптимальную стратегию покупки и продажи акций.

Входные данные
Первая строка входного файла содержит два целых числа n и x (1 ≤ n ≤ 100000, 1 ≤ x ≤ 106).

Вторая строка входного файла содержит n целых чисел a1, . . . , aт. Третья строка входного файла содержит n целых чисел b1, . . . , bт. Для каждого индекса i (1 ≤ i ≤ n) выполняются неравенства 1 ≤ bi ≤ ai ≤ 1000.

Выходные данные
В первой строке выходного файла выведите максимальную сумму, которой вы можете обладать по окончании рассматриваемого периода. Во второй строке выведите два числа — номер дня d1, в который следует купить акции, и номер дня d2, в который эти акции следует продать (должно выполняться неравенство d2 > d1). При этом подразумевается, что покупается столько акций, сколько их можно купить на x рублей, а потом они все продаются. Если в найденной вами стратегии продавать и покупать акции не требуется, то выведите выведите во второй строке «-1 -1».

Если существует несколько вариантов оптимальной стратегии, то выведите любой из них

Примеры
входные данные
5 1000
2 3 1 4 3
1 2 1 2 3
выходные данные
3000
3 5
входные данные
5 1000
10 9 8 7 6
9 8 7 6 5
выходные данные
1000
-1 -1
Прошел 49 тестов из 51
не знаю в чем ошибка
Вот код

C++

#include <iostream>
#include <iostream>
#include <vector>
#include <sstream>
#include <ctime>
using namespace std;
 
int main(){
    int a[100000];
    int b[100000];
int imin = 0;
    int ibest = 0;
    int jbest = 1;
    int n;
cin >>n;
 int m;
 cin>>m;
    for(int i=0;  i<n;++i){
        cin>>a[i];
    }
     for(int i=0;  i<n;++i){
        cin>>b[i];
    }
    for (int j = 1; j < n; ++j)
    {
        if (a[j - 1] < a[imin])
            imin =  j - 1;
        if (b[j] / a[imin] > b[jbest] / a[ibest])
        {
            jbest = j;
            ibest = imin;
        }
    }
 
        if((m/a[ibest])*b[jbest]+m%a[ibest]<=m){
            cout<<m<<endl;
       cout<<"-1"<<" "<<"-1";}
        if((m/a[ibest])*b[jbest]+m%a[ibest]>m){
       cout<< (m/a[ibest])*b[jbest]+m%a[ibest]<<endl;
        cout << ibest+1 << " " << jbest+1 << endl;
        }
    
}

@oleg-m1973 · 10.07.2020, 15:03

Сообщение от massa431

Прошел 49 тестов из 51
не знаю в чем ошибка

Сообщение от massa431

for (int j = 1; j < n; ++j)
{
if (a[j - 1] < a[imin])
imin = j - 1;

Здесь, наверное, надо

C++

1 2	if (a[j] < a[imin]) imin = j ;

Добавлено через 1 минуту
И ты уверен, что imin и ibest/jbest должны рассчитываться в одном цикле? Может быть сначала нужно найти imin, а потом, в другом цикле, ibest/jbest?

@massa431 · 10.07.2020, 15:14 **[ТС]**

да в одном цикле. У меня где то не учтены 2 случая. То что исправил не подходит

@oleg-m1973 · 10.07.2020, 15:20

Сообщение от massa431

да в одном цикле. У меня где то не учтены 2 случая. То что исправил не подходит

Сообщение от massa431

int jbest = 1;

Почему у тебя jbest здесь равен единице? Т.е. b[0] вообще не должен учитываться в расчётах?

@massa431 · 10.07.2020, 20:59 **[ТС]**

Jbest равен единице так как мы не можем продавать акции в тот день когда купили их

@little_Ganter · 04.08.2021, 14:00

massa431, ты понял в чём ошибка?

Добавлено через 10 минут
massa431,

C++ (Qt)

if(m/a[imin]*b[i]+m%a[imin]>m/a[ibest]*b[jbest]+m%a[ibest]){
        jbest=i;
        ibest=imin;
    }

нужно сравнивать конечную прибыль, а не разницу акций

@1chous · 09.08.2021, 09:47

little_Ganter, у тебя зашло?

@irthgr · 09.08.2021, 18:49

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
int main()
{
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    vector<int> b(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    for(int i = 0; i < n; ++i){
        cin >> b[i];
    }
    int a2 = -2;
    int b2 = -2;
    int maxs = x;
    int mina = a[0];
    int mini = 0;
    for (int i = 0; i < n; ++i){
        if (((x / mina) * b[i] + x % mina) > maxs){
            maxs = (x / mina) * b[i] + x % mina;
            a2 = mini;
            b2 = i;
        }
        if (a[i] < mina){
            mina = a[i];
            mini = i;
        }
    }
    cout << maxs << endl;
    cout << a2 + 1 << " " << b2 + 1;
}

Задача то лёгкая

В общем, если помог нажмите на спасибо и удачи!

@massa431 1 / 1 / 0 Регистрация: 26.05.2020 Сообщений: 47
	10.07.2020, 15:14 [ТС]	3
	да в одном цикле. У меня где то не учтены 2 случая. То что исправил не подходит 0

@oleg-m1973 6579 / 4564 / 1843 Регистрация: 07.05.2019 Сообщений: 13,726
	10.07.2020, 15:20	4
	Сообщение от massa431 да в одном цикле. У меня где то не учтены 2 случая. То что исправил не подходит Сообщение от massa431 int jbest = 1; Почему у тебя jbest здесь равен единице? Т.е. b[0] вообще не должен учитываться в расчётах? 0

@massa431 1 / 1 / 0 Регистрация: 26.05.2020 Сообщений: 47
	10.07.2020, 20:59 [ТС]	5
	Jbest равен единице так как мы не можем продавать акции в тот день когда купили их 0

@1chous 3 / 3 / 0 Регистрация: 09.08.2021 Сообщений: 3
	09.08.2021, 09:47	7
	little_Ganter, у тебя зашло? 0

	09.08.2021, 18:49