Orange Boy Can You Solve It Out? Ep. 28

思考题 for 300iq

Little Town Hero

If you prefer easier version, please move to Ep 28.5
XGN is playing the new game Little Town Hero(LTH) recently, but he is too stupid to beat the bosses. So he askes Orange Boy to help him.
In each turn, the player has N Dazzits(skills) and the enemy has M Dazzits.
Each Dazzit of yours has two parameters: a_i and c_i - the power of it and cost of it.
Each Dazzit of your enemy's has 1 parameter as well: b_i - the defense of it.
When two Dazzits meet, the enemy Dazzit will break if the power is greater or equal to the defense.
You can choose M different Dazzits to fight the enemy. You can only choose a sequence of Dazzits if the sum of their cost doesn't exceed a given integer pow. After you've done this, the enemy will arrange its Dazzits in totally random order. Then the Dazzits will meet one pair by one pair.
We call the enemy's Dazzits all break if all of its Dazzits are broken. What's the maximum possibility of all break if XGN chooses his Dazzits optimally?

Examples

Input
XGN={{3,1},{4,2},{2,0},{5,3},{6,6}} pow=3
Enemy={4,3}
Output
0.5
Explain
If XGN chooses {{3,1},{4,2}}:
Enemy - {3,4}(all break) {4,3}(break 0)
All break possibility 50%
If XGN chooses {{3,1},{2,0}}
Enemy - {3,4}(break 1) {4,3}(break 0)
All break possibility 0%
If XGN chooses {{4,2},{3,1}}
Enemy - {3,4}(break 1) {4,3}(all break)
All break possibility 50%
If XGN chooses {{4,2},{2,0}}
Enemy - {3,4}(break 1) {4,3}(break 1)
All break possibility 0%
If XGN chooses {{2,0},{5,3}}
Enemy - {3,4}(break 1) {4,3}(break 1)
All break possibility 0%
If XGN chooses {{5,3},{2,0}}
Enemy - {3,4}(break 1) {4,3}(break 0)
All break possibility 0%
So optimally, When XGN chooses {{4,2},{3,1}} or stuff like this, he can get 50% of all break.

Constriants

Subtask 1:n<=5,m<=5
Subtask 2:n<=8,m<=8
Subtask 3:n<=20,m<=20
Subtask 4:n<=100,m<=100, 0<=all integers inputted<=1000000
pic

版权声明:
作者:XGN
链接:https://blog.hellholestudios.top/archives/307
来源:Hell Hole Studios Blog
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>