Palindromes in a Progression
National Olympiad — Regional round (2022 season)
Submission name: pal.cpp
Problem summary
For each arithmetic progression A,A+C,A+2C,… up to B inclusive, count its palindromic values. If at least two occur, also find the minimum and maximum gaps between consecutive palindromes. A gap between x<y means y−x−1 integers, not the number of progression terms.
Input
T, followed by T rows A B C.
Output
For each case: 0 or 1 alone if that is the count; otherwise count, minimum gap, maximum gap.
Constraints
0 < T < 10; 0 < A < B < 50,000,000; 0 < C < 50,000,000. Memory limit: 1 MB.
Worked example
An independently prepared example for this explanation.
Input
2 20 23 5 100 299 3
Output
0 7 20 29
Solution analysis
- Testing every progression term may inspect nearly fifty million numbers per case. Instead generate every decimal palindrome up to B by choosing its first half and mirroring it. There are fewer than 15,000 positive palindromes below fifty million.
- Process lengths increasingly and prefixes increasingly within each length. Mirror the whole prefix for even lengths; omit its last digit when mirroring odd lengths. This produces palindromes in increasing order without storing them.
- Keep a generated value only when it lies in [A,B] and (value−A) mod C = 0. Compare each accepted palindrome with the previous accepted value. For 100,299,3, accepted values are 121,151,181,202,232,262,292, giving seven values and gaps ranging from 20 to 29.
Why it works
Every positive decimal palindrome is uniquely determined by its length and first ceil(length/2) digits, so generation is complete and has no duplicates. Increasing prefixes give increasing values, and increasing lengths preserve global order. The membership test is equivalent to belonging to the progression. Consecutive accepted values are thus exactly the neighboring palindromes whose gaps are required.
Watch out. For odd lengths, do not mirror the middle digit twice. Use y−x−1 for gaps, not (y−x)/C−1. Include A when it is palindromic.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
#include <limits>
using namespace std;
int makePalindrome(int prefix, bool oddLength) {
int result = prefix;
// The centre digit of an odd-length palindrome is not mirrored.
int suffix = oddLength ? prefix / 10 : prefix;
while (suffix > 0) {
result = result * 10 + suffix % 10;
suffix /= 10;
}
return result;
}
int main() {
int tests;
cin >> tests;
while (tests-- > 0) {
int a, b, step;
cin >> a >> b >> step;
int count = 0;
int previous = 0;
int minimumGap = numeric_limits<int>::max();
int maximumGap = 0;
int lowerPrefix = 1;
for (int length = 1; length <= 8; length++) {
if (length > 2 && length % 2 == 1) {
lowerPrefix *= 10;
}
for (int prefix = lowerPrefix; prefix < lowerPrefix * 10; prefix++) {
int value = makePalindrome(prefix, length % 2 == 1);
if (value > b) {
break;
}
if (value < a || (value - a) % step != 0) {
continue;
}
if (count > 0) {
int gap = value - previous - 1;
minimumGap = min(minimumGap, gap);
maximumGap = max(maximumGap, gap);
}
previous = value;
count++;
}
}
cout << count;
if (count > 1) {
cout << ' ' << minimumGap << ' ' << maximumGap;
}
cout << '\n';
}
}