Connection Status:
Competition Arena > PrettyPrimes

PrettyPrimes

SRM 813 · 2021-09-15 · by misof

SRM 813 · 2021-09-15 · by misof · Brute Force, Math
Class Name: PrettyPrimes
Return Type: int
Method Name: solve
Arg Types: (int, int)
Problem Statement

Problem Statement

Time limit is 4 seconds.


All numbers in this problem are positive integers in base 10 with no leading zeros.

We are interested in occurrences of a number in another number. This happens whenever the string of digits that represents the first number occurs in the string of digits that represents the second number (as a contiguous subsequence).

For example:

  • There are two occurrences of 47 in 147000470.
  • There is one occurrence of 47 in 47.
  • There are no occurrences of 47 in 3.
  • There are no occurrences of 42 in 4002.
  • There are three occurrences of 33 in 133337. (Note that there are three occurrences, not just two. Occurrences may overlap.)

You are given an int pattern with at most two digits and an int D.

Let S be the set of all D-digit prime numbers with the maximum number of occurrences of the given pattern.

Return sum(S) modulo 1,000,000,007.

Constraints

  • pattern will be between 1 and 99, inclusive.
  • D will be between 1 and 12, inclusive.
Examples
0)
17
5
Returns: 125285

Clearly we can get at most two occurrences of 17 in a 5-digit number. There are five 5-digit primes with two occurrences of the number 17. These are 11717, 17117, 17317, 17417, and 61717. The answer is their sum.

1)
42
5
Returns: 12818536

There are no primes with two occurrences of 42. There are 258 primes with one occurrence of 42. The smallest among them is 10427, the largest one is 98429. The answer is their sum.

2)
44
10
Returns: 444444419

The only 10-digit number with 9 occurrences of 44 is clearly not a prime. The only 10-digit number with 8 occurrences of 44 is 4,444,444,447. The answer is this number modulo 10^9 + 7.

3)
14
1
Returns: 17

The 1-digit primes with the most occurrences of the number 14 are the primes 2, 3, 5, and 7. Each of them contains zero occurrences of the number 14.

4)
6
1
Returns: 17

Submissions are judged against all 115 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PrettyPrimes with a public method int solve(int pattern, int D) · 115 test cases · 2 s / 256 MB per case

Submitting as anonymous