[백준] 1344번: 축구

https://www.acmicpc.net/problem/1344

initial

referred to

https://sdev.tistory.com/562

So this is maths question and i managed to derive the pattern but not able to implement it. Turns out it is actually binomial probability from hl maths lol but i forgot about it. Out of 18 intervals, we choose the primes (nCk) and just implement the formula for team a and b. So that prob represents probability of winning k prime number games out of 18 intervals for that team. We increment that to the total_win_prob a and total_win_prob b. But we need to minus the intersection (rmb subsets?) cuz we require only 1 team to have prime number wins, not both.

solution

import math

# Input winning rates and convert to probabilities
win_a = int(input()) / 100
win_b = int(input()) / 100
lose_a = 1 - win_a
lose_b = 1 - win_b

prime = [2, 3, 5, 7, 11, 13, 17]

fact = []
for i in prime:
    fact.append(math.factorial(18) // (math.factorial(i) * math.factorial(18 - i)))

a, b = 0, 0

for i in range(7):
    a += fact[i] * pow(win_a, prime[i]) * pow(lose_a, 18 - prime[i])
    b += fact[i] * pow(win_b, prime[i]) * pow(lose_b, 18 - prime[i])

# Calculate the total probability and round to 10^-6
result = round(a + b - a * b, 10)
print(result)

complexity

n! time cuz of factorial? wait but it is factorial 18 and 18 is constant so isnt it just time 1 and space 1?

yes

Let's analyze the time and space complexity of the provided Python code.

Time Complexity:

• Calculating the factorials for each prime number up to 18 requires a loop over the prime numbers, resulting in a time complexity of O(7) or O(1).
• The subsequent loop iterates over the prime numbers and performs arithmetic operations using the pow() function and basic arithmetic operations. These operations have a constant time complexity.
• Therefore, the overall time complexity is O(1).

Space Complexity:

• The space complexity primarily depends on the storage of the fact list, which stores precomputed factorials. Since the list contains a fixed number of elements (7 in this case), the space complexity is O(1).
• Other variables (win_a, win_b, lose_a, lose_b, a, b, prime, result) and intermediate values occupy constant space.
• Therefore, the overall space complexity is O(1).

In summary, both the time and space complexities of the provided code are constant, indicating that the code is efficient and does not depend on the input size.