IOISureWinner
SRM 808 · 2021-06-23 · by misof
Problem Statement
The International Olympiad in Informatics (IOI) is currently in progress. To honor this competition, our problems for this round have IOI-flavored stories.
Topher Coder is leading the IOI after day 1. On day 2, he needs at least scoreNeeded points to be guaranteed the first place.
Day 2 contains N subtasks Topher may possibly solve. Each subtask offers some number of points. Additionally, for each subtask we are given the probability that Topher will successfully solve the subtask (and thus get the points). The tasks are such that each subtask is solved independently, so we will assume that all the random events "Topher solves subtask i" are mutually independent.
You are given the information about subtasks in the
Calculate and return the probability that Topher's day 2 score will be greater than or equal to scoreNeeded points.
Notes
- Your return value must have an absolute error of at most 1e-9 to be accepted. In languages where you have the choice, we recommend the use of double-precision floating point variables ("double"s) when calculating the result.
Constraints
- scoreNeeded will be between 1 and 300, inclusive.
- N (the length of subtasks) will be between 1 and 50, inclusive.
- Each element of subtasks will be positive.
- sum(subtasks) will not exceed 300.
- p will contain exactly N elements.
- Each element of p will be between 1 and 100, inclusive.
31
{10, 10, 10, 10}
{50, 50, 50, 50}
Returns: 0.0625
Topher needs at least 31 points. There are four subtasks. Each gives 10 points and Topher will solve it with probability 50 percent. He needs to solve all four, which will happen with probability (1/2)^4 = 1 / 16.
40
{10, 10, 10, 10}
{50, 50, 50, 50}
Returns: 0.0625
The same situation as in the previous example. Getting exactly 40 points is still enough.
101
{10, 20, 30, 40}
{99, 98, 97, 96}
Returns: 0.0
There is no way to get 101 or more points.
100
{20, 30, 100, 50}
{12, 34, 56, 78}
Returns: 0.57400256
One option for Topher is to solve the subtask worth 100 points (and any other subtasks along with it). If he doesn't solve that subtask, he must solve all three remaining subtasks. The first option has probability 0.56, the second option has probability 0.12 * 0.34 * (1 - 0.56) * 0.78.
20
{10, 11, 12, 13, 14}
{10, 10, 10, 10, 10}
Returns: 0.08146000000000005
Any two (or more) of these five subtasks are enough.
Submissions are judged against all 61 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class IOISureWinner with a public method double probability(int scoreNeeded, vector<int> subtasks, vector<int> p) · 61 test cases · 2 s / 256 MB per case