PrimeSubstrings

TCO20 Round 2A · 2020-04-13 · by misof

TCO20 Round 2A · 2020-04-13 · by misof · Brute Force, Graph Theory, Greedy, Math, Search

Show categories

Class Name: PrimeSubstrings

Return Type: String

Method Name: construct

Arg Types: (int, int)

Problem Statement

As you certainly know, a positive integer is called a prime if it has exactly two divisors: 1 and itself. The smallest few primes are 2, 3, 5, 7, 11, 13, 17, and so on.

A string of L digits is called a prime string if it does not contain any leading zeros and represents a prime number. E.g., "7", "47", and "10007" are prime strings but "047" and "42" aren't.

The L-quality of a number is computed by taking its base-10 representation as a string, looking at each (contiguous) substring of length L and counting those that are prime strings. E.g., the 2-quality of the number 470537 is 3 because its substrings "47", "53", and "37" are prime strings. (The substrings "70" and "05" are not prime strings.)

You are given the ints N and L. Construct an N-digit positive integer with the largest possible L-quality. Return a String with its base-10 representation. Any valid answer will be accepted.

Constraints

N will be between 1 and 1000, inclusive.
L will be between 1 and 7, inclusive.
L will be less than or equal to N.

Examples

4
2
Returns: "5317"

7
7
Returns: "1301779"

The returned number is a prime. Any 7-digit prime is a correct answer for this test case.

5
4
Returns: "13079"

1
1
Returns: "3"

2
1
Returns: "33"

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

Coding Area

Language: C++17 · define a public class PrimeSubstrings with a public method string construct(int N, int L) · 63 test cases · 2 s / 256 MB per case