← All solutions

Solved by 66 teams.

First solved after 71 minutes.

Shortest judge solution: 1675 bytes.

Let’s first consider how to solve the problem for n = 1. For each digit from 0 to 8, we’ll use dynamic programming to determine the maximum number of times it can appear. We will run a separate DP for each possible number of digits, which will proceed left-to-right in the number, and will track the following state:

• the current value modulo p;
• whether the value so far is a prefix of m (relevant only if the number of digits is the same as the length of m).

If n > 1 it is a little more tricky. It’s well-known that “large” scores can be achieved if and only if they are a multiple of the GCD of the p values. The threshold for being “large” is known as the Frobenius number, and while determining bounds is still an open area of research, it will not exceed the square of the largest p. Thus, we can separate the search into values less than 10⁶ and those that are at least 10⁶. The former can be treated as an integer knapsack problem, and the latter can be handled as for n = 1.