Codeforces Round #741 Scenes From a Memory Solution (Java/C++)

Solution:

First of all, it is obvious that if the 1, 4, 6, 8, 9 appear in the original number. All other numbers can be deleted, and only one digit is left.

So we are left with 2, 3, 5, 7. We can easily find that if a prime number is to be constructed, it must have the following properties:
1. Each number can only appear once at most, otherwise it must be a number divisible by 11.
2. 2 and 5 must not appear at the same time, otherwise 25 and 52 are not prime numbers.
3. 2 and 7 cannot appear at the same time, otherwise they must be divisible by 3.
4. 5 and 7 cannot appear at the same time, otherwise they must be divisible by 3.

We found that if these numbers are used to form two digits, and the two digits are prime numbers, then it must be one of: 23, 53, 37, 73.

Then we consider the three-digit situation. It is not difficult to find that the three digits formed must not be prime numbers, or the digits can be further deleted.

In summary, we only need to enumerate all the numbers within three digits that can be formed in turn.

Code:

Java

Submission #127463690 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #127463771 - Codeforces
Codeforces. Programming competitions and contests, programming community
Show Comments
DigitalOcean Referral Badge