PipeCuts
SRM 233 · 2005-03-03 · by ValD
SRM 233 · 2005-03-03 · by ValD · Simple Math, Simulation
Problem Statement
Problem Statement
A 100 meter long pipe must be cut in two places. It can only be cut at certain places, where it was originally welded from smaller pipes. If the two cut locations are chosen at random (each potential location has equal probability of being chosen), find the probability of a resulting pipe being longer than L meters.
Create a method named probability that accepts a int[] weldLocations and int L as parameters. It should calculate the probability of one or more resulting pipes being strictly longer than L if the two cut locations are chosen at random from weldLocations. Each element in weldLocations represents the number of meters from the left end of the pipe.
Create a method named probability that accepts a int[] weldLocations and int L as parameters. It should calculate the probability of one or more resulting pipes being strictly longer than L if the two cut locations are chosen at random from weldLocations. Each element in weldLocations represents the number of meters from the left end of the pipe.
Notes
- Your return value must have a relative or absolute error less than 1e-9.
Constraints
- weldLocations will have between 2 and 50 elements, inclusive.
- Each element in weldLocations will be between 1 and 99, inclusive.
- weldLocations will not contain duplicate elements.
- L will be between 1 and 100, inclusive.
Examples
0)
{25, 50, 75}
25
Returns: 1.0
Any random set of cuts results in a pipe being longer than 25 meters.
1)
{25, 50, 75}
50
Returns: 0.0
This time, it is impossible to cut the pipe such that some resulting pipe is longer than 50 meters.
2)
{25, 50, 75}
24
Returns: 1.0
3)
{99, 88, 77, 66, 55, 44, 33, 22, 11}
50
Returns: 0.7222222222222222
4)
{2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98}
34
Returns: 0.9974489795918368
5)
{2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98}
95
Returns: 0.002551020408163265
Probably the smallest return value greater than 0.0
6)
{2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98}
60
Returns: 0.4362244897959184
random test
10)
{2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98}
34
Returns: 0.9974489795918368
probably largest return value less than 1.0
Submissions are judged against all 46 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PipeCuts with a public method double probability(vector<int> weldLocations, int L) · 46 test cases · 2 s / 256 MB per case