URL: http://acm.zju.edu.cn/show_problem.php?pid=1078
Problem:
We say that a number is a palindrom if it is the sane when read from left to right or from right to left. For example, the number 75457 is a palindrom.
Of course, the property depends on the basis in which is number is represented. The number 17 is not a palindrom in base 10, but its representation in base 2 (10001) is a palindrom.
The objective of this problem is to verify if a set of given numbers are palindroms in any basis from 2 to 16.
Input Format:
Several integer numbers comprise the input. Each number 0 < n < 50000 is given in decimal basis in a separate line. The input ends with a zero.
Output Format:
Your program must print the message Number i is palindrom in basis where I is the given number, followed by the basis where the representation of the number is a palindrom. If the number is not a palindrom in any basis between 2 and 16, your program must print the message Number i is not palindrom.
Sample Input:
17
19
0
Sample Output:
Number 17 is palindrom in basis 2 4 16
Number 19 is not a palindrom
My Solution: (C++, GCC)
I am wondering if another way does exit in which I can get the final answer beside mine given below. May be you have an more effective solution. If it is true, simply send it to my email address ichobits@21cn.com, I would be very pleased to having a discussion with you.
#include <iostream>
#include <vector>
// PS: The code is for study purpose only, never submit it as ones own.
// From: http://blog.csdn.net/mskia/
// email: ichobits@21cn.com
int main(void) {
int num;
while (std::cin >> num && num != 0) {
std::vector<int> result;
for (int i = 2; i <= 16; ++i) {
std::vector<int> bn;
int tmp = num;
while (tmp > 0) {
bn.push_back(tmp % i);
tmp /= i;
}
std::vector<int>::const_iterator left;
std::vector<int>::const_iterator right = bn.end();
for (left = bn.begin(), --right; left < right; ++left, --right) {
if (*left != *right) {
break;
}
}
if (left >= right) {
result.push_back(i);
}
}
std::cout << "Number " << num << " is ";
if (result.size() == 0) {
std::cout << "not a palindrom" << std::endl;
} else {
std::cout << "palindrom in basis";
for (std::vector<int>::const_iterator p = result.begin()
; p != result.end(); ++p) {
std::cout << ' ' << *p;
}
std::cout << std::endl;
}
}
return 0;
}