首页 > 代码库 > 循环序列

循环序列

循环序列

(circulate.cpp/c/pas)

(1s/256M)

 

题目描述

Alice与Bob在玩游戏:

Alice首先给出两个数X与Y(X<=Y);

Bob则按顺序将X,X+1,X+2,…,Y-1,Y写成一个大数S。

Alice最后将S首尾相连,让其围成一个圈。

这时,Bob想知道,从S的开头出发,往后的第L到第R数字之和是多少。

 

输入格式(circulate.in)

第一行四个整数X,Y,L,R,代表Alice的两个数字和Bob想要知道的第L位到第R位的数字之和。

 

输出格式(circulate.out)

仅一行,一个整数M,代表第L位到第R位的数字之和。

 

样例输入

10 11 4 12

 

样例输出

7

 

样例解释

Bob将数字写成一行大数S = 1011;围成一个圈后,从第4位到第12位分别是1,1,0,1,1,1,0,1,1,它们的和是7.

 

数据范围与限制

对于50%的数据,L=1, X,Y,L,R<=1000;

对于100%的数据,S的长度不大于10000,X,Y,L,R<=100000000.

 

代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int x,y,l,r,lens,sum,tot;
 5 long long ans;
 6 int num[10001],a[10001];
 7 int main()
 8 {
 9     /*freopen("circulate.in","r",stdin);
10     freopen("circulate.out","w",stdout);*/
11     cin>>x>>y>>l>>r;
12     int tmp=x;
13     while(tmp)//将x,y各位数倒序放入num中 
14     {
15         num[++lens]=tmp%10;
16         tmp/=10;
17     }
18     tmp=y;
19     while(tmp)
20     {
21         num[++lens]=tmp%10;
22         tmp/=10;
23     }
24     int b=0;
25     for(int i=lens;i;i--)
26     //将各个数正序放入a数组中 
27      a[++b]=num[i];
28     for(int i=1;i<=lens;i++)//求出各位数之和 
29      sum+=a[i];
30     while(r>lens) 
31     {
32         r-=lens;
33         tot++;
34     }
35     while(l>=lens)
36     {
37         l-=lens;
38         tot--;
39     }
40     ans+=tot*sum;
41     if(l>r)//l在r的右侧 
42      for(int i=l;i>r;i--)
43       ans-=a[lens-i];
44     else
45      for(int i=lens-l+1;i>=lens-r+1;i--)
46       ans+=a[i];
47     cout<<ans;
48     //fclose(stdin);fclose(stdout);
49     return 0;
50 }

 

循环序列