10396 - Vampire Numbers

[eloha]

I got wrong answer for this problem.
Can anyone post part of the answers for n=6 and n=8?
My answer for n=6, total number of line: 107

• 102510
  104260
  105210
  .
  .
  .
  815958
  829696
  939658

My answer for n=8, total number of line: 2366

• 10025010
  10042510
  10052010
  .
  .
  .
  96098800
  96399072
  96977920

[kmhasan]

Your output seems to be incorrect.
My AC solution gives 106 lines of output for N=6, and 2353 lines of output for N=8.

for N=6:
102510
104260
105210
105264
105750
....
....
789250
794088
809964
815958
829696
939658

for N=8:
10025010
10042510
10052010
10052064
10081260
10102252
...
...
94765198
94765918
95438970
95999260
96098800
96399072
96977920

[eloha]

Your output seems to be incorrect.
My AC solution gives 106 lines of output for N=6, and 2353 lines of output for N=8.

I drop the duplicate numbers from my answer and now I got 106 lines for N=6 and 2353 lines for N=8. Just like yours. But I still got WA. Can anyone help me to check my output. If you will, please leave me a message. Thanks in advance.

[likhan]

As said

Your output seems to be incorrect.
My AC solution gives 106 lines of output for N=6, and 2353 lines of output for N=8.

for N=6:
102510
104260
105210
105264
105750
....
....
789250
794088
809964
815958
829696
939658

for N=8:
10025010
10042510
10052010
10052064
10081260
10102252
...
...
94765198
94765918
95438970
95999260
96098800
96399072
96977920

If you mail me your solution I can check it out p_persia@yahoo.com

[Dominik Michniewski]

Could anyone help me and says, how can I solve this question with time below 1 second ?
Is any special math solution for this ?

I try to solve this problem, but my solution runs over 30 seconds ...

Please help

Regards
Dominik Michniewski

[Larry]

Try precalculating the results for 4, 6, and 8, store it somewhere and just print it out when you need to.

If there's a non-precal way of doing this, let me know..

[Red Scorpion]

Using my algorithm I always get TLE.
Here is my algo :
(At first I precalculating n=4,6,and 8 and store it at array.

for n=8 :

for (i=1000; i<=9999; i++) {
--for (j=i; j<=9999; j++) {
---- if(i%2 && j%2) continue;
---- else check_vampire_number();
--}
}

Is there another Algo, that not using an iteration and can run
fast enough ?

Thanks,
Red Scorpion

[Red Scorpion]

I've got AC.
Thanks.

[WanBa]

how u plot "check_vampire_number()" ?

[Red Scorpion]

Use modulo congruence(I find it in the net).

[WanBa]

Red Scorpion:
if possible ,illustrate to me with sufficient detail.
thanx in advance !

[Red Scorpion]

Sure, This is modulo 9 congruence problem.

If x,y is a vampire number then :
x.y == x+y (mod 9)

The solution of the above formula is (x mod 9, y mod 9) :
(0,0), (2,2), (3,6), (5,8), (6,3) , and (8,5).

so you find for (x mod 9, y mod 9) that satisfy the above condition and check whether the number is vampire. Of course that's will reduce the search time.

Good Luck,
RS

[titid_gede]

i try using your clue, yes i believe it will reduce search time, but still too slow. any other trick to prune the search?

[Master]

Can anyone tell me how can I solve this withen a the time limit 5sec?
I do not find any way to solve it withen the time limit . Pls Help me...

Thanks in advance
M H Rasel
CUET Old Sailor

[sohel]

I solved this problem by precalculating all the answers and using a table.
It took around 1.5 minutes to generate all the numbers in my P4 processor.

Is there any efficient way of solving this problem in which table won't be necessary...

... cos I am not satisfied with my method.