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

@ProgrammistBegi · Регистрация: 14.04.2024

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

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

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

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

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

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

Первая строка входных данных содержит целые числа N
и X
(1 ⩽ N ⩽ 100 000,1 ⩽ X ⩽ 106
). Вторая строка содержит N
целых чисел a1, ..., aN
. Третья строка содержит N
целых чисел b1, ..., bN(1 ⩽ bi ⩽ ai ⩽ 1 000)
.

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

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    long long n,X;
    cin >> n >> X;
    vector<int> stocks_before(n);
    for (int i = 0; i < n; i++)
        cin >> stocks_before[i];
    vector<int> stocks_after(n);
    for (int i = 0; i < n; i++)
        cin >> stocks_after[i];
    int imin = 0;
    int ibest = 0;
    int jbest = 1;
    for (int i = 2; i < n; i++)
    {
        if (stocks_before[i-1] < stocks_before[imin])
        {
            imin = i-1;
        }
        if (stocks_after[i] - stocks_before[imin] >= 
            stocks_after[ibest] - stocks_before[ibest])
        {
            jbest = i;
            ibest = imin;
        }
    }
    if (X % stocks_before[ibest] + X / stocks_before[ibest] * stocks_after[jbest] > X)
    {
        cout << X % stocks_before[ibest] + X / stocks_before[ibest] * stocks_after[jbest];
        cout << '\n';
        cout << ibest + 1 << " " << jbest + 1;
    }
    else
    {
        cout << X;
        cout << '\n' << -1 << " " << -1;
    }
}

Не могу понять в чем проблема,вроде все случаи разобрал,помогите пожалуйста!Я только начинающий

@gunslinger · 26.06.2024, 19:08

SmallEvil, я что-то даже не подумал, что можно с конца двигаться. Точнее, не предполагал, что нужно отталкиваться от значения b_max, а это более чем логично и очевидно (но оказалось, что не для меня).

Подход ТС-а не смотрел, хотел сам ответ получить. Получил, но через одно место.

@ProgrammistBegi · 26.06.2024, 20:37 **[ТС]**

Всем спасибо,особенно gunslinger и SmallEvil помогли мне.Задачу решил,вот конечное решение:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    long long n,X;
    cin >> n >> X;
    vector<int> stocks_before(n);
    for (int i = 0; i < n; i++)
        cin >> stocks_before[i];
    vector<int> stocks_after(n);
    for (int i = 0; i < n; i++)
        cin >> stocks_after[i];
    int imin = 0;
    int ibest = 0;
    int jbest = 1;
    for (int i = 2; i < n; i++)
    {
        if (stocks_before[i-1] < stocks_before[imin])
        {
            imin = i-1;
        }
        if (X % stocks_before[imin] + X / stocks_before[imin] * stocks_after[i]>=
            X % stocks_before[ibest] + X / stocks_before[ibest] * stocks_after[jbest])
        {
            jbest = i;
            ibest = imin;
        }
    }
    if (X % stocks_before[ibest] + X / stocks_before[ibest] * stocks_after[jbest] > X)
    {
        cout << X % stocks_before[ibest] + X / stocks_before[ibest] * stocks_after[jbest];
        cout << '\n';
        cout << ibest + 1 << " " << jbest + 1;
    }
    else
    {
        cout << X;
        cout << '\n' << -1 << " " << -1;
    }
}

Решение проходит все тесты

@gunslinger · 26.06.2024, 21:07

Переделал свой код с учетом нормального подхода:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
using namespace std;
 
void func (long N, long X, long *a, long *b)
{
  long i, di = N - 1, d1 = di, d2 = di, max = 0, tmp = X, B = 0;
  for (i = d1; i > 0; i--)
  {
    if (B < b[i])
    {
      B = b[i];
      di = i + 1;
    }
    tmp = a[i - 1];
    tmp = (X / tmp) * (B - tmp);
    if (tmp > max)
    {
      max = tmp;
      d1 = i;
      d2 = di;
    }
  }
 
  cout << X + max << endl;
 
  if (max > 0)
    cout << d1 << " " << d2;
  else
    cout << "-1 -1";
}
 
int main()
{
  const long N = 4;
  long X = 10;
  long a[N] = {6, 3, 12, 5}, b[N] = {2, 1, 11, 4};
  func(N, X, a, b);
 
  cout << endl;
  system("pause");
  return 0;
}

Результат:

Code
1
2
34
2 3

Добавлено через 46 секунд
ProgrammistBegi, не за что.

Новые блоги и статьи Все статьи Все блоги /
FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .

@gunslinger place status here 3192 / 2227 / 640 Регистрация: 20.07.2013 Сообщений: 6,028
	26.06.2024, 19:08
	SmallEvil, я что-то даже не подумал, что можно с конца двигаться. Точнее, не предполагал, что нужно отталкиваться от значения b_max, а это более чем логично и очевидно (но оказалось, что не для меня). Подход ТС-а не смотрел, хотел сам ответ получить. Получил, но через одно место. 0