Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1880
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1880
Renzo and the Palindromic Decoration
By Marcio T. I. Oshiro, Universidade de São Paulo 
Brazil
Timelimit: 2
At the ruins of Wat Phra Si Sanphet (วัดพระศรีสรรเพชญ์), one can find famous inscriptions that have only recently been decoded. Several numbers written using Thai numerals decorate these ruins.
A couple of years ago, the famous Peruvian researcher Renzo "elintrépido" Morales found out that most numbers found at the ruins are palindromic, that is, they represent the same number when read backwards. For instance, 171 is palindromic, whereas 17 is not.
Intrigued by the existence of non palidromic numbers as decorations in the ruins, Renzo found out that, while these numbers are not palindromic when represented in base 10 (which is the base used in the Thai numeral system), they are palindromic when represented in another base. For b > 0, the base-b representation of a number N is the sequence amam-1...a1a0 so that 0 ≤ ai ≤ b-1 for each 0 ≤ i ≤ m, am > 0, and ambm+ am-1bm-1+ ... + a1b + a0 = N. For the previous example, the base-2 representation of 17 is 10001, which is palindromic.
To validate his discovery, Renzo wants you to write a program that takes a number represented in base 10 and checks in which bases from 2 to 16 such number has a palindromic representation.
Input
The input contains several instances. The first line of the input has an integer T corresponding to the number of instances.
Each instance has a single line with an integer N (0 ≤ N < 231) written in base 10.
Output
For each instance, print in a single line a space-separated list of integers, from 2 to 16 and in increasing order, of the bases for which the representation of N is palindromic. If N does not have a palindromic representation for any of the bases from 2 to 16, print -1.
| Input Sample | Output Sample |
|
2 17 2570 |
2 4 16 4 16 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
int palindrome(int n, int b)
{
char ret[35];
int tam = 0;
int i;
i = 0;
while (n)
{
int resto = n % b;
if (resto < = 9)
ret[i++] = resto + '0';
else ret[i++] = resto - 10 + 'a';
n /= b;
++tam;
}
ret[tam] = '\0';
for (int k = 0, j = tam - 1; k < j; ++k, --j)
if (ret[j] != ret[k]) return 0;
return 1;
}
int main()
{
int cases;
int flag;
int n;
ios_base :: sync_with_stdio(0); cin.tie(0);
cin >> cases;
while (cases--)
{
cin >> n;
flag = 0;
for (int i = 2; i < = 16; ++i)
{
if (palindrome(n, i))
{
if (flag) cout << ' ' ;
cout << i;
flag = 1;
}
}
if (!flag) cout << -1;
cout << '\n';
}
}
Input
17
2570
Output
4 16