Paste: 111

Author: 1111 python Thu, 6 Oct 2022 01:43:30
Plain Text |
```class Solution:

# O(1) intersection of two lines!!!
def trade_math(self, comicBooks, coins, coinsNeeded, coinsOffered) -> int:
def f(sales):
return comicBooks - sales
def g(sales):
return (coins + coinsOffered * sales) / coinsNeeded
m1 = -1
b1 = comicBooks

m2 = coinsOffered / coinsNeeded
b2 = coins / coinsNeeded

x = (b2 - b1) / (m1 - m2)
return min(comicBooks, floor(f(x)), floor(g(x)))

def trade_bsearch(self, comicBooks, coins, coinsNeeded, coinsOffered) -> int:

# helper function
def count(comicBooks, coins, coinsNeeded, coinsOffered, sales) -> int:
# sell comic books
comicBooks -= sales
# get coinsOffered coins for each sold comic book
coins += coinsOffered * sales

# buy as many fiction books as possible.
# you will either be limited:
# 1. by the number of comic books you have, or
# 2. the amount of coins you have
fictionBooks = min(comicBooks, coins // coinsNeeded)
return fictionBooks

# O(log(n))
lo = 0
hi = comicBooks + 1
while lo < hi:
mid = lo + (hi - lo) // 2
m = count(comicBooks, coins, coinsNeeded, coinsOffered, mid)
right = mid
rc = m
while right < comicBooks and rc == m:
rc = count(comicBooks, coins, coinsNeeded, coinsOffered, right)
right += 1
if right == comicBooks or rc < m:
hi = mid
else:
lo = mid+1

return count(comicBooks, coins, coinsNeeded, coinsOffered, lo)

# Times out
def trade(self, comicBooks, coins, coinsNeeded, coinsOffered) -> int:

# helper function
def count(comicBooks, coins, coinsNeeded, coinsOffered, sales) -> int:
# sell comic books
comicBooks -= sales
# get coinsOffered coins for each sold comic book
coins += coinsOffered * sales

# buy as many fiction books as possible.
# you will either be limited:
# 1. by the number of comic books you have, or
# 2. the amount of coins you have
fictionBooks = min(comicBooks, coins // coinsNeeded)
return fictionBooks

best = 0
for n in range(comicBooks+1):
best = max(best, count(comicBooks, coins, coinsNeeded, coinsOffered, n))
return best```