Optimal Group Size for Minimizing Reagent Usage in Virus Testing

Little Blue has opened a pet store. Recently, a virus named X virus has been infecting animals. To be on the safe side, Little Blue plans to purchase test kits to check if his pets are infected.

To reduce the number of test kits used, he devised the following strategy. Suppose there are N pets which are partitioned evenly into groups, each containing exactly K pets. For each group, a sample from each pet is mixed into one and a single test kit is used to test the mixture. If the test is negative, all pets in that group are assumed to be virus‐free. However, if the test is positive, then each of the K pets in that group is tested individually using one test kit each. (Note that when K = 1, no secondary test is needed since the single pet’s test already gives the required answer.)

Assume that each pet is infected with probability p independently. For K ≥ 2, the expected number of test kits needed for one group is \[ E(K)=1+K\Bigl(1-(1-p)^K\Bigr), \] so the expected number of test kits used per pet is \[ f(K)=\frac{1}{K}+1-(1-p)^K. \] For K = 1, the cost is simply 1 per pet (since every pet is tested individually).

Your task is to choose an integer K that minimizes the expected test kit usage per pet. If multiple values yield the same minimum expected cost, output the smallest K.

Input Format: A single line containing a floating-point number p (with 0 < p < 1).

Output Format: Output the optimal value of K as an integer.

inputFormat

The input consists of a single line containing a floating-point number p representing the probability that any given pet is infected (0 < p < 1).

outputFormat

Output the optimal integer K that minimizes the expected test kit consumption per pet. In case of multiple optimal solutions, output the smallest one.

sample

0.1

4