SRETAN (sretan.pas/c/cpp)
题目描述
4和7是幸运数字，输入k，输出第k个只含有4和7的数。
输入格式
一行一个数k
输出格式
一行一个数表示答案
样例输入
3
样例输出
44
数据范围与约定
1 <= k <= 10^9

分析：

   个位上有2个，十位上有4个，百位上有8个…… 找出规律：2^n，我们要分析第n个是在哪一位上，当前面所有方案数大于k时，可以在当前位上查找。将当前位数div 2；若k大于它，则输出7，否则输出4，直到div 2=1时，输出所有的数。

代码实现：

program exam;

var

  i,j:longint;

  k,t,s1,a2:int64;

function f(a,b:int64):int64;

var

  t,y:int64;

begin

  t:=1;

  y:=a;

  while b<>0 do

  begin

    if b and 1=1 then

      t:=t*y;

    y:=y*y;

    b:=b shr 1;

  end;

  exit(t);

end;

procedure make(x,y:int64);

begin

  if x div 2=1 then

  begin

    if y=2 then

      write(7);

    if y=1 then

      write(4);

    close(input);

    close(output);

    halt; 注意，一定要halt；如果exit，会继续递归，会产生多余的数。

  end;

  x:=x div 2;

  if y>x then

  begin

    write(7);

    y:=y-x;

    make(x,y);

  end;

  if y<=x then

  begin

    write(4);

    make(x,y);

  end;

end;

begin

  assign(input,‘sretan.in‘);

  reset(input);

  assign(output,‘sretan.out‘);

  rewrite(output);

  readln(k);

  for i:=1 to 60 do

  begin

    t:=f(2,i+1)-2;

    if t>=k then

    begin

      s1:=f(2,i)-2;

      k:=k-s1;

      a2:=f(2,i);

      make(a2,k);

    end;

    if t>k then

      break;

  end;

  close(input);

  close(output);

end.

SRETAN