TheLotteryBothDivs
SRM 502 · 2010-11-01 · by rng_58
SRM 502 · 2010-11-01 · by rng_58 · Math, String Manipulation
Problem Statement
Problem Statement
Farmer John wants to buy a lottery ticket. Before he buys a ticket, Fox Brus decided to calculate the probability that John will get a prize.
There are 1,000,000,000 types of lottery tickets. They are numbered "000000000" to "999999999" (they may have leading zeroes). Each type of ticket has an equal probability of being bought by John. You are given aString[] goodSuffixes. If the number written on John's ticket has at least one element of goodSuffixes as a suffix, he will get a prize.
Return the probability that John will get a prize.
There are 1,000,000,000 types of lottery tickets. They are numbered "000000000" to "999999999" (they may have leading zeroes). Each type of ticket has an equal probability of being bought by John. You are given a
Return the probability that John will get a prize.
Notes
- The returned value must have an absolute or relative error less than 1e-9.
- A suffix of a string is obtained by removing zero or more contiguous characters from the beginning of the string.
Constraints
- goodSuffixes will contain between 1 and 50 elements, inclusive.
- Each element of goodSuffixes will contain between 1 and 9 characters, inclusive.
- Each character in goodSuffixes will be a digit ('0'-'9').
Examples
0)
{"4"}
Returns: 0.1
John will get a prize if the last digit is '4'. It happens with probability 0.1.
1)
{"4", "7"}
Returns: 0.2
2)
{"47", "47"}
Returns: 0.01
goodSuffixes may contain duplicate elements.
3)
{"47", "58", "4747", "502"}
Returns: 0.021
4)
{"000000000"}
Returns: 1.0E-9
Submissions are judged against all 112 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TheLotteryBothDivs with a public method double find(vector<string> goodSuffixes) · 112 test cases · 2 s / 256 MB per case