Problem Statement |
| | A prime number is a number that is divisible by only itself and one. In this problem we will say that a prime number p is x-isolated at distance (a,b) if there there are at most x primes (including p) between (p-a) and (p+b), inclusive. You are given the numbers a, b and x. Your task is to find the smallest prime p
between a+2 and 263-1-b, inclusive, such that p is x-isolated at distance (a,b),
and return a String which contains its decimal notation.
For example, for x=2 and a=b=5, the smallest possible value is 23, as the only primes in [18,28] are 19 and 23.
Your score for each individual test case will simply be the value you return (or 0 if your value does not meet the criteria above).
Invalid returns (a string which is not a prime number, a number outside of the bounds or a number which is not sufficiently isolated)
result in a score of 0 and don't contribute to the overall score.
Assuming your return is valid for a test case, it's contribution to your overall score will be BEST/YOU, where BEST is the best (lowest) value found for this test case by any competitors and YOU is your value. The total score will simply be the sum of these ratios over all test cases.
|
| |
Definition |
| | | Class: | IsolatedPrimes | | Method: | findPrime | | Parameters: | int, int, int | | Returns: | String | | Method signature: | String findPrime(int x, int a, int b) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | java.math.BigInteger.isProbablePrime(200) is used for primality testing. |
| - | If a test case has no valid returns, everyone will receive a 0 for that test. |
| |
Constraints |
| - | x is chosen uniformly at random in [1,500] |
| - | a and b are chosen uniformly at random in [4x,25x] |
| - | The size of your code is limited to 100K (102400 bytes) |
| - | The time limit is 20 seconds. The memory limit is 1024M. |
| |
Examples |
| 0) | |
| | | Returns: "x = 2
a = 5
b = 5
" | |
|
| 1) | |
| | | Returns: "x = 410
a = 5954
b = 1916
" | |
|
| 2) | |
| | | Returns: "x = 400
a = 4067
b = 9810
" | |
|
| 3) | |
| | | Returns: "x = 87
a = 922
b = 630
" | |
|
| 4) | |
| | | Returns: "x = 76
a = 1127
b = 546
" | |
|
| 5) | |
| | | Returns: "x = 312
a = 7649
b = 4383
" | |
|
| 6) | |
| | | Returns: "x = 449
a = 3232
b = 8777
" | |
|
| 7) | |
| | | Returns: "x = 489
a = 11822
b = 8438
" | |
|
| 8) | |
| | | Returns: "x = 126
a = 2399
b = 1183
" | |
|
| 9) | |
| | | Returns: "x = 500
a = 12500
b = 12500
" | |
|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2020, TopCoder, Inc. All rights reserved.