The device consists of several blocks. For each block, the probability of its failure-free operation for a certain time (reliability) is known. If at least one of the device blocks fails, the entire device ceases to work, and therefore the probability of failure-free operation of the entire device P is found as the product of the reliability of its blocks: P device = p1 · p2 · ... · pN.
To increase the reliability of the device, it was decided to backup some units. Block reservation is the connection of one or several of the same blocks in parallel to it. In the event of an accident of the first block, the second one will perform its functions, etc., this replacement will not affect the reliability of all other blocks.
We assume that the probability of failure-free operation of a group of K identical blocks (including the original one) is found as follows: p '= 1 - (1 - p) K, where p is the probability of failure-free operation of one such block. The probability of failure-free operation of the device is then defined as P'device = p'1 · p'2 · ... · p'N.
The cost of each unit and the amount S allocated for the modernization of the entire device are known. It is required to find the maximum probability of device uptime, which we can obtain, provided that the total cost of the added blocks should not exceed S.
The first line of the input contains an integer N - the number of blocks in the device (1 ≤ N ≤ 30). The next N lines contain two numbers separated by a space - the probability of failure-free operation of the next block pi and its cost si (pi is a real number, 0 <pi ≤ 1, si is an integer, 1 ≤ si ≤ 1000). The last line contains an integer S - the amount allocated for the modernization of the device (0 ≤ S ≤ 1000).
Print one number - the probability of the device’s uptime after modernization with an accuracy of at least four digits after the decimal point.
8 freelancers are bidding on average $32 for this job
Hello. How are you. I'm software engineer and algorithm expert. I have many experiences in c, c++, c#, java, python, node.js. I can complete your project successfully. Thanks.
I believe I will be the best person for your work. I am an Algorithm Expert and had solved lots of programming problems in different online judges. So hope you will give me your work.