首页 > 代码库 > SRETAN

SRETAN

 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