学步园

 
Dual Palindromes
Mario Cruz (Colombia) & Hugo Rickeboer (Argentina) 
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

/*
ID:nealgav1
PROG:dualpal
LANG:C++
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 12345
using namespace std;
char num[123];
const char ke[]={'0','1','2','3','4','5','6','7','8','9'};
int shu[N];
int transform(int sh,int n)//把shu转换为n进制
{
  int i=0;
  while(sh)
  {
    num[i++]=ke[sh%n];
    sh/=n;
  }
  num[i]='\0';
  return i;
}
int charge()
{
  int l=0,r=strlen(num)-1;
  bool flag=1;
  while(l<r)
  {
    if(num[l]!=num[r])
    {
      flag=0;
      break;
    }
    l++;r--;
  }
  return flag;
}
int creat()
{
  int ans=0;
  int pa;
  int ques=999999;
  for(int i=1;;i++)
  {
    pa=0;
    if(i==10000)
    ques=ans;
    if(ans-ques>15)
    break;
    for(int j=2;j<=10;j++)
    {
      transform(i,j);
      if(charge())
      {
        pa++;
        if(pa>=2)
        {
          shu[++ans]=i;
          break;
        }
      }
    }
  }
  return ans;
}
int search(int m,int l,int r)
{
  int mid;
  while(l<r)
  {
    if(r==l+1)
    break;
    mid=(l+r)/2;
    if(shu[mid]==m)
    return mid+1;
    else if(shu[mid]<m)
     l=mid;
     else
     r=mid;
  }
  if(shu[mid]<m)
  return mid+1;
  else
  return mid;
}
int main()
{
  freopen("dualpal.in","r",stdin);
  freopen("dualpal.out","w",stdout);
  int ans=creat();
  int n,s;
  int k;
  while(scanf("%d%d",&n,&s)!=EOF)
  {
    k=search(s,1,ans);
    if(shu[k]<=s)
    k++;
    for(int i=k;i<k+n;i++)
    printf("%d\n",shu[i]);
  }
}

USER: Neal Gavin Gavin [nealgav1]
TASK: dualpal
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.022 secs, 3392 KB]
   Test 2: TEST OK [0.032 secs, 3392 KB]
   Test 3: TEST OK [0.032 secs, 3392 KB]
   Test 4: TEST OK [0.043 secs, 3392 KB]
   Test 5: TEST OK [0.043 secs, 3392 KB]
   Test 6: TEST OK [0.032 secs, 3392 KB]
   Test 7: TEST OK [0.043 secs, 3392 KB]

All tests OK.
Your program ('dualpal') produced all correct answers!  This is your
submission #5 for this problem.  Congratulations!

Here are the test data inputs:

------- test 1 ----
5 1
------- test 2 ----
9 10
------- test 3 ----
15 9900
------- test 4 ----
10 90
------- test 5 ----
12 125
------- test 6 ----
12 1900
------- test 7 ----
8 500

Keep up the good work!

Dual palindromes are actually very common, a fact we can test by writing a program such as this one.

Since they are very common, we can just use a brute force search to test all numbers bigger than s until we find enough dual palindromes.

How do we know they are common enough? Write the brute force program (which is very simple and thus not much effort) and check.

This reasoning is a little circular, but if we had been wrong and ended up needing a more clever and more efficient algorithm, we would have this brute force version to test against.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

/* is string s a palindrome? */
int
ispal(char *s)
{
    char *t;

    t = s+strlen(s)-1;
    for(t=s+strlen(s)-1; s<t; s++, t--)
	if(*s != *t)
	    return 0;

    return 1;
}

/* put the base b representation of n into s: 0 is represented by "" */
char*
numbconv(char *s, int n, int b)
{
    int len;

    if(n == 0) {
	strcpy(s, "");
	return s;
    }

    /* figure out first n-1 digits */
    numbconv(s, n/b, b);

    /* add last digit */
    len = strlen(s);
    s[len] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[n%b];
    s[len+1] = '\0';
    return s;
}

/* is number n a dual palindrome? */
int
isdualpal(int n)
{
    int i, j, npal;
    char s[40];

    npal = 0;
    for(i=2; i<=10; i++)
	if(ispal(numbconv(s, n, i)))
	    npal++;

    return npal >= 2;
}

void
main(void)
{
    FILE *fin, *fout;
    int n, s;

    fin = fopen("dualpal.in", "r");
    fout = fopen("dualpal.out", "w");
    assert(fin != NULL && fout != NULL);

    fscanf(fin, "%d %d", &n, &s);

    for(s++; n>0; s++) {
	if(isdualpal(s)) {
	    fprintf(fout, "%d\n", s);
	    n--;
	}
    }

    exit(0);
}