Мбокоины

@smihds · Регистрация: 19.09.2020

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

Условие
Саша сильно увлекся криптовалютами. Недавно он наткнулся на мбокоины — очередную криптовалюту.

Сейчас у Саши S рублей. Сегодня начинаются торги мбокоинами, они будут длиться n дней. Каждый день торгов Саша может либо купить сколько-то мбокоинов, либо продать какое-то количество мбокоинов из тех, которые у него есть, либо ничего не делать. В i-й день можно купить один мбокоин за ai рублей или продать один мбокоин за bi рублей.

Какое максимальное количество рублей может оказаться у Саши под конец торгов?

Формат входных данных
В первой строке вводятся два целых числа n и S (1≤n≤50000,1≤S≤1000000) — продолжительность торгов в днях и кол-во рублей у Саши в начале торгов соответственно.

Последующие N строк содержат информацию о каждем дне торгов. В i-й из этих строк вводятся два целых числа ai и bi (1≤bi≤ai≤1000000) — цена покупки мбокоина и продажи мбокоина соответственно.

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

входные данные
3 1000
100 99
110 105
90 80
выходные данные
1050

входные данные
3 15
4 3
9 4
9 8
выходные данные
27

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

@eaa · 21.10.2022, 10:25

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

Если честно, пока даже не знаю, как к ней подойти

Динамическое программирование

@Red white socks · 21.10.2022, 10:42

Рассмотрим сначала случай, когда во все дни цена продажи равна цене покупки. Сможете сформулировать стратегию игрока?

Добавлено через 2 минуты

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

Динамическое программирование

Кажется, что здесь за линейное время есть эвристический алгоритм.

@eaa · 21.10.2022, 10:50

Red white socks, дп тоже линейное. да можно из без прекалка, не спорю.

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

Добавлено через 1 минуту
smihds, кстати решение этой задачи есть тут на форуме, формулировка только другая. ищите.

@Red white socks · 21.10.2022, 11:08

eaa, наверное двупроходной все же.
За первый проход отмечаем минимумы в последовательности цены покупки и максимумы в цене продажи, а во втором проходе их чередуем.
Правда сейчас у меня появились к нему вопросы, полной уверенности нет.
С ДП все таки понадежнее.

@eaa · 21.10.2022, 11:17

Не по теме:

Red white socks, ТС наверное думает. О чем они говорят?)))

@Afrikanskaya_ab · 21.10.2022, 18:01

eaa, покажи, какое, пожалуйста)

@d1skr1m1nant · 22.10.2022, 12:44

Red white socks, не могли бы подсказать, что конкретно нужно делать во втором проходе, и как это нужно делать. Уже 2 день бьюсь над задачей. Вот код:

Python

n, s = map(int, input().split())
count = 0
buy = []
sell = []
buy_day = 0
sell_day = 0
for i in range(n):
    a, b = map(int, input().split())
    buy.append(a)
    sell.append(b)
for i in range(n): #и дальше не знаю что нужно сделать...

Добавлено через 2 часа 6 минут
В общем я всё немного переосмыслил, но код всё равно проходит далеко не все тесты...

Python

n, s = map(int, input().split())
delcount = 0
buy = []
sell = []
buycount = 0
for i in range(n):
    a, b = map(int, input().split())
    buy.append(a)
    sell.append(b)
for i in range(n):
    if buy.index(min(buy)) > sell.index(max(sell)):
        buy.remove(min(buy))
        delcount += 1
    else:
        buycount = s // min(buy)
        s -= (s // min(buy)) * min(buy)
        s += buycount * max(sell)
        break
print(s)

@Red white socks · 22.10.2022, 13:14

d1skr1m1nant, я уже сказал, что не уверен в 100% правильности такого подхода, но если решили идти этим путем, то

Сообщение от Red white socks

Рассмотрим сначала случай, когда во все дни цена продажи равна цене покупки. Сможете сформулировать стратегию игрока?

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

Уже 2 день бьюсь над задачей

О, да это вы даже не начали)
Это задача не в одно действие, к тому же и подумать тут есть где. И неделю не зазорно потратить)

@eaa · 22.10.2022, 13:29

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

if buy.index(min(buy)) > sell.index(max(sell))

это у вас выполняется за O(n). Итого у вас алгоритм получается за O(n^2).
Подумайте как это сделать за O(1).

