8343: BZOJ4343：GCJ2014 Final F

在游戏英雄联盟里，你可以玩一种游戏叫 “ARAM”，这是 “All Ran- dom,AllMid” 的缩写。这个题目和它有点相似，但并不需要你了解英雄联 盟。每次你开始玩 “ARAM”，你会被随机分配为一种 “champion”，总共 n 种。有一些 “champion” 你能更加轻松地取胜。所以如果你不幸分到 一个概率低的，你会想得到一个不同的 “champion”。幸运的是，游戏包 含”Reroll” 功能。F“Reroll” 会重新将你随机分配为一种 “champion”，但 你不能任意时刻都 “Reroll”。具体地说它需要耗费钱。在你玩 “ARAM” 游 戏前，你一开始就有 R 的 “RD”（“Rerolldollars”）。你能 “Reroll” 当且仅 当你有至少 1RD。进行一次 “Reroll” 操作会花费 1RD。每次游戏后，你都 会得到 1G 的 RD（G 是个整数），但你不能得到超过 R 的 RD。如果你有 R 的 RD，再玩一盘，你仍然是 R 的 RD。 如果你有至少 1RD，并且你选择 “Reroll”，你会花费 1RD 并重新随机 分配成 n 个 “champion” 中的一个。你有可能会和之前分配给同一个。如 果你不喜欢这次 “Reroll” 所得到的，并且你还有至少 1RD，你可以再进行 一次 “Reroll”。只要你有至少 1RD，你就能继续 “Reroll”。 举个例子，如果 R =2;G =2，并且你使用了一次 reroll 在你第一次游 戏中，第一次游戏结束后你会有 1.5RD。如果你又玩了一个游戏，没有用 reroll，你会有 2.0RD。如果你再玩一个游戏不用 reroll，你仍然是 2.0RD （因为任意时刻不允许超过 R）。如果你使用了两次 reroll 在你下一次游戏 中，你就会变成 0.5RD。 你有一张表，记录你用第 i 个 “champion” 的胜率。你会玩 10100 盘游 戏并选择一种最优秀的策略。求期望的取胜次数比例。

输入格式

第一行一个整数 T 表示数据组数。接下来 T; 1 ≤ T ≤ 100 组数据，每 组数据第一行输入三个整数 n;R;G; 1 ≤ n ≤ 1000; 1 ≤ R;G ≤ 20。接下来 一行 n 个实数 pi; 0:0 ≤ pi ≤ 1:0，表示获胜概率。pi 会是一个四位小数。

输出格式

对于每组数据，输出一个实数表示期望的取胜次数所占比例。如果你 的答案与标准答案绝对误差或相对误差不超过 10^-10，你就会被判定为正 确。

样例输入

