Решаю следующую задачу:
Задача №1253. Торговля акциями
В настоящее время на бирже при торговле акциями активно применяются компьютерные системы, которые упрощают и автоматизируют процесс покупки и продажи акций. Некоторые из них даже позволяют вести торговлю вообще без участия человека.
Разумеется, основным критерием, по которому такие системы оцениваются, является прибыль, которую приносит торговля с их применением. Для того, чтобы ее повысить при построении этих систем применяются различные математические методы и модели, такие, как, например, квадратичное программирование, нейронные сети, генетические алгоритмы и т. д.
Основной трудностью при создании таких систем является то, что они должны некоторым образом учитывать изменение стоимости акций в будущем, а также его прогнозировать. Ваша задача несколько проще — курсы продажи и покупки акций за весь период из 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
Испробовал разные решения, но многие тесты все равно не проходят (статус: неправильный ответ)
Исходный код:
#include<iostream>
#include<stdio.h>
#include<queue>
#include<set>
#include<functional>
#include<stack>
#include<iterator>
#include<algorithm>
#include<math.h>
#include<limits>
using namespace std;
int main()
{
int n,x,a[100009],b[100009],mina,mini,a2=-2,b2=-2;
cin>>n>>x;
int maxs = x;
for (int i=0; i<n; i++)
cin>>a[i];
for (int i=0; i<n; i++)
cin>>b[i];
mina = a[0];
mini = 0;
for (int i=1; i<n; i++)
{
if ((x/mina)*b[i]>maxs)
{
maxs = (x/mina)*b[i];
a2 = mini;
b2 = i;
}
if (a[i]<mina)
{
mina = a[i];
mini=i;
}
}
cout<<maxs<<endl;
cout<<a2+1<<" "<<b2+1;
return 0;
}
Помогите пожалуйста, может я не учел какие-то вещи из условия. Буду рад контрпримерам.
Средний
