結果
問題 |
No.155 生放送とBGM
|
ユーザー |
![]() |
提出日時 | 2025-06-12 14:31:48 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,763 bytes |
コンパイル時間 | 177 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 241,408 KB |
最終ジャッジ日時 | 2025-06-12 14:32:05 |
合計ジャッジ時間 | 14,638 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 -- * 14 |
ソースコード
import sys from math import factorial def main(): # 读取输入 input = sys.stdin.read().split() idx = 0 N = int(input[idx]) idx +=1 L = int(input[idx]) idx +=1 S = [] for s in input[idx:idx+N]: mm, ss = map(int, s.split(':')) S.append(mm *60 + ss) idx +=N T = sum(S) L_total = L *60 M_max = L_total // T if T !=0 else 0 # 对于每首歌i计算其被播放的概率 total_expectation = 0.0 for i in range(N): prob_i = 1.0 for k in range(M_max +1): R_total = L_total - k*T if R_total <=0: continue R_play = min(R_total, T) R_needed = R_play -1 # 至少播放1秒 if R_needed <0: continue # 准备其他歌曲的列表 S_without_i = [] for j in range(N): if j != i: S_without_i.append(S[j]) n = len(S_without_i) # 对于每个p,计算sum <= R_needed的概率 # 并计算q_k q_k = 0.0 for p in range(1, N+1): # 计算选择p-1首歌的总和 <= R_needed的概率 m = p-1 if m > n: continue if m ==0: # p=1,sum=0 <= R_needed count = 1 total =1 prob_p = 1.0 else: # 动态规划计算 max_sum = R_needed dp = [ [0]*(max_sum +1) for _ in range(m+1) ] dp[0][0] =1 for s in S_without_i: for current_m in range(m, 0, -1): for current_sum in range(max_sum, -1, -1): if dp[current_m-1][current_sum] >0: if current_sum + s <= max_sum: dp[current_m][current_sum + s] += dp[current_m-1][current_sum] # 计算符合条件的总数 count =0 for s in range(0, R_needed +1): count += dp[m][s] total = factorial(n) // ( factorial(m) * factorial(n -m) ) if total ==0: prob_p =0.0 else: prob_p = count / total # 概率为 prob_p 乘以 1/N q_k += (prob_p / N) prob_i *= (1.0 - q_k) prob_i = 1.0 - prob_i total_expectation += prob_i # 输出结果,保留一位小数 print("{0:.1f}".format(total_expectation)) if __name__ == '__main__': main()