10396 - Vampire Numbers

[WR]

Hi Sohel,

there's a valuable hint by Red Scorpion down this thread (June 2003)
but you probably read that already.

I used two nested loops and prepared a table with valid counters:

[c] for (i=100;i<10000;i++){
ROOT = 0;
if ((i % 9) == 1) continue; <-- these counters can't
if ((i % 9) == 4) continue; <-- generate
if ((i % 9) == 7) continue; <-- vampire numbers
rootx(i,&ROOT); <-- sum of digits for valid counters
}
[/c]

In the loops these counters are excluded:
[c]for (i=min;i<max;i++){
if (!ROOT) continue;

...


for (j=k;j<max;j++){
if (!ROOT[j]) continue;
...

vn = i*j;
if (((i+j) % 9) != (vn % 9)) continue;

VAMPIRE[maxnum] = vn; maxnum++;
}
}
[/c]

This program is definitely not optimal but needs less than 2 seconds.
Just make sure you get anything possible out of the inner loop.

By the way, there is a description of an algorithm in the net
hjem.get2net.dk/jka/math/vampires
I didn't understand all of it, though.

[minskcity]

can anybody tell me which 7 numbers are not vampire numbers? I've heard there are only 106 of them with length 6.

• 102510,104260,105210,105264,105750,
  110758,115672,118440,120600,123354,
  125248,125460,125500,126000,126846,
  129640,131242,132430,135828,136948,
  139500,140350,143500,145314,146952,
  150300,152608,153000,153436,156240,
  162976,163944,172822,173250,174370,
  182250,182650,182700,186624,190260,
  192150,201852,211896,213466,215860,
  217638,218488,218700,226498,226872,
  229648,233896,241564,245182,251896,
  253750,254740,260338,262984,263074,
  284598,284760,286416,296320,315594,
  315900,319536,326452,329346,329656,
  336550,336960,338296,346968,362992,
  365638,368550,378400,378418,378450,
  384912,392566,404968,416650,416988,
  428980,429664,447916,456840,457600,
  458640,475380,486720,498550,529672,
  538650,559188,567648,568750,629680,
  638950,673920,679500,688000,729688,
  738468,769792,789250,794088,809964,
  815958,829696,939658

[asif_rahman0]

The problem is actually a pre calculative problem.So,if you can calculate the numbers using a dummy program and then submit.Then it must be solved within 5 sec.Otherwise,in the problem description the numbers of 4 digits are given.So,you have to just calculate only for 6 and 8 digits.And as far as I know the 6 and 8 digits numbers start from 317 and 3170 respectivly.After all pre calculation solve the problem within 5 sec.

BEST OF LUCK

[asif_rahman0]

I've got 148 for N=6 and 3226 for N=8.Is my calculation is correct?Help me plz

[daveon]

minskcity wrote:

can anybody tell me which 7 numbers are not vampire numbers? I've heard there are only 106 of them with length 6.

Code: Select all

210 * 600 = 126000
150 * 930 = 139500
410 * 350 = 143500
510 * 300 = 153000
210 * 870 = 182700
810 * 270 = 218700
860 * 800 = 688000

When both x and y have trailing 0's, the product is not considered.

[minskcity]

Thanks a lot . I should start reading the problem statements more carefully...

[sazzadcsedu]

my solution give ,n=6 then 106
n=8 then 2365
but from forum i came to know n=8 should be 2353.
so plz someone help.
i discarded both having trailing Zero.
my code


#include<stdio.h>
#include<memory.h>
#include<stdlib.h>

int comp(const void *i,const void *j)
{
return *(int *)i- *(int*)j;
}



int main()



{

int i,a,j,count,n,l,k;
int fill[10];
int sort[10000];
int max=0;
//int flag[10];


memset(sort,0,sizeof(sort));

while(scanf("%d",&n)==1)

{
k=0;
if(n==4)

{
for(i=10;i<100;i++)

{

for(j=i+1;j<100;j++)

{
memset(fill,0,sizeof(fill));


fill[i/10]+=1;
fill[i%10]+=1;
fill[j/10]+=1;
fill[j%10]+=1;


a=i*j;

count=0;
if(a>=1000)
{
if(fill[a%10]>=1)
{
count=count+1;
fill[a%10]--;

}
if(fill[(a/10)%10]>=1)
{
count+=1;
fill[(a/10)%10]--;

}
if(fill[(a/100)%10]>=1)
{
count+=1;
fill[(a/100)%10]--;
}


if(fill[a/1000]>=1)

{
count+=1;
fill[a/1000]--;

}


if(count==4 && a%2==0)
{
sort[k]=a;
k++;
// printf("%d * %d ==%d\n",i,j,a);
}


}



}

}


}

else if(n==6)

{
for(i=100;i<1000;i++)

{

for(j=i+1;j<1000;j++)

{



memset(fill,0,sizeof(fill));


fill[i%10]+=1;
fill[(i/10)%10]+=1;
fill[i/100]+=1;
fill[j%10]+=1;
fill[(j/10)%10]+=1;
fill[j/100]+=1;


a=i*j;

count=0;
if(a>=100000 && (i%10!=0 || j%10!=0))
{
if(fill[a%10]>=1)
{
count=count+1;
fill[a%10]--;

}
if(fill[(a/10)%10]>=1)
{
count+=1;
fill[(a/10)%10]--;

}
if(fill[(a/100)%10]>=1)
{
count+=1;
fill[(a/100)%10]--;
}


if(fill[(a/1000)%10]>=1)

{
count+=1;
fill[(a/1000)%10]--;

}
if(fill[(a/10000)%10]>=1)
{
count+=1;
fill[(a/10000)%10]--;
}


if(fill[(a/100000)%10]>=1)

{
count+=1;
fill[(a/100000)%10]--;

}





if(count==6 && a%2==0)

{
sort[k]=a;
k++;

printf("%d * %d ==%d\n",i,j,a);
}
}


}



}




}



else if(n==8)

{
for(i=1000;i<10000;i++)

{

for(j=i+1;j<10000;j++)

{
memset(fill,0,sizeof(fill));


fill[i%10]+=1;
fill[(i/10)%10]+=1;
fill[(i/100)%10]+=1;
fill[i/1000]+=1;
fill[j%10]+=1;
fill[(j/10)%10]+=1;
fill[(j/100)%10]+=1;
fill[j/1000]+=1;


a=i*j;

count=0;
if(a>=10000000 && (i%10!=0 || j%10!=0))
{
if(fill[a%10]>=1)
{
count=count+1;
fill[a%10]--;

}
if(fill[(a/10)%10]>=1)
{
count+=1;
fill[(a/10)%10]--;

}
if(fill[(a/100)%10]>=1)
{
count+=1;
fill[(a/100)%10]--;
}


if(fill[(a/1000)%10]>=1)

{
count+=1;
fill[(a/1000)%10]--;

}
if(fill[(a/10000)%10]>=1)
{
count+=1;
fill[(a/10000)%10]--;
}


if(fill[(a/100000)%10]>=1)

{
count+=1;
fill[(a/100000)%10]--;

}
if(fill[(a/1000000)%10]>=1)
{
count+=1;
fill[(a/1000000)%10]--;
}


if(fill[(a/10000000)%10]>=1)

{
count+=1;
fill[(a/10000000)%10]--;

}






if(count==8 && a%2==0)
{

sort[k]=a;
k++;
printf("%d * %d = %d\n",i,j,a);
}
}

}

}




}

qsort(sort,k-1,sizeof(int),comp);

for (l=0;l<k;l++)
{
printf("%d\n",sort[l] );

}

printf("\n");
printf("total number:%d\n",k-1);

}

return 0;

}