Задача к ЕГЭ по информатике на тему «практика программирования» №1

Просмотров 8 Комментарии 0

У Арчи есть $10000$ тугриков. Он хочет их эффективно вложить в лимонад. Ему даны цены за $1000$ кубометров лимонада за $N$ дней. Арчи может только один раз купить лимонад в день $i$ и продать его в один из последующих дней $j$ $(i < j)$ . Помогите Арчи определить номера дней для покупки и продажи лимонада, чтобы получить максимальную прибыль. В ответ укажите день покупки и день продажи через пробел.

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

В первой строке файла содержится число дней $N$ $(1 ≤ N ≤ 1000000)$ .

В последующих $N$ строках файла содержатся цены $p$ $(1 ≤ p ≤ 10000)$ за $1000$ кубометров лимонада в каждый из дней. Дни нумеруются с единицы.

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

Два числа $i$ и $j$ — номера дней для покупки и продажи лимонада.

file = open("temp.txt")
n = int(file.readline())
prices = [int(file.readline()) for x in range(n)]

maxProfit = -1e9
minIndex = 0
left = 0
right = 0

for i in range(1, n):
    purchasePricePerUnit = prices[minIndex] / 1000
    lemonadeThatCanBeBought = 1000 / purchasePricePerUnit
    salePricePerUnit = prices[i] / 1000
    lemonadeThatCanBeSold = lemonadeThatCanBeBought * salePricePerUnit
    profit = lemonadeThatCanBeSold - purchasePricePerUnit * lemonadeThatCanBeBought

    if prices[i] < prices[minIndex]:
        minIndex = i
    elif profit >= maxProfit:
        maxProfit = profit
        left = minIndex + 1
        right = i + 1

print(left, right)

Ответ: 21 92