USACO 1.2.5 Dual Palindromes双重回文数

发布于 2019-04-05  12 次阅读


题目描述

如果一个数从左往右读和从右往左读都是一样,那么这个数就叫做“回文数”。例如,12321就是一个回文数,而77778就不是。当然,回文数的首和尾都应是非零的,因此0220就不是回文数。

事实上,有一些数(如21),在十进制时不是回文数,但在其它进制(如二进制时为10101)时就是回文数。

编一个程序,从文件读入两个十进制数

N (1 <= N <= 15)

S (0 < S < 10000)

然后找出前N个满足大于S且在两种以上进制(二进制至十进制)上是回文数的十进制数,输出到文件上。

本问题的解决方案不需要使用大于4字节的整型变量。

输入

只有一行,用空格隔开的两个数N和S。

输出

N行, 每行一个满足上述要求的数,并按从小到大的顺序输出。

思路

暴力模拟一下就可以了

{
ID: a1192631 
PROG: dualpal
LANG: PASCAL
} 
var
  x,m:int64;
  i,j,l,r,k,s,y,n:longint;
  st:string;
  a:array[1..1000]of longint;
function sjz(n:string;x:longint):int64;
  var
    st:string;
    i:longint;
  begin
    st:=n;
    sjz:=0;
    if x<=9 then
      for i:=1 to length(st) do
        sjz:=sjz*x+ord(st[i])-48
    else
      for i:=1 to length(st) do
        if (st[i] in ['A'..'Z']) then sjz:=sjz*x+ord(st[i])-55
                                 else sjz:=sjz*x+ord(st[i])-48;
  end;
procedure zh(n,m:int64);
  var
    st,ch:string;
    x,p:longint;
  begin
    x:=n;    st:=''; i:=101;
      while x>0 do
        begin
          dec(i);
          a[i]:=x mod m;
          x:=x div m;
        end;

  end;

begin
  assign(input,'dualpal.in'); reset(input);
  assign(output,'dualpal.out'); rewrite(output);
  readln(l,r);
  for k:=r+1 to maxlongint do
    begin
      m:=10;
      str(k,st);
      x:=sjz(st,m);
      s:=0;
      for n:=2 to 10 do
        begin
          fillchar(a,sizeof(a),0);
          zh(x,n);
          j:=100;
          while (i<=j) and (a[i]=a[j]) do begin inc(i); dec(j); end;
          if i>j then inc(s);
          if s>=2 then begin writeln(k); inc(y); break; end;
        end;
      if y>=l then halt;
    end; 
end.

]]>