USACO 1.2 - Dual Palindromes

A number that reads the same from right to left as when read from left to right is called a palindrome. The number 12321 is a palindrome; the number 77778 is not. Of course, palindromes have neither leading nor trailing zeroes, so 0220 is not a palindrome.

The number 21 (base 10) is not palindrome in base 10, but the number 21 (base 10) is, in fact, a palindrome in base 2 (10101).

Write a program that reads two numbers (expressed in base 10):

• N (1 <= N <= 15)
• S (0 < S < 10000)

and then finds and prints (in base 10) the first N numbers strictly greater than S that are palindromic when written in two or more number bases (2 <= base <= 10).

Solutions to this problem do not require manipulating integers larger than the standard 32 bits.

PROGRAM NAME: dualpal

INPUT FORMAT

A single line with space separated integers N and S.

SAMPLE INPUT (file dualpal.in)

3 25

OUTPUT FORMAT

N lines, each with a base 10 number that is palindromic when expressed in at least two of the bases 2..10. The numbers should be listed in order from smallest to largest.

SAMPLE OUTPUT (file dualpal.out)

26
27
28

출처: http://train.usaco.org/

Palindromes 은 앞으로 읽으나 뒤로 읽으나 똑같은 수입니다. 주어진 N 과 S가 있을 때 S보다 큰 수중 2~10진법으로 고쳤을 때 최소 2개가 Palindromes 인 수를 N개 출력하는 문제입니다.

직전 문제인 Palindromic Squares 와 거의 같은 문제네요. 

my solving

c++

#include <fstream>
#include <iostream>
#include <string>
using namespace std;
 
 
string convertToBase(int number, int base) 
{
    if (base == 10)
        return to_string(number);
    string ret;
    int temp = base;
 
    while (temp < number)
    {
        temp *= base;
    }
 
    while (true)
    {
        temp /= base;
 
        //if (number / temp == 10)
        //    ret += number / temp - 10 + 'A';
        //else
            ret += number / temp + '0';
 
        number = number % temp;
 
        if (temp < 2) 
            break;
    }
 
    return ret;
}
 
string reverseString(string str) 
{
    string ret = "";
    for (int i = str.length() - 1; i >= 0; i--)
        ret += str[i];
    return ret;
}
 
bool isPalindromic(string str)
{
    return str == reverseString(str);
}
 
bool isDualPalindromes(int number)
{
    bool ret = false;
    int leftCount = 2;
 
    for (int base = 2; base <= 10; base++)
    {
        if (isPalindromic(convertToBase(number, base)))
            leftCount--;
        
        if (leftCount == 0)
        {
            ret = true;
            break;
        }
    }
 
    return ret;
}
 
int main() 
{
    ofstream fout("dualpal.out");
    ifstream fin("dualpal.in");
    int N, S;
    fin >> N >> S;
 
    for (int i = S + 1; ; ++i)
    {
        if (isDualPalindromes(i))
        {
            fout << i << endl;
            N--;
        }
        if (N == 0)
            break;
    }
 
    return 0;
}