Problem 3812 --Guess the weight

3812: Guess the weight

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $2$ 秒/Second(s) Memory Limit $128$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

"'Guess The Weight', It's turn 2. Well let's play this and see what we can draw'"
**Draws "Innervate"**.
"Wow that's lucky for me! All I need to do is to click "'Greater' then getting a free second draw!"
**Sees another "Innervate"**
"Are you sure you want to uninstall Hearthstone from your computer?" "Yes."

uuzlovetree loves playing Hearthstone, and his favorite class is Druid. In Hearthstone, there's a spell for the Druid class called 'Guess the weight,', as shown below.


uuzlovetree knows the number of cards in the deck and knows the mana cost of each card. He wants to know the probability of getting the second card when he plays the 'Guess the weight' under the optimal guessing strategy.

Formally, assume there are currently m cards in the deck, with a number representing mana cost on each card. Now one randomly shuffles all m cards in the deck(each of the m! possible arrangements of the cards appear with equal probability). When one plays the card 'Guess the weight,' he draws the first card of the deck and chooses one of the following two options:

  • Predict that the next(second) card of the deck has a smaller mana cost than the first card, then reveal the next card of the deck. If your prediction is correct, you draw the second card.

  • Predict that the next(second) card of the deck has a greater mana cost than the first card, then reveal the next card of the deck. If your prediction is correct, you draw the second card.

Caution: If the second card of the deck has equal mana cost with the first card, then no matter which option you choose, you cannot draw the second card of the deck.

Initially, there are n≥2 cards in the deck, with mana costs a1,a2,…,an , respectively. Now q events happen to the deck(How can those events happen? Try Hearthstone to find out for yourself!), with each event in one of the following two forms:
  • Add x cards with mana cost w into the deck.

  • Find out when one applies an optimal strategy, what is the maximum probability that he can draw the second card when he plays 'Guess the weight.'

Input

The first line contains a number T(1≤T≤10), denoting the number of test cases.

The first line of each test case contains two numbers n(2≤n≤2⋅105) and q(1≤q≤2⋅105), denoting the initial size of the deck, and the number of events, respectively.

Then one line follow, containing n integers a1,a2,…,an(1≤ai≤2⋅105), denoting the mana costs of the n initial cards.

Then q lines follow, with each line in one of the two following forms:
  • 1xw, denoting that x cards with mana cost w is added into the deck. (1≤x≤100,1≤w≤2⋅105).

  • 2, denoting a query that asks, when playing 'Guess the weight' with the current deck, what is the maximum probability that one can draw the second card.

It is guaranteed that ∑n≤106 and ∑q≤106 over all test cases.

Output

For each event of the second type of each test case, output a fraction in the form of p/q in one line, denoting the maximum probability that one can draw the second card. It is required that p and q are both integers and gcd(p,q)=1, where gcd(p,q) denotes the greatest common divisor of p and q

Sample Input复制

2
2 5
1 1
2
1 1 2
2
1 1 2
2
2 5
1 2
2
1 1 3
2
1 100 4
2

Sample Output复制

0/1
2/3
2/3
1/1
5/6
201/3502

提示

For the first test case of the sample, initially, the deck consists of two cards with mana cost 1. So no matter which choice one picks, he cannot draw the second card. 

After adding a card with mana cost 2 into the deck, the optimal strategy one can apply is as follows: If the mana cost of the first card drawn is 1, then he predicts that the next card has a greater cost, otherwise he predicts that the next card has a smaller mana cost. One can certify that under this strategy the probability of drawing the second card is 2/3. 

After adding another card with mana cost 2 into the deck, the optimal strategy doesn't change. One can certify that under this strategy the probability of drawing the second card is still 2/3.

推荐代码 查看3812 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战

赛题来源/所属竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