아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

주사위 던지기

시간 제한1초메모리 제한1024 MB

요약
가중치가 있는 N면체 주사위를 M번 던졌을 때 눈의 합이 1 이상 x 이하일 확률을 각 쿼리마다 구한다.
난이도

보통10점 중 5점

유형
동적 계획법, 확률, 누적 합
정답자
아직 제출이 없습니다

문제

NN면체 주사위가 있고 ii번째 면에는 수 ii가 적혀 있다. ii번째 면이 나올 확률은 A_i∑_i=1NA_i\displaystyle{\frac{A\_i}{\sum\_{i=1}^{N} A\_i}} 이다. 이때 다음과 같은 쿼리에 QQ회 답하라.

  • xx: 주사위를 MM번 던졌을 때 나오는 눈의 합이 11 이상 xx 이하일 확률을 출력하라.

입력

첫 번째 줄에는 정수 N,M,QN, M, Q가 공백으로 구분되어 주어진다.

두 번째 줄에는 A_1,A_2,⋯ ,A_NA\_1, A\_2, \cdots, A\_N 이 공백으로 구분되어 주어진다.

세 번째 줄부터 QQ개의 줄에 걸쳐 쿼리가 주어진다.

입력에 주어지는 모든 수는 정수이다.

출력

QQ개의 줄에 걸쳐 정답을 출력한다. 실제 정답과 출력값의 절대오차 또는 상대오차가 10−110^{-1} 이하이면 정답이다.

제한

  • 1≤N≤1001 \le N \le 100
  • 1≤M,Q≤5×1031 \le M, Q \le 5 \times 10^3
  • 1≤A_i≤1031 \le A\_i \le 10^3
  • 1≤x≤N×M1 \le x \le N \times M

예제3

  1. 예제 1

    입력
    1 50 5
1
10
20
30
40
50
    예상 출력
    0.0000000000
0.0000000000
0.0000000000
0.0000000000
1.0000000000

  2. 예제 2

    입력
    6 2 4
1 3 5 7 9 11
2
4
8
11
    예상 출력
    0.0007716049
0.0200617284
0.3904320988
0.9066358025

  3. 예제 3

    입력
    30 500 10
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
7827
7828
7829
7830
7831
7832
7833
7834
7835
7836
    예상 출력
    0.4879787541
0.4900390086
0.4920995287
0.4941602596
0.4962211463
0.4982821337
0.5003431670
0.5024041912
0.5044651513
0.5065259923