Prime Palindrome Flags
Time limit1sMemory limit128 MB
Given n and an optional middle digit c, output the largest n-digit-palindromic number that is prime if any such palindrome is prime, otherwise the largest palindrome.
- Level
Medium6 of 10
- Topics
- Math, Number theory, Brute force, Implementation
- Solved
- No attempts yet
Problem
At the athletics festival of J Middle School, each class plays the following class-versus-class contest. A class chooses boy–girl representative pairs
Every student freely chooses a flag printed with a single digit from to (there are plenty of flags of each digit) and they line up in one horizontal row. The two students of a pair must hold flags showing the same digit, so . The row is ordered as
that is, the girls stand in the reverse order of the boys. In the middle, the homeroom teacher either stands holding a flag whose digit is fixed in advance by the head referee, or is told not to stand at all.
Reading the whole row of digits from left to right as a single integer — it has digits (no teacher) or digits (with the teacher) — the class whose integer is prime wins. If both integers are prime, or both are non-prime, the class with the larger integer wins. A leading zero is not allowed (numbers are written in the usual way), so arrangements such as
or
are forbidden; hence .
Because , the row of digits is a palindrome . You want your class to never lose. Determine the arrangement that guarantees you do not lose.
Against optimal play the never-losing arrangement is unique. If at least one valid palindrome is prime, it is the largest prime palindrome (a prime always beats a non-prime, and among primes only the largest never loses); otherwise every palindrome is non-prime and it is the largest palindrome.
Input
A single line contains the integer and the single-digit integer , separated by one space. If , the teacher does not stand in the middle (the integer then has digits); otherwise the teacher stands with the digit (the integer has digits).
Constraints: and . In most cases .
Output
Print, on a single line, the never-losing arrangement — the row of digits read as one integer.