@d1skr1m1nant · 22.10.2022, 14:21

eaa, я так понимаю, что нужно реализовать эту часть кода так, чтобы она не зависела от n?

Новые блоги и статьи
Из чего и как собрать свой домашний кинотеатр bt_guru 21.01.2025 Создание домашнего кинотеатра: от идеи до реализации В современном мире домашний кинотеатр стал неотъемлемой частью комфортного жилого пространства, предоставляя возможность наслаждаться. . .	Ошибки стиральных машин bt_guru 21.01.2025 Современные стиральные машины представляют собой сложные электронные устройства, оснащенные множеством датчиков и систем контроля. Они способны самостоятельно определять вес загруженного белья,. . .	Копирование (маппинг) объектов в JavaScript bytestream 21.01.2025 В современной разработке программного обеспечения копирование объектов представляет собой фундаментальную операцию, которая требует особого внимания и понимания. Маппинг объектов в JavaScript – это. . .	Как работать с Apache Kafka в C# .NET bytestream 21.01.2025 Apache Kafka представляет собой распределенную платформу потоковой передачи данных, которая произвела революцию в области обработки больших объемов информации в реальном времени. Эта система,. . .	Как использовать RabbitMQ в C# .NET bytestream 21.01.2025 RabbitMQ представляет собой мощный брокер сообщений, который эффективно решает эту задачу, обеспечивая надежную передачу данных между множеством приложений. Этот инструмент реализует протокол AMQP. . .	Как объединить последние коммиты в Git bytestream 21.01.2025 В мире разработки программного обеспечения система контроля версий Git стала незаменимым инструментом для управления исходным кодом. Одной из наиболее полезных, но порой сложных для освоения функций. . .
Как запушить новую локальную ветку (branch) в удалённый репозиторий Git и отслеживать её bytestream 21.01.2025 В современной разработке программного обеспечения система контроля версий Git стала неотъемлемым инструментом для эффективного управления кодом и организации командной работы. Одной из ключевых. . .	Как создать директорию и все родительские директории, указанные в пути, с помощью Python bytestream 21.01.2025 Python предоставляет мощные инструменты для работы с файловой системой через встроенные модули os и pathlib, которые значительно упрощают процесс манипуляции директориями. Эти модули содержат. . .	Как работать с массивами в JavaScript bytestream 21.01.2025 Массивы в JavaScript представляют собой один из фундаментальных типов данных, который позволяет хранить упорядоченные коллекции различных элементов в одной переменной. Эта структура данных является. . .	Какая максимальная длина адреса (URL) в различных браузерах и стандартах bytestream 21.01.2025 В современном мире интернет-технологий URL-адреса (Uniform Resource Locator) играют фундаментальную роль в функционировании веб-пространства. Эти уникальные идентификаторы ресурсов стали неотъемлемой. . .	Как сбросить локальный репозиторий до состояния удалённого репозитория Git bytestream 21.01.2025 При разработке программного обеспечения с использованием системы контроля версий Git разработчики часто сталкиваются с необходимостью синхронизации локального и удаленного репозиториев. Данная задача. . .	Как запретить подсветку выделенного текста с помощью CSS bytestream 20.01.2025 Подсветка текста при выделении является стандартным поведением браузера, которое не всегда соответствует дизайнерским решениям или функциональным требованиям веб-приложения. Выделение текста может. . .

