Acm队的流年对数学的研究不是很透彻,但是固执的他还是想一头扎进去。
浏览网页的流年忽然看到了网上有人用玫瑰花瓣拼成了521三个数字,顿时觉得好浪漫,因为每个男生都会不经意的成为浪漫的制造者。此后,流年走到哪里都能看到5、2、1三个数字,他怒了,现在他想知道在连续的数中有多少数全部包含了这三个数字。例如12356就算一个,而5111就不算。特别的,如果他看到了521三个数连续出现,会特别的愤怒。例如35210。
- 输入
- 多组测试数据:
一行给定两个数a,b(0<a,b<1000000),表示数字的开始和结束。 - 输出
- 一行显示他想要知道的数有几个及显示有多少个数字令他特别的愤怒。用空格隔开。
样例输入
200 500
300 900
1 600
样例输出
Case 1:2 0
Case 2:2 1
Case 3:6 1
南阳理工提供的最优代码如下(注释为个人编写):
#include<stdio.h> /*定义二维数组,2行1000001列,在下面的程序中用第一行(a[0][i])存储截止到 i 有多少个含有5,2,1的数 用第二行(a[1][i])存储截止到 i 有多少个连续含有5,2,1(即含有521)的数*/ int a[2][1000001]={0}; int main() { int k=0,i,sum=0;//k存储含有521的数的个数,sum存储含有5,2,1的数的个数 for(i=1;i<=1000000;i++)//i 的值可以从125开始,因为125之前并没有满足题意的数字 { if((i%10==5||(i/10)%10==5||(i/100)%10==5||(i/1000)%10==5||(i/10000)%10==5||(i/100000)%10==5)&&(i%10==2||(i/10)%10==2||(i/100)%10==2||(i/1000)%10==2||(i/10000)%10==2||(i/100000)%10==2)&&(i%10==1||(i/10)%10==1||(i/100)%10==1||(i/1000)%10==1||(i/10000)%10==1||(i/100000)%10==1)) //判断i是否含有5,2,1三个数字 { sum++; if(i/1000==521||(i/100)%1000==521||(i/10)%1000==521||i%1000==521)k++; //在含有5,2,1三个数字基础之上再判断5,2,1是否连续出现 } a[0][i]+=sum;//统计截止到 i 有多少个含有5,2,1的数 a[1][i]+=k;//统计截止到 i 有多少个连续含有5,2,1(即含有521)的数 } int m,n,w=0; while(scanf("%d%d",&n,&m)!=EOF) //截止到m含有5,2,1的数的个数减去截止到n - 1含有5,2,1的数的个数即为所求从n到m含有含有5,2,1的数的个数 //同理,求得含有521数的个数 printf("Case %d:%d %d\n",++w,a[0][m]-a[0][n-1],a[1][m]-a[1][n-1]); }
个人代码(南阳ACM系统超时,求大神优化):
#include<stdio.h> int s[1000000]; //数字分离例如123分离为1 2 3 分别存入数组,返回数字位数 int Fl(int x) { int i = 0; while(x) { s[i] = x % 10; x /= 10; i ++; } return i; } int main() { int a,b,i,count; int k,k1,k2,k5; int countl = 0;//统计怒的个数 int counttl = 0;//统计特别怒的个数 while(scanf("%d%d",&a,&b)) { for(i = a; i <= b; i ++) { count = Fl(i); k1 = k2 = k5 = 0;//用0标记不存在 for(k = 0; k < count; k ++) { if(s[k] == 1) k1 = 1; //表示1在这个数中出现 else if(s[k] == 2) k2 = 1;//表示2在这个数中出现 else if(s[k] == 5) k5 = 1;//表示5在这个数中出现 if(s[k]== 1 && s[k+1]== 2 && s[k+2] == 5) counttl ++;//存在一个使他特别怒的数 } if(k1 && k2 && k5) countl ++; } printf("%d %d\n",countl,counttl); countl = counttl = 0; } return 0; }