GCJ2014 Final F

内存限制：256 MiB 时间限制：10 Sec

提交提交记录讨论

在游戏英雄联盟里，你可以玩一种游戏叫 “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

#4343. GCJ2014 Final F

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示