GCJ2014 Final F
时间限制：10s 空间限制：256MB
题目描述
在游戏英雄联盟里，你可以玩一种游戏叫 “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