Description
You have two soups, A and B, each starting with n mL. On every turn, one of the following four serving operations is chosen at random, each with probability 0.25 independent of all previous turns:
- pour 100 mL from type A and 0 mL from type B
從 A 型倒入 100 毫升，從 B 型倒入 0 毫升 - pour 75 mL from type A and 25 mL from type B
從 A 型倒入 75 毫升，從 B 型倒入 25 毫升 - pour 50 mL from type A and 50 mL from type B
從 A 型倒入 50 毫升，從 B 型倒入 50 毫升 - pour 25 mL from type A and 75 mL from type B
從 A 型倒入 25 毫升，從 B 型倒入 75 毫升
Note:
- There is no operation that pours 0 mL from A and 100 mL from B.
不存在從 A 倒出 0 mL，從 B 倒出 100 mL 的操作。 - The amounts from A and B are poured simultaneously during the turn.
在輪流期間，A 和 B 中的量會同時倒入。 - If an operation asks you to pour more than you have left of a soup, pour all that remains of that soup.
如果操作人員要求您倒出比剩餘湯更多的湯，請將剩餘的湯全部倒出。
The process stops immediately after any turn in which one of the soups is used up.
任何一輪用完一碗湯後，該過程都會立即停止。
Return the probability that A is used up before B, plus half the probability that both soups are used up in the same turn. Answers within 10-5 of the actual answer will be accepted.
回傳 A 先於 B 用完的機率，加上兩杯湯在同一輪次用完的機率的一半。答案與實際答案的誤差在 10-5 以內即可接受。
Solution
If we use basic recursion—setting aside Python's maximum recursion depth—even a test case with n = 800 will cause the code to exceed the time limit, , therefore we need the following concepts.
如果我們使用最基礎的遞迴，先不論 python 的遞迴最大深度，光 n = 800 的測資就會讓程式碼 Time Limit Exceeded，因此我們需要以下概念。
Core concept
- cache：This section uses Python's built-in caching tool,
lru_cache. For usage and a detailed introduction, you can refer to this article, which explains why caching is needed and how to uselru_cacheeffectively.
快取：這裡使用 python 內建的快取 lru_cache。使用方式和介紹可以參考這篇，裡面詳細介紹了為何需要快取以及 lru_cache 的使用方法。 - Answers within 10-5 of the actual answer will be accepted. This means that in some case we can just return 1 when n is very big
答案與實際答案的誤差在 10-5 以內即可接受。這代表當 n 很大時，我們可以直接回傳 1。 - Last but not the least, the number of milliliters poured out is a multiple of 25, so we can record 25 as 1, 50 as 2, and so on.
最後，同時也很重要的概念，倒出的毫升數都是 25 的倍數，因此，我們可以將 25 記為 1，50 記為 2，以此類推。
Code
from functools import lru_cache
import math
class Solution:
def soupServings(self, n: int) -> float:
if n >= 4800:
return 1.0
n = math.ceil(n/25)
return self.recursion(n,n)
@lru_cache(None)
def recursion(self, A, B):
if A <= 0 and B <= 0:
return 0.5
elif A<=0:
return 1
elif B<=0:
return 0
return 0.25*(
(self.recursion(A-4,B))+
(self.recursion(A-3,B-1))+
(self.recursion(A-2,B-2))+
(self.recursion(A-1,B-3))
)
If you like this article, give it a like. OwO b
如果這篇對你有幫助請按個讚 ouob。
