## Entries

コメントの投稿

### トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2254-057cbee7
この記事にトラックバックする(FC2ブログユーザー)

### 未使用問題: Ciel and Dice [CIELDICE](この記事を編集する[管理者用])

This is an unused problem for CodeChef March Cook-Off 2012.

Ciel has N dice. The i-th die is a fair Ai-sided die. For a single roll of fair k-sided dice, the number i is shown with probability 1/k for all 1 ≤ ik. (I don't know what 1-sided dice are like, but Ciel may have them!)

Ciel sometimes holds the game with her dice. In the game, Ciel rolls her N dice, and asks the challenger to answer the sum of the numbers which are shown. Of course, the result of the rolling is concealed, but Ciel gives one hint to the challenger. Ciel's hint is the sum S of Xk-th die over all 1 ≤ kM, where Xk are distinct. If the challenger's answer is correct, the challenger get any food menu in the restaurant for free.

Your task is to find the most probable sum for various her hints.

### Input

The first line contains 2 integers N and Q, where Q is the number of hints. Then next line contains N integers A1, A2, ..., AN. Then next Q lines contain M+2 integers M, S, X1, X2, ..., XM.

### Output

For each hint, if the hint must be wrong, print "Ciel lies" without quotes. Otherwise print the most probable sum. If there are multiple answers, print the minimal one.

### Constraints

1 ≤ N ≤ 50000 (5 * 104)
1 ≤ Q ≤ 1500
1 ≤ Ai ≤ 1000000000 (109)
0 ≤ M ≤ 500
0 ≤ S ≤ 1000000000000000000 (1018)
1 ≤ XiN
XiXj (ij)

### Sample Input

2 1
6 6
0 0

### Sample Output

7

### Sample Input

4 2
1 2 3 4
2 3 1 2
2 6 2 3

### Sample Output

7
Ciel lies

### Output details

The first hint of the first sample input is totally useless. Ciel rolls two six-sided dice, the most probable sum is 7 which occurs with probability 6/36 = 1/6, because there are 6 patterns (1, 6), (2, 5), (3, 4), (4, 3), (5, 2) and (6, 1) whose sum is 7.

For the first hint of the second sample input, there are two most probable sums 7, 8.
Sum = 5: There is 1 pattern (1, 2, 1, 1).
Sum = 6: There are 2 patterns (1, 2, 1, 2), (1, 2, 2, 1).
Sum = 7: There are 3 patterns (1, 2, 1, 3), (1, 2, 2, 2), (1, 2, 3, 1).
Sum = 8: There are 3 patterns (1, 2, 1, 4), (1, 2, 2, 3), (1, 2, 3, 2).
Sum = 9: There are 2 patterns (1, 2, 2, 4), (1, 2, 3, 3).
Sum = 10: There is 1 pattern (1, 2, 3, 4).

The second hint of the second sample input is wrong, because the sum of two-sided and three-sided dice cannot be 6.

コメントの投稿

### トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2254-057cbee7
この記事にトラックバックする(FC2ブログユーザー)