@smihds 0 / 0 / 0 Регистрация: 19.09.2020 Сообщений: 8
		1
	Мбокоины 21.10.2022, 09:31. Показов 1660. Ответов 10 Метки python, циклы for (Все метки) Условие Саша сильно увлекся криптовалютами. Недавно он наткнулся на мбокоины — очередную криптовалюту. Сейчас у Саши S рублей. Сегодня начинаются торги мбокоинами, они будут длиться n дней. Каждый день торгов Саша может либо купить сколько-то мбокоинов, либо продать какое-то количество мбокоинов из тех, которые у него есть, либо ничего не делать. В i-й день можно купить один мбокоин за ai рублей или продать один мбокоин за bi рублей. Какое максимальное количество рублей может оказаться у Саши под конец торгов? Формат входных данных В первой строке вводятся два целых числа n и S (1≤n≤50000,1≤S≤1000000) — продолжительность торгов в днях и кол-во рублей у Саши в начале торгов соответственно. Последующие N строк содержат информацию о каждем дне торгов. В i-й из этих строк вводятся два целых числа ai и bi (1≤bi≤ai≤1000000) — цена покупки мбокоина и продажи мбокоина соответственно. Формат выходных данных Выведите максимальное количество рублей, которое может оказаться у Саши под конец торгов. входные данные 3 1000 100 99 110 105 90 80 выходные данные 1050 входные данные 3 15 4 3 9 4 9 8 выходные данные 27 Если честно, пока даже не знаю, как к ней подойти. Думала на каждой итерации проверять, что нам выгоднее сделать: купить или продать, но тогда еще нужно учесть, что на следующей итерации продать или купить может быть выгоднее. Получается, нужно тогда два списка создать, проходиться по ним и смотреть, что сейчас будет выгоднее делать или не делать... Не знаю, в общем, буду благодарна за любые идеи! 0

@eaa Status 418 4580 / 2348 / 601 Регистрация: 26.11.2017 Сообщений: 5,264 Записей в блоге: 3
	21.10.2022, 10:25	2
	Сообщение от smihds Если честно, пока даже не знаю, как к ней подойти Динамическое программирование 0

@Red white socks 4511 / 1887 / 335 Регистрация: 18.01.2021 Сообщений: 3,471
	21.10.2022, 10:42	3
	Рассмотрим сначала случай, когда во все дни цена продажи равна цене покупки. Сможете сформулировать стратегию игрока? Добавлено через 2 минуты Сообщение от eaa Динамическое программирование Кажется, что здесь за линейное время есть эвристический алгоритм. 0

@eaa Status 418 4580 / 2348 / 601 Регистрация: 26.11.2017 Сообщений: 5,264 Записей в блоге: 3
	21.10.2022, 10:50	4
	Red white socks, дп тоже линейное. да можно из без прекалка, не спорю. Добавлено через 3 минуты однопроходной Вы имеете в виду. но с предкалком префикс-максимумов, имхо более нагляднее будет. может ошибаюсь. Добавлено через 1 минуту smihds, кстати решение этой задачи есть тут на форуме, формулировка только другая. ищите. 1

@Red white socks 4511 / 1887 / 335 Регистрация: 18.01.2021 Сообщений: 3,471
	21.10.2022, 11:08	5
	eaa, наверное двупроходной все же. За первый проход отмечаем минимумы в последовательности цены покупки и максимумы в цене продажи, а во втором проходе их чередуем. Правда сейчас у меня появились к нему вопросы, полной уверенности нет. С ДП все таки понадежнее. 1

@eaa
	21.10.2022, 11:17 #6
	Не по теме: Red white socks, ТС наверное думает. О чем они говорят?))) 0

@Afrikanskaya_ab 1 / 1 / 0 Регистрация: 18.10.2022 Сообщений: 9
	21.10.2022, 18:01	7
	eaa, покажи, какое, пожалуйста) 0

@Red white socks 4511 / 1887 / 335 Регистрация: 18.01.2021 Сообщений: 3,471
	22.10.2022, 13:14	9
	d1skr1m1nant, я уже сказал, что не уверен в 100% правильности такого подхода, но если решили идти этим путем, то Сообщение от Red white socks Рассмотрим сначала случай, когда во все дни цена продажи равна цене покупки. Сможете сформулировать стратегию игрока? Сообщение от d1skr1m1nant Уже 2 день бьюсь над задачей О, да это вы даже не начали) Это задача не в одно действие, к тому же и подумать тут есть где. И неделю не зазорно потратить) 0

@eaa Status 418 4580 / 2348 / 601 Регистрация: 26.11.2017 Сообщений: 5,264 Записей в блоге: 3
	22.10.2022, 13:29	10
	Сообщение от d1skr1m1nant if buy.index(min(buy)) > sell.index(max(sell)) это у вас выполняется за O(n). Итого у вас алгоритм получается за O(n^2). Подумайте как это сделать за O(1). 0

@d1skr1m1nant 1 / 1 / 0 Регистрация: 08.06.2022 Сообщений: 10
	22.10.2022, 14:21	11
	eaa, я так понимаю, что нужно реализовать эту часть кода так, чтобы она не зависела от n? 0