10396 - Vampire Numbers

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10396 - Vampire Numbers

Post by 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
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by 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
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

Post by eloha »

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

Post by likhan »

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:

Post by 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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by 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
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

10396

Post by 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 :cry:

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion »

I've got AC.
Thanks. :lol:

WanBa
New poster
Posts: 14
Joined: Mon Apr 28, 2003 11:21 am

Post by WanBa »

how u plot "check_vampire_number()" ? :oops:
destiny conditioned by past

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion »

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

:lol: :lol: :lol: :lol:

WanBa
New poster
Posts: 14
Joined: Mon Apr 28, 2003 11:21 am

Post by WanBa »

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

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by 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
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by 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?
Kalo mau kaya, buat apa sekolah?

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

10396 - How can i solve this problem withen the time

Post by Master »

Can anyone tell me how can I solve this withen a the time limit 5sec? :roll:
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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

10396 Vampire Numbers AC.... but

Post by 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. :oops:

Post Reply

Return to “Volume 103 (10300-10399)”