PKU OJ 1019 Number Sequence

2023-11-01 19:38

文章标签 number sequence oj pku 1019

本文主要是介绍PKU OJ 1019 Number Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

终于0MS AC了，时间复杂度为O（1）

我的感觉是：算法虽然有点复杂，但很容易想到，编程时细心点很快就能AC

#include<stdio.h>
#include<math.h>
long pow10(long n)
{
if(n==0)return 1;
else if(n==1)return 10;
else if(n==2)return 100;
else if(n==3)return 1000;
else if(n==4)return 10000;
else if(n==5)return 100000;
else if(n==6)return 1000000;
else return -1;
}
#define MAX 4
int main()
{
int i,t,n,m;
long I,l[MAX],len[MAX],X,R,Xp,Y,r,y;
//compute l
l[0]=9;
for(i=1;i<MAX;i++)l[i]=l[i-1]+(i+1)*9*pow10(i);
//compute len
len[0]=l[0]*(l[0]+1)/2;
for(i=1;i<MAX;i++)len[i]=len[i-1]+9*pow10(i)*l[i-1]+(i+1)*9*pow10(i)*(9*pow10(i)+1)/2;
//input
scanf("%d",&t);
while(t--)
{
  scanf("%ld",&I);
  //Get X
  //compute n
  if(I<=len[0])n=1;
  else if(I>len[MAX-1])n=MAX+1;
  else
  {
   for(i=1;i<MAX;i++)
    if(I<=len[i])
    {
     n=i+1;
     break;
    }
  }
  //compute X and R
  if(n==1)
  {
   X=(long)((sqrt(1+8*(I-1))+1)/2);
   R=I-X*(X-1)/2;
  }
  else
  {
   Xp=(long)((sqrt((n+2.*l[n-2])*(n+2.*l[n-2])+8.*n*(I-1-len[n-2]))+n-2*l[n-2])/(2*n));
   X=Xp+pow10(n-1)-1;
   R=I-len[n-2]+(1-Xp)*l[n-2]-Xp*(Xp-1)/2*n;
  }
  //Get Y
  //compute m
  if(R<=l[0])
  {
   m=1;
   r=R;
  }
  else if(R>l[MAX-1])
  {
   m=MAX+1;
   r=R-l[MAX-1];
  }
  else
  {
   for(i=1;i<MAX;i++)
   {
    if(R<=l[i])
    {
     m=i+1;
     r=R-l[i-1];
     break;
    }
   }
  }
  //compute Y and r
  Y=(r-1)/m+pow10(m-1);
  r=(r-1)%m+1;
  //compute y and output
  y=Y%((long)pow10(m-r+1))/((long)pow10(m-r));
  printf("%ld/n",y);
}
return 0;
}