100
8 3 1
0.6504 0.0470 0.7700 0.2624 0.0064 0.8346 0.9107 0.3092 
2 1 1
0.2018 0.3000 
1 1 2
0.1662 
3 2 1
0.6011 0.3316 0.0532 
8 2 2
0.1357 0.5523 0.0232 0.7670 0.1968 0.7247 0.0075 0.5826 
5 1 1
0.6026 0.6445 0.9232 0.9132 0.4979 
2 2 2
0.0010 0.1262 
9 3 2
0.5325 0.0792 0.0251 0.5327 0.0256 0.2833 0.4185 0.0214 0.2198 
3 2 1
0.9008 0.6494 0.6352 
2 2 1
0.8263 0.0048 
5 3 1
0.8824 0.6101 0.1815 0.1343 0.0362 
7 3 1
0.6737 0.8726 0.5792 0.2323 0.2035 0.9388 0.0787 
8 1 2
0.5812 0.1177 0.7661 0.3209 0.5278 0.2019 0.5466 0.0177 
10 3 2
0.2880 0.0650 0.2284 0.6229 0.7026 0.4968 0.1029 0.4383 0.1418 0.1332 
1 3 1
0.5174 
9 2 2
0.1740 0.2498 0.9701 0.4841 0.6857 0.4836 0.1282 0.7013 0.1698 
7 3 1
0.6231 0.9057 0.8451 0.1402 0.6808 0.1204 0.4083 
2 2 1
0.2841 0.9272 
8 2 2
0.7120 0.8636 0.1858 0.6429 0.9256 0.1249 0.0787 0.5636 
4 3 1
0.6901 0.5694 0.9830 0.1927 
3 3 1
0.5945 0.1771 0.5384 
1 3 1
0.7238 
4 2 2
0.9717 0.4176 0.4547 0.0162 
7 1 1
0.3602 0.7914 0.0847 0.7428 0.7919 0.8946 0.3858 
6 2 2
0.2482 0.8074 0.9351 0.1287 0.3498 0.9388 
4 3 1
0.8753 0.5020 0.7534 0.4821 
8 2 1
0.4641 0.0337 0.9947 0.4182 0.0885 0.1181 0.1681 0.4586 
3 2 1
0.2876 0.9992 0.5965 
8 1 2
0.0187 0.8814 0.2140 0.0485 0.3503 0.3099 0.2500 0.1350 
1 3 1
0.2219 
7 2 2
0.5541 0.6915 0.4908 0.3988 0.0191 0.4865 0.9539 
8 3 1
0.6983 0.5412 0.8022 0.4659 0.1153 0.6005 0.1162 0.9018 
8 3 1
0.7051 0.1617 0.0484 0.5656 0.5554 0.4224 0.0998 0.5084 
5 1 2
0.7060 0.6392 0.2017 0.0574 0.3968 
10 1 1
0.0120 0.3729 0.0196 0.8320 0.6365 0.6829 0.8436 0.5067 0.2027 0.9101 
3 1 2
0.6198 0.4564 0.9158 
6 1 1
0.7703 0.2479 0.9260 0.5363 0.0552 0.8117 
3 2 1
0.4745 0.6740 0.6633 
4 3 2
0.2621 0.7052 0.7500 0.1113 
9 3 1
0.5996 0.6731 0.6803 0.6891 0.8987 0.2175 0.3879 0.1192 0.5852 
1 2 2
0.9276 
4 2 2
0.1855 0.1786 0.6104 0.1227 
8 3 2
0.7155 0.3435 0.1177 0.4573 0.4554 0.7384 0.9665 0.1331 
4 1 1
0.7851 0.9351 0.3632 0.9061 
10 3 1
0.9419 0.3477 0.2717 0.3542 0.0252 0.7895 0.0979 0.1008 0.5795 0.9095 
6 2 2
0.1320 0.0354 0.2316 0.9712 0.4766 0.3007 
1 2 2
0.5745 
6 2 2
0.2360 0.2990 0.6549 0.8539 0.9672 0.5803 
9 3 2
0.4213 0.5481 0.3422 0.2604 0.4929 0.0172 0.6961 0.6854 0.8279 
10 2 1
0.2584 0.9000 0.6259 0.8990 0.1568 0.9068 0.0358 0.3019 0.2345 0.1926 
6 1 1
0.3105 0.4419 0.0846 0.9034 0.4417 0.5420 
10 3 1
0.1280 0.5114 0.6378 0.2062 0.9234 0.0715 0.7964 0.0357 0.7118 0.1040 
8 1 1
0.2694 0.6901 0.3190 0.0572 0.7133 0.8105 0.8001 0.8530 
2 1 1
0.2054 0.8972 
8 1 2
0.8580 0.4247 0.8619 0.5039 0.9409 0.1907 0.2769 0.0189 
2 2 2
0.5674 0.2237 
9 3 1
0.0488 0.5231 0.2921 0.2266 0.7823 0.9366 0.0157 0.8537 0.3460 
6 1 1
0.3258 0.3748 0.4597 0.5865 0.7450 0.2188 
3 2 2
0.6324 0.0524 0.0554 
4 3 1
0.0073 0.9551 0.3479 0.4780 
8 3 2
0.7219 0.0169 0.1860 0.2305 0.5946 0.1243 0.1333 0.5815 
10 1 1
0.9085 0.3833 0.5457 0.2122 0.9221 0.9616 0.2923 0.4048 0.8228 0.0491 
1 1 1
0.5001 
7 1 2
0.3410 0.4201 0.3483 0.9545 0.3881 0.9079 0.6459 
2 1 1
0.2538 0.2728 
10 3 2
0.2739 0.7974 0.7999 0.9854 0.1766 0.2510 0.2172 0.7115 0.4476 0.0288 
8 1 1
0.0714 0.9212 0.6052 0.3531 0.0599 0.8437 0.3195 0.5608 
10 2 1
0.7915 0.0909 0.7699 0.4180 0.6608 0.1532 0.7274 0.1116 0.5581 0.0897 
10 2 1
0.2564 0.5860 0.0171 0.2949 0.6170 0.0431 0.4381 0.2562 0.1490 0.4874 
10 2 2
0.0551 0.6022 0.4829 0.6519 0.0912 0.7524 0.9113 0.3649 0.9898 0.7421 
2 1 2
0.0062 0.1206 
3 1 2
0.6764 0.5323 0.0010 
7 3 1
0.9597 0.0577 0.3853 0.9342 0.9937 0.5385 0.1655 
9 3 1
0.1617 0.0819 0.8652 0.5926 0.9043 0.7152 0.7226 0.8545 0.8939 
5 3 2
0.2532 0.4326 0.4685 0.3518 0.0797 
6 1 1
0.7041 0.0720 0.0679 0.4770 0.8848 0.2357 
3 1 2
0.0322 0.9758 0.8069 
10 1 1
0.1525 0.1762 0.6375 0.1946 0.7249 0.4126 0.2248 0.3267 0.4039 0.5203 
2 1 1
0.7979 0.7691 
8 3 1
0.7597 0.4169 0.0921 0.0026 0.1935 0.8507 0.0482 0.0764 
10 3 2
0.9796 0.1237 0.3296 0.0750 0.0649 0.8732 0.5537 0.7291 0.6985 0.1613 
10 3 1
0.7562 0.6721 0.8427 0.3467 0.2180 0.5641 0.2309 0.4028 0.9737 0.2531 
1 1 1
0.1130 
6 1 1
0.7292 0.2143 0.8740 0.2779 0.7543 0.7061 
9 1 2
0.3077 0.2487 0.6833 0.3617 0.2657 0.5459 0.1064 0.7667 0.9759 
4 2 2
0.8199 0.9802 0.8034 0.9156 
3 1 2
0.0327 0.0657 0.5684 
2 1 1
0.3123 0.2502 
3 1 2
0.4381 0.1963 0.1368 
8 2 1
0.7937 0.4984 0.5959 0.5610 0.7230 0.8738 0.7884 0.6438 
4 3 1
0.2176 0.3486 0.0146 0.1577 
3 2 1
0.6631 0.5010 0.0972 
6 1 1
0.1872 0.2201 0.7144 0.8300 0.9577 0.4927 
3 3 2
0.0793 0.7391 0.3307 
8 3 1
0.2127 0.6258 0.6027 0.0028 0.6175 0.4371 0.5984 0.7196 
8 1 1
0.8243 0.6831 0.0251 0.9260 0.2698 0.5982 0.0978 0.9824 
10 1 2
0.3309 0.3921 0.0993 0.1399 0.3651 0.0196 0.9966 0.0263 0.2835 0.2551 
5 2 2
0.3981 0.2187 0.2113 0.5321 0.6679 
7 2 1
0.3827 0.8387 0.9843 0.6756 0.6789 0.9666 0.0085 
10 1 2
0.5036 0.1048 0.9888 0.1449 0.3840 0.3641 0.3377 0.4010 0.6550 0.1173 

样例输出

Case #1: 0.71202812499999990000
Case #2: 0.27544999999999997000
Case #3: 0.16619999999999999000
Case #4: 0.46560833333333329000
Case #5: 0.50180067567567554000
Case #6: 0.79704799999999998000
Case #7: 0.09142222222222222400
Case #8: 0.33076863412788493000
Case #9: 0.80232380952380944000
Case #10: 0.68938333333333335000
Case #11: 0.58950461538461529000
Case #12: 0.73452682215743437000
Case #13: 0.45932045454545462000
Case #14: 0.41761186528497402000
Case #15: 0.51739999999999997000
Case #16: 0.56244473192468014000
Case #17: 0.73258746355685123000
Case #18: 0.82001666666666662000
Case #19: 0.65635911100196453000
Case #20: 0.79299374999999994000
Case #21: 0.55826296296296296000
Case #22: 0.72380000000000000000
Case #23: 0.59824714285714287000
Case #24: 0.70814489795918356000
Case #25: 0.71529761904761890000
Case #26: 0.77406249999999988000
Case #27: 0.50399230769230774000
Case #28: 0.80566666666666653000
Case #29: 0.33328333333333332000
Case #30: 0.22189999999999999000
Case #31: 0.61359330171902782000
Case #32: 0.70779602272727271000
Case #33: 0.54183749999999997000
Case #34: 0.47755428571428571000
Case #35: 0.64193999999999996000
Case #36: 0.71589999999999998000
Case #37: 0.69694999999999996000
Case #38: 0.65940476190476183000
Case #39: 0.59357307692307693000
Case #40: 0.68803093681917216000
Case #41: 0.92759999999999998000
Case #42: 0.33372647058823529000
Case #43: 0.62217250430292592000
Case #44: 0.84341874999999999000
Case #45: 0.66340759999999988000
Case #46: 0.46306916666666664000
Case #47: 0.57450000000000001000
Case #48: 0.71502196969696974000
Case #49: 0.58790726977618313000
Case #50: 0.65209368421052627000
Case #51: 0.54357777777777772000
Case #52: 0.64268363636363635000
Case #53: 0.69490312499999995000
Case #54: 0.72424999999999995000
Case #55: 0.60421136363636352000
Case #56: 0.47192777777777778000
Case #57: 0.66965144032921808000
Case #58: 0.52441666666666664000
Case #59: 0.34054414414414408000
Case #60: 0.66660312499999996000
Case #61: 0.42887420494699652000
Case #62: 0.69164400000000004000
Case #63: 0.50009999999999999000
Case #64: 0.64421428571428574000
Case #65: 0.26804999999999995000
Case #66: 0.60846400184842875000
Case #67: 0.59978749999999992000
Case #68: 0.61771125000000005000
Case #69: 0.43382795454545447000
Case #70: 0.69454901408450698000
Case #71: 0.08246666666666666000
Case #72: 0.50379166666666653000
Case #73: 0.83334810495626821000
Case #74: 0.82598856400259901000
Case #75: 0.38784407643312097000
Case #76: 0.54777500000000001000
Case #77: 0.74815833333333326000
Case #78: 0.45861999999999997000
Case #79: 0.79070000000000007000
Case #80: 0.50977989864864859000
Case #81: 0.61701794936708865000
Case #82: 0.70654899999999987000
Case #83: 0.11300000000000000000
Case #84: 0.70814444444444435000
Case #85: 0.55052539682539670000
Case #86: 0.91005277777777771000
Case #87: 0.29149333333333333000
Case #88: 0.29677500000000001000
Case #89: 0.29327333333333333000
Case #90: 0.75806666666666656000
Case #91: 0.26330312499999997000
Case #92: 0.56190833333333323000
Case #93: 0.70052499999999995000
Case #94: 0.50845628415300537000
Case #95: 0.61817067307692308000
Case #96: 0.70831406250000006000
Case #97: 0.35357285714285719000
Case #98: 0.48090928571428571000
Case #99: 0.83040930232558130000
Case #100: 0.46422461538461535000

提示

没有写明提示

题目来源

鸣谢Claris提供SPJ