How to solve this problem?
I think that we can optimize function fun(int a) by replacing line:
Code: Select all
for(i=1; i<=a; i++){
Code: Select all
for(i=max(1, a-100); i<=a; i++){
Thanks, bye!
Moderator: Board moderators
Code: Select all
for(i=1; i<=a; i++){
Code: Select all
for(i=max(1, a-100); i<=a; i++){
Code: Select all
floor(a / 101) * 10 + floor( (a % 101) / 11 ) + 4
hi ......Victor Barinov wrote:Hello, everybody!!!
How to solve this problem?
I think that we can optimize function fun(int a) by replacing line:toCode: Select all
for(i=1; i<=a; i++){
But what to do with fun(int a, int b) ???Code: Select all
for(i=max(1, a-100); i<=a; i++){
Thanks, bye!
Code: Select all
for(i=1;i<=10000000;++i) B[i+sod(i)]=true;
for(i=1;i<=10000000;++i)
if(!B[i]) A[ct++]=i;
That's a nice idea. May pass the timelimit. I had also checked those papers but overlooked this point. Maybe was concentrating on some other formula.Sedefcho wrote:For even bases b the following can be proven:
If n ≥ b is a self number then n has the form n = (b-1) + a1(b^1+1) + a2(b^2+1) + ... with 0 ≤ ai < b.
Code: Select all
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 10000001
int arr[MAX],arr1[MAX/10];
int main ()
{
int i, k, sum,cnt,a,b,no;
char str[30],*p,*y;
cnt=1;
for (i = 1; i < MAX; i++)
{
k = i;
sum = 0;
while (k)
{
sum += k % 10;
k /= 10;
}
if ( (i + sum < MAX) && arr[i+sum]==0)
{
arr[i + sum] = i;
}
if(arr[i]==0)
arr1[cnt++]=i;
}
/* for(i=0;i<cnt;i++)
printf("%d\n",arr1[i]);
*/
// printf("%d\n",cnt);
scanf(" %d\n",&no);
for(i=1;i<=no;i++)
{
fgets(str,25,stdin);
b=-1;
y=str;
k=0;
while((p=strtok(y," "))!=NULL)
{
if(k==0)
a=strtoul(p,NULL,10);
if(k==1)
b=strtoul(p,NULL,10);
y=NULL;
k++;
}
printf("Case %d: ",i);
if(k==1)
printf("%d\n",(arr[a]==0)?-1:arr[a]);
else
{
int *pos1,*pos2;
pos1=lower_bound(arr1,arr1+cnt,a-1);
pos2=lower_bound(arr1,arr1+cnt,b);
printf("%d\n",-distance(arr1,pos1)+distance(arr1,pos2));
}
}
return 0;
}
Code: Select all
#include<cstdio>
#include<ctype.h>
#include<iostream>
int max(int a,int b){
if(a>b)
return a;
return b;
}
int main(){
char string[50];
int num1,num2,c,cnt,test,i,l,sum,j,cas=0;
int i1,i2,i3,i4,i5,i6;
bool arr[10000001]={0};
arr[1]=arr[3]=arr[5]=arr[7]=1;
for(i1=0;i1<10000000;i1+=1000001){
for(i2=0;i2<1000000;i2+=100001){
for(i3=0;i3<100000;i3+=10001){
for(i4=0;i4<10000;i4+=1001){
for(i5=0;i5<1000;i5+=101){
for(i6=0;i6<100;i6+=11){
sum=i1+i2+i3+i4+i5+i6+9;
arr[sum]=true;
}
}
}
}
}
}
scanf("%d",&test);
while(test>0){
scanf(" %[^\n]",string);
l=strlen(string);
c=0;
cas++;
for(i=0;i<l;i++){
if(isdigit(string[i])){
sum=0;
while(isdigit(string[i])){
sum=sum*10+string[i]-'0';
i++;
}
c++;
if(c==1)
num1=sum;
else
num2=sum;
}
}
printf("Case %d: ",cas);
if(c==1){
if(arr[num1]==false){
printf("-1\n");
}
else{
i=max(1,num1-90);
cnt=0;
for(;i<=num1;i++){
j=i;
sum=0;
while(j>0){
sum+=j%10;
j/=10;
}
if(i+sum==num1){
printf("%d\n",i);
break;
}
}
}
}
else if(c==2){
cnt=0;
for(i=num1;i<=num2;i++)
if(arr[i]==false)
cnt++;
if(cnt==0)
printf("-1\n");
else
printf("%d\n",cnt);
}
test--;
}
return 0;
}