Воды слонам!

@dmitrii2000 · Регистрация: 03.05.2020

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

Воды слонам!
Кроме Земли, пандорианцы уже много тысячелетий исследуют и другие планеты. Большой интерес для них в прошлом представляла планета Арракис. К сожалению, с началом исследований на Земле финансирование исследований на Арракисе было существенно урезано, и местным агентам-исследователям пришлось искать дополнительные источники дохода.

К счастью, пандорианцы очень хорошо разбираются в финансовых вопросах. Им не составило труда проанализировать политические, экономические и психологические тенденции, а также некоторые другие факторы, не имеющих названий на земных языках и на основе этих данных точно предсказать изменение стоимости воды на Арракисе на ближайший год. Как известно, вода на этой планете является главной ценностью после золота, на которое эту воду можно купить.

Изначально пандорианцы обладают запасом золота в 10 золотых слитков. Они решили в один из дней года купить на все это золото воды, а в какой-то последующий день продать всю купленную воду и получить прибыль за счет разницы стоимости. К примеру, если бы стоимость воды в день покупки составляла 1 литр за 4 золотых слитка, а стоимость воды в день продажи – 1 литр за 6 золотых слитков, то пандорианцы могли бы получить купить 104=2.5 литра воды, а продать они эту воду смогут за 2.5×6=15 золотых слитков. Таким образом, прибыль пандорианцев составила бы 15−10=5 золотых слитков. Конечно же, пандорианцы хотят максимизировать свой доход в результате этих махинаций. Помогите им выбрать оптимальные дни для покупки и продажи воды!

Входные данные
В первой строке задано целое число 2 ≤ N ≤ 100 000 — количество дней в году на планете Арракис.

Во второй строке заданы N целых положительных чисел a i ( 1 ≤ i ≤ N , 1 ≤ a i ≤ 5000 ), задающих стоимость воды на Арракисе в день i .

Выходные данные
Выведите два целых числа: первое число — номер дня, в который стоит купить воду, второе число — номер дня, в который следует воду продать. Дни нумеруются с единицы. Если оптимальных пар дней для покупки/продажи несколько, то выведите любую из них.

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

Примеры
входные данные
6
10 3 5 3 11 9
выходные данные
2 5
входные данные
4
5 5 5 5
выходные данные
0 0

@Kastaneda · 28.07.2021, 14:50

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

Воды слонам!

Земли рабочим!

Новичок · 28.07.2021, 15:59

Я б посчитал максимумы на суффиксах, дальше за линейное время кажется очевидное решение.

@Kuzia domovenok · 28.07.2021, 16:19

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

Новичок · 28.07.2021, 16:21

Или минимум на префиксе, да.

@Kuzia domovenok · 28.07.2021, 16:23

Новичок, わからない

@dmitrii2000 · 28.07.2021, 17:47 **[ТС]**

Скиньте код пожалуйста!

@Kastaneda · 30.07.2021, 07:50

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

Скиньте код пожалуйста!

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
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <string>
using namespace std;
 
int main() {
    deque<int> left;
    deque<int> right;
    vector<int> v;
    int n; cin >> n;
    string t;
    int a, j = 0, b;
    for (int i = 0; i < n; i++) {
        cin >> t;
        if (t[0] == '+') {
            cin >> a;
            right.push_back(a);
            if (right.size() - left.size() == 1) {
                b = right[0];
                right.pop_front();
                left.push_back(b);
            }
        }
        if (t[0] == '*') {
            cin >> a;
            if (right.size() == left.size())
                left.push_back(a);
            else if (left.size() - right.size() == 1)
                right.push_front(a);
 
        }       
        if (t[0] == '-') {
            if (left.size() != 0) {
                v.push_back(left[0]);
                left.pop_front();
 
            }
            else {
                v.push_back(right[0]);
                right.pop_front();
            }
        }
    }
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << endl;
    return 0;
}

@dmitrii2000 · 30.07.2021, 08:07 **[ТС]**

Выводит в неверном формате

@Kastaneda · 30.07.2021, 08:16

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

Выводит в неверном формате

Ну подправь немного.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@dmitrii2000 2 / 2 / 0 Регистрация: 03.05.2020 Сообщений: 202

	Воды слонам! 28.07.2021, 14:38. Показов 6160. Ответов 9 Метки нет (Все метки) Воды слонам! Кроме Земли, пандорианцы уже много тысячелетий исследуют и другие планеты. Большой интерес для них в прошлом представляла планета Арракис. К сожалению, с началом исследований на Земле финансирование исследований на Арракисе было существенно урезано, и местным агентам-исследователям пришлось искать дополнительные источники дохода. К счастью, пандорианцы очень хорошо разбираются в финансовых вопросах. Им не составило труда проанализировать политические, экономические и психологические тенденции, а также некоторые другие факторы, не имеющих названий на земных языках и на основе этих данных точно предсказать изменение стоимости воды на Арракисе на ближайший год. Как известно, вода на этой планете является главной ценностью после золота, на которое эту воду можно купить. Изначально пандорианцы обладают запасом золота в 10 золотых слитков. Они решили в один из дней года купить на все это золото воды, а в какой-то последующий день продать всю купленную воду и получить прибыль за счет разницы стоимости. К примеру, если бы стоимость воды в день покупки составляла 1 литр за 4 золотых слитка, а стоимость воды в день продажи – 1 литр за 6 золотых слитков, то пандорианцы могли бы получить купить 104=2.5 литра воды, а продать они эту воду смогут за 2.5×6=15 золотых слитков. Таким образом, прибыль пандорианцев составила бы 15−10=5 золотых слитков. Конечно же, пандорианцы хотят максимизировать свой доход в результате этих махинаций. Помогите им выбрать оптимальные дни для покупки и продажи воды! Входные данные В первой строке задано целое число 2 ≤ N ≤ 100 000 — количество дней в году на планете Арракис. Во второй строке заданы N целых положительных чисел a i ( 1 ≤ i ≤ N , 1 ≤ a i ≤ 5000 ), задающих стоимость воды на Арракисе в день i . Выходные данные Выведите два целых числа: первое число — номер дня, в который стоит купить воду, второе число — номер дня, в который следует воду продать. Дни нумеруются с единицы. Если оптимальных пар дней для покупки/продажи несколько, то выведите любую из них. Выведите два нуля, если покупка и продажа воды по указанной схеме не принесет пандорианцам прибыли. Примеры входные данные 6 10 3 5 3 11 9 выходные данные 2 5 входные данные 4 5 5 5 5 выходные данные 0 0 0

Новичок 1682 / 1098 / 489 Регистрация: 17.07.2012 Сообщений: 5,360
	28.07.2021, 15:59
	Я б посчитал максимумы на суффиксах, дальше за линейное время кажется очевидное решение. 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	28.07.2021, 16:19
	я б создал массив размера 100000 и заполнил бы его индексами самого дешёвого дня до этого момента. потом второй раз прошёлся бы циклом по этому массиву, ища максимальную прибыль от продажи в этот день. 0

Новичок 1682 / 1098 / 489 Регистрация: 17.07.2012 Сообщений: 5,360
	28.07.2021, 16:21
	Или минимум на префиксе, да. 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	28.07.2021, 16:23
	Новичок, わからない 0

@dmitrii2000 2 / 2 / 0 Регистрация: 03.05.2020 Сообщений: 202
	28.07.2021, 17:47 [ТС]
	Скиньте код пожалуйста! 0

@dmitrii2000 2 / 2 / 0 Регистрация: 03.05.2020 Сообщений: 202
	30.07.2021, 08:07 [ТС]
	Выводит в неверном формате 0