Problem Statement
We have N = 2*A + B pieces of string. Each end of each piece has a color, as follows:
- A pieces of rope have both ends red.
- A pieces of rope have both ends green.
- B pieces of rope have one end red and one end green.
All strings are jumbled up. We have found all 2*N ends of our strings. Note that N of them are red and N are green. We are going to create N red-green pairs at random, with each of the N! possible pairings being equally likely. Then, we will make N knots, each tying one pair of ends together.
Clearly, the above process will produce some disjoint string rings. Calculate and return the expected number of those rings.
Definition
- Class:
- StringRings
- Method:
- expectedRings
- Parameters:
- int, int
- Returns:
- double
- Method signature:
- double expectedRings(int A, int B)
- (be sure your method is public)
Notes
- The return value must have an absolute or a relative error up to 1e-9.
Constraints
- A will be between 0 and 10^6, inclusive.
- B will be between 0 and 10^6, inclusive.
Examples
0
1
Returns: 1.0
We have one piece of string. One of its ends is green and the other is red. We will pair up the two ends and tie them together, thereby forming a single string ring.
1
0
Returns: 1.0
We have one red-red piece and one green-green piece. There are two possible ways how to pair up their ends, but both of them lead to exactly one string ring containing both strings.
1
2
Returns: 1.5833333333333333
There are four pieces of strings. Together, they have four red and four green ends. There are 4! = 24 ways to create four disjoint pairs of ends, each containing a red and a green end. Out of those 24 ways, in 12 of them we will obtain a single string ring, in 10 of them we will obtain two, and two ways produce three string rings each. Thus, the expected number of string rings is (12*1 + 10*2 + 2*3) / 24.
0
0
Returns: 0.0
A boring special case: no strings means no rings.
2
3
Returns: 1.8428571428571427
2
0
Returns: 1.3333333333333333
1
1
Returns: 1.3333333333333333
0
2
Returns: 1.5
1000000
1000000
Returns: 8.294975316767665
1000000
0
Returns: 7.889510291992833
1000000
47
Returns: 7.8895337917108375
0
1000000
Returns: 14.392726722865772
47
1000000
Returns: 12.17383879753566
2304
15624
Returns: 6.332343823919247
442221
453
Returns: 7.482049586994206
4431
8579
Returns: 5.8569688313763555
8
502
Returns: 5.4692272761280005
133466
1899
Returns: 6.889645006213854
188
112601
Returns: 9.304002205515259
24315
3
Returns: 6.031241062242502
3448
182447
Returns: 8.36707861904099
137
26
Returns: 3.532242987377249
13
463249
Returns: 12.033225975839045
98675
11
Returns: 6.731604200119429
1471
39986
Returns: 7.308880259022453
13976
756
Returns: 5.780990044146261
199646
2212
Returns: 7.089430061897259
53228
469488
Returns: 8.111199790226687
369
643758
Returns: 10.70875698044594
112
49357
Returns: 8.738502634844007
680737
16881
Returns: 7.70954348818475
37
6
Returns: 2.8646861670346833
127993
14181
Returns: 6.915537868269625
3
1000000
Returns: 13.476066056178107
1069
389556
Returns: 9.679372028173283
108
11206
Returns: 7.288571350045073
62
80
Returns: 3.54158819279138
10
442527
Returns: 12.11303462021947
116963
12
Returns: 6.8166127720854295
16398
14
Returns: 5.834639124400042
6
1
Returns: 1.955133755133755
2
63
Returns: 4.039352407376227
127
124989
Returns: 9.602563490002465