solution

Cho biến ngẫu nhiên rời rạc $X$ với bảng phân phối xác suất gồm $n$ giá trị nguyên $x_i$ và xác suất $P(X=x_i)=p_i/q_i$ (đảm bảo tổng bằng 1 chính xác, các giá trị $x_i$ đôi một phân biệt nhưng KHÔNG nhất thiết cho theo thứ tự tăng dần trong input). Cho $m$ truy vấn, mỗi truy vấn là một số nguyên $t$; với mỗi truy vấn hãy tính $F(t) = P(X \le t) = \sum_{x_i \le t} P(X = x_i)$.

Ví dụ: $X$ đồng đều trên $\{1,2,3,4,5,6\}$ (xúc xắc), với $t=3$ ta có $F(3) = 1/2$.