2012 百度之星初赛第二题
本帖最后由 wljyy521 于 2012-6-2 21:38 编辑小小度刷礼品时间限制:1000ms 内存限制: 65536kB描述 一年一度的百度之星又开始了,这次参赛人数创下了吉尼斯世界纪录,于是百度之星决定奖励一部分人:所有资格赛提交ID以x结尾的参赛选手将得到精美礼品一份。 小小度同学非常想得到这份礼品,于是他就连续狂交了很多次,提交ID从a连续到b,他想问问你他能得到多少份礼品,你能帮帮他吗?输入 第一行一个正整数T表示数据组数; 接下来T行,每行三个不含多余前置零的整数x,a,b (0 <=x <= 10^18, 1 <= a,b <= 10^18,a <= b)输出 T行,每行为对应的数据情况下,小小度得到的礼品数样例输入 1 88888 88888 88888样例输出 1这个题目乍一看挺简单的,就自认为说题目中的尾数x就是一个一位数,比如说: 尾数 x=8 是 a=10 b=28 之间数的尾数,其实这里的尾数x 不一定就是一位数,你比如说题目给出的样例输入一样: 尾数 x=8888 也就是说尾数不一定就是一位数,要是一位数,这个也太easy了{:5_154:},,所以总的来说吧: 尾数不一定就是一位数这是我有gcc做的答案,是被系统Accepted的,代码如下所示:(我的方法不是最简单的,大家可以贴上自己的代码,大家交流一下,我的方法是比较笨的方法,让大家见笑了{:5_136:})我写的函数比较多,都是一些简单的辅助函数,其实不写成函数也行,这个可能是我的个人习惯吧,我其实是刚刚才学的C语言,以前主要是Java,各位C大牛请指教)
#include <stdio.h>
#include <stdlib.h>
int bytes(int temp){
int num=0;
while(temp!=0){
num++;
temp=temp/10; //
} //
return num;
}
int power(int x,int num){
int i;
int temp=1;
for(i=0;i<num;i++)
temp=temp*x;
return temp;
}
int decide(int x,int a,int b){
int count=0;
int n;
int num=bytes(x);
int add=0;
if(x>a){
count=decide(x,x,b);
return count;
}
if(x==a){
add=1;
}
for( n=a+1;n<=b;n++){
if(((n-x)%10==0)&& (((n-x)%power(10,num))==0)){
count++;
printf("n=%d\n",n);
}
}
return count+add;
}
int main()
{
int x,a,b,t;
int i;
scanf("%d\n",&t);
int count;
for(i=0;i<t;i++)
{
scanf("%d %d %d",&x,&a,&b);
count=decide(x,a,b);
}
for(i=0;i<t;i++)
printf("%d\n",count);
return 0;
}
这个程序是被系统Accepted的,希望大家提出更好的方法 :lol wljyy521 发表于 2012-6-2 21:38 static/image/common/back.gif
友情帮顶,这两天太忙了,脑子转不动了,有空好好回来做做{:6_160:} 研究中,,,, 可是我看不懂题目,到底是做什么啊?楼主能简化下,直接写出要求吗? 首先10^18是大数,溢出了吧亲 其实题目的意思就是判断连续从a 到b 之间的数尾数是x的数有多少个 zhongkedaer 发表于 2012-6-3 11:30 http://www.ruanyuan.net/static/image/common/back.gif
首先10^18是大数,溢出了吧亲
是的,要是使用int 肯定是溢出,使用long long
l if(((n-x)%10==0)&& (((n-x)%power(10,num))==0))
nice啊 没想到~ czc30114 发表于 2012-6-4 09:30 static/image/common/back.gif
if(((n-x)%10==0)&& (((n-x)%power(10,num))==0))
nice啊 没想到~
这个是我突发奇想{:5_143:} 我的想法是用几个数组模拟x,a,b 然后用a,b中的对应位与x比较 都相等就是了 不谋而合
不过好可惜
当天一个小时只AC这一道
所以中途就放弃了
有一点不一样的地方
我不知道bytes函数
自己写方法来判断了x的长度
数据类型用地是unsigned long long 我不知道楼主用的是什么编译环境,我用的是vc++6.0,楼主的main函数中是否应该count->cout。
刚写了一个,对于题目要求的输入、输出格式的理解,与楼主略有不同!
附:
#include <stdio.h>
#include <math.h>
#define unllong unsigned long
int check_bits( unllong x )
{
int num=0;
while ( x )
{
x /= 10;
num++;
}
return num;
}
int check_mantissa( unllong i, unllong x )
{
unllong bits_num;
bits_num = check_bits(x);
if ( i%(unllong)pow(10, bits_num) == x )
{
return 1;
}
return 0;
}
int process( unllong x, unllong a, unllong b)
{
unllong i, print_num=0;
for ( i=a; i<=b; i++)
{
if ( check_mantissa(i, x) )
{
print_num++;
}
}
return print_num;
}
void main()
{
unllong x, a, b;
int t, i;
unllong * counter;
scanf("%d", &t);
counter = malloc(t*sizeof(unllong));
for (i=0; i<t; i++)
{
scanf("%ld%ld%ld", &x, &a, &b);
if( a<1 || b>pow(10, 18) || x<a || x>b )
{
printf("data error\n");
i--;
continue;
}
*(counter+i) = process(x, a, b);
}
for (i=0; i<t; i++)
{
printf("You can get from Group %d: %u\n", i+1, *(counter+i));
}
}
注:
1、vc不支持C99标准,所以用long(32bits)代替longlong(64bits)。
2、人工输入时T的值不可能很大,所以我采用int或unsigned char应该没问题。
3、题目要求的1s的处理时间,和内存要求,这个我没考虑。望大神给出处理时间和所需内存大小的代码。 poiu9080 发表于 2012-6-10 15:47 static/image/common/back.gif
不谋而合
不过好可惜
当天一个小时只AC这一道
我也是自己判断的 lhong 发表于 2012-6-12 10:11 static/image/common/back.gif
我不知道楼主用的是什么编译环境,我用的是vc++6.0,楼主的main函数中是否应该count->cout。
刚写了一个, ...
我用的是Ubuntu下的code::blocks,支持gcc 这是第一场吧 stevesea 发表于 2012-6-14 13:04 static/image/common/back.gif
这是第一场吧
嗯是的
页:
[1]