## 10396 - Vampire Numbers

Moderator: Board moderators

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

### 10396 - Vampire Numbers

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
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Contact:
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
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan
kmhasan wrote: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
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions
As said
kmhasan wrote: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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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 ...

Regards
Dominik Michniewski

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

### 10396

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
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
I've got AC.
Thanks.

WanBa
New poster
Posts: 14
Joined: Mon Apr 28, 2003 11:21 am
how u plot "check_vampire_number()" ?
destiny conditioned by past

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Use modulo congruence(I find it in the net).

WanBa
New poster
Posts: 14
Joined: Mon Apr 28, 2003 11:21 am
Red Scorpion:
if possible ,illustrate to me with sufficient detail.
destiny conditioned by past

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
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
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
i try using your clue, yes i believe it will reduce search time, but still too slow. any other trick to prune the search?
Kalo mau kaya, buat apa sekolah?

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Contact:

### 10396 - How can i solve this problem withen the time

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...

M H Rasel
CUET Old Sailor

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### 10396 Vampire Numbers AC.... but

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.