471 - Magic Numbers

[Ferdous]

What's wrong with my code? plz help me.


deleted later......

[Riyad]

can some one provide me with some I/O of Magic Numbers[471] .. i am getting WA on this .. may be i am missing some thing ...Pliz Help

Here is some Random I/O[cpp]
30

5

6

120

100

50

33

1234567890

123456098

52364

1205478

1245698

52369874

1234506879

5263417890

1472583690

741852963

4563217890

9517246830

7531478293

125364780

120456987

358947126

100000000

123000000

963852741

524178939

9999999

14253

555


121[/cpp]

[cpp]5 / 1 = 5
10 / 2 = 5
15 / 3 = 5
20 / 4 = 5
25 / 5 = 5

6 / 1 = 6
12 / 2 = 6
18 / 3 = 6
24 / 4 = 6
30 / 5 = 6
36 / 6 = 6

120 / 1 = 120
240 / 2 = 120
360 / 3 = 120
480 / 4 = 120
720 / 6 = 120
840 / 7 = 120
960 / 8 = 120
1560 / 13 = 120
1680 / 14 = 120
1920 / 16 = 120
2160 / 18 = 120
2760 / 23 = 120
3120 / 26 = 120
3240 / 27 = 120
3480 / 29 = 120
3720 / 31 = 120
3840 / 32 = 120
4320 / 36 = 120
4560 / 38 = 120
4680 / 39 = 120
4920 / 41 = 120
5160 / 43 = 120
5640 / 47 = 120
5760 / 48 = 120
6120 / 51 = 120
6240 / 52 = 120
6480 / 54 = 120
6720 / 56 = 120
6840 / 57 = 120
7320 / 61 = 120
7560 / 63 = 120
7680 / 64 = 120
8160 / 68 = 120
8520 / 71 = 120
8640 / 72 = 120
8760 / 73 = 120
9120 / 76 = 120
9360 / 78 = 120
9480 / 79 = 120
9720 / 81 = 120
9840 / 82 = 120
12360 / 103 = 120
12480 / 104 = 120
12840 / 107 = 120
12960 / 108 = 120


50 / 1 = 50
12350 / 49 = 50

6749 / 5 = 33
6782 / 6 = 33
6815 / 7 = 33
6914 / 10 = 33
6980 / 12 = 33
7013 / 13 = 33
7046 / 14 = 33
7145 / 17 = 33
7409 / 25 = 33
7508 / 28 = 33
7541 / 29 = 33
7640 / 32 = 33

1234567890 / 1 = 1234567890
2469135780 / 2 = 1234567890
4938271560 / 4 = 1234567890
6172839450 / 5 = 1234567890
8641975230 / 7 = 1234567890
9876543120 / 8 = 1234567890

123456098 / 1 = 123456098

52364 / 1 = 52364

1205478 / 1 = 1205478
3025749816 / 512 = 1205478
3579064218 / 971 = 1205478
5237801946 / 2347 = 1205478
6150348792 / 3104 = 1205478
6531279840 / 3420 = 1205478
8150236794 / 4763 = 1205478
8197250436 / 4802 = 1205478
8561304792 / 5104 = 1205478
8790345612 / 5294 = 1205478
9160427358 / 5601 = 1205478
9730618452 / 6074 = 1205478

1245698 / 1 = 1245698
2973481650 / 389 = 1245698

52369874 / 1 = 52369874

1234506879 / 1 = 1234506879
2469013758 / 2 = 1234506879
4938027516 / 4 = 1234506879

5263417890 / 1 = 5263417890

1472583690 / 1 = 1472583690
2945167380 / 2 = 1472583690
7362918450 / 5 = 1472583690

741852963 / 1 = 741852963

4563217890 / 1 = 4563217890
9126435780 / 2 = 4563217890

9517246830 / 1 = 9517246830


125364780 / 1 = 125364780

120456987 / 1 = 120456987

358947126 / 1 = 358947126



963852741 / 1 = 963852741



14253 / 1 = 14253

[/cpp]

Regards
Riyad

[dip]

Hi,
Your code produce very few output for a particular input. I just checked some of your input. Hope it will help you. Be careful, its a multiple input problem. Keep posting.

Some of your input :
[cpp]
5

1245698

52369874

741852963

963852741

358947126

[/cpp]

Output Should Be :
[cpp]
1245698/1=1245698
12456980/10=1245698
73496182/59=1245698
429765810/345=1245698
734961820/590=1245698
9215673804/7398=1245698

52369874/1=52369874
261849370/5=52369874
523698740/10=52369874

741852963/1=741852963
1483705926/2=741852963
3709264815/5=741852963
7418529630/10=741852963

963852741/1=963852741
4819263705/5=963852741
9638527410/10=963852741

358947126/1=358947126
3589471260/10=358947126
[/cpp]

[Riyad]

i am stuck in this problem ...i have several question associated with this very problem ...
1) what will be the upper limit of n [though it is mentioned to be an integer ]
2) is default data type suitable for this problem or some thing to do with big integer ..
3) when will i stop ??? when s2==n ???? or what ???
4) can s1 have a greater value than ( 2^63 - 1 )...

thanx in advance
Riyad

[dip]

Hi,
Here is your answer .....

1. Though the problem statement mention Integer, I use double data type to avoid possible overflow.

2. Don't need big integer. You can use double or long long.

3. The highest value of S2 not more than 9876543210. So when S2 is greater than that then break.

4. No, S1 dont cross that limit.

So, try with this. Hope you will get acc . Keep posting and thank you.

[WR]

Hi,
for Riyad's input my program prints a lot more output:

Code: Select all

5 / 1 = 5
10 / 2 = 5
15 / 3 = 5
20 / 4 = 5
25 / 5 = 5

6 / 1 = 6
12 / 2 = 6
18 / 3 = 6
24 / 4 = 6
30 / 5 = 6
36 / 6 = 6

120 / 1 = 120
 ... 43 lines omitted
12960 / 108 = 120


50 / 1 = 50
 ... 16 lines omitted
2450 / 49 = 50

132 / 4 = 33
 ... 21 lines omitted
1056 / 32 = 33

1234567890 / 1 = 1234567890
2469135780 / 2 = 1234567890
4938271560 / 4 = 1234567890
6172839450 / 5 = 1234567890
8641975230 / 7 = 1234567890
9876543120 / 8 = 1234567890

123456098 / 1 = 123456098

52364 / 1 = 52364
 ... 58 lines omitted
2560913784 / 48906 = 52364

1205478 / 1 = 1205478
 ... 22 lines omitted
9816207354 / 8143 = 1205478

1245698 / 1 = 1245698
12456980 / 10 = 1245698
73496182 / 59 = 1245698
429765810 / 345 = 1245698
734961820 / 590 = 1245698
9215673804 / 7398 = 1245698

52369874 / 1 = 52369874
261849370 / 5 = 52369874
523698740 / 10 = 52369874

1234506879 / 1 = 1234506879
2469013758 / 2 = 1234506879
4938027516 / 4 = 1234506879

5263417890 / 1 = 5263417890

1472583690 / 1 = 1472583690
2945167380 / 2 = 1472583690
7362918450 / 5 = 1472583690

741852963 / 1 = 741852963
1483705926 / 2 = 741852963
3709264815 / 5 = 741852963
7418529630 / 10 = 741852963

4563217890 / 1 = 4563217890
9126435780 / 2 = 4563217890

9517246830 / 1 = 9517246830


125364780 / 1 = 125364780

120456987 / 1 = 120456987

358947126 / 1 = 358947126
3589471260 / 10 = 358947126



963852741 / 1 = 963852741
4819263705 / 5 = 963852741
9638527410 / 10 = 963852741



14253 / 1 = 14253
 ... 124 lines omitted
198473025 / 13925 = 14253

7215 / 13 = 555
 ... 134 lines omitted
304695 / 549 = 555

605 / 5 = 121
 ... 55 lines omitted
14520 / 120 = 121

but even as I get the same results as dip for his input, it's still WA.

Hints are welcome!

[Riyad]

Thanx Dip for his Help . i got ac in this problem ...it is very important to know that the upper limit for s1 is 9876543210 . i used unsigned long long as data type .

TO WR :
may be u made some silly mistake ...when u know the limits of the problem solving this should not a problem .

happy coding
Riyad

[dip]

Hi, WR
At first, sabash for Riyad. WR, your program also produce few output. For input 5, the correct output more than 100 lines. Check this input.

Input :-
[cpp]
1
52364
[/cpp]

The output should be :-
[cpp]
52364 / 1=52364
104728 / 2=52364
157092 / 3=52364
209456 / 4=52364
523640 / 10=52364
680732 / 13=52364
785460 / 15=52364
1832740 / 35=52364
1937468 / 37=52364
3089476 / 59=52364
4398576 / 84=52364
5602948 / 107=52364
6912048 / 132=52364
9530248 / 182=52364
9687340 / 185=52364
12357904 / 236=52364
13824096 / 264=52364
18275036 / 349=52364
19374680 / 370=52364
21573968 / 412=52364
35974068 / 687=52364
38906452 / 743=52364
41629380 / 795=52364
43985760 / 840=52364
50374168 / 962=52364
51369084 / 981=52364
56134208 / 1072=52364
57024396 / 1089=52364
63150984 / 1206=52364
65873912 / 1258=52364
81059472 / 1548=52364
107398564 / 2051=52364
138974056 / 2654=52364
154369072 / 2948=52364
154630892 / 2953=52364
170392456 / 3254=52364
190657324 / 3641=52364
215739680 / 4120=52364
273916084 / 5231=52364
309261784 / 5906=52364
317954208 / 6072=52364
457923180 / 8745=52364
483529176 / 9234=52364
490231768 / 9362=52364
507983164 / 9701=52364
508349712 / 9708=52364
516937408 / 9872=52364
547360892 / 10453=52364
658739120 / 12580=52364
725189036 / 13849=52364
807924156 / 15429=52364
817035492 / 15603=52364
860759432 / 16438=52364
914537260 / 17465=52364
940876352 / 17968=52364
965173248 / 18432=52364
965382704 / 18436=52364
976431508 / 18647=52364
1659834072 / 31698=52364
2560913784 / 48906=52364
3028419576 / 57834=52364
4516237908 / 86247=52364
4835291760 / 92340=52364
5139264780 / 98145=52364
6915032748 / 132057=52364
9651732480 / 184320=52364
[/cpp]
Hope it'll help you. For a input of 1234567890, you can only have 6 possible answer, because in 9876543120 / 8 = 1234567890,
9876543120 is the largest it can go. So, you must care about S2. Keep posting.

[WR]

Thanks for the data, dip. It really helped. Got accepted right now.

And, yes, Riyad, it was an unusually silly mistake!

[Antonio Ocampo]

Hi folks.

I got WA several times . I don't know what's going on. Please help me

Code: Select all

Deleted after I got AC

[mf]

You shouldn't assume that there's no solution when N has repeated digits.

My accepted program, for example, has found over 600 solutions for N=12321.

[Antonio Ocampo]

Hi mf

Thx for your hint. At last, I got AC

Keep posting

[Sedefcho]

In order to clear all misunderstandings about this problem
I'd like to share what I learnt about it while solving it. It took
me some time though to solve it as the boundaries for N, S1,
S2 were not clearly stated.

What they want in this problem is the following algorithm
( see below ). I've used Java but I give just pseudo-code here.
I hope that piece of pseudo code makes it clear. Just to note
that S1_MAX is the contant 9 876 543 210.
S2_MIN and S2_MAX are variables ( not constants ).

For the variables below use a built-in type ( no BigInteger needed )
which can hold non-negative values up to 2^63 - 1. That would
be enough.

Code: Select all

const S1_MAX=9876543210; 

function  find_And_Print_Solutions_For_N(var N){ 
        
        var S2_MIN := 1; 
        var S2_MAX := S1_MAX / N; 
        var s1 := 0; 
        var s2 := 0; 
        
        LOOP -> for s2 = S2_MIN  to S2_MAX  do the following 
        {
            1) if ( has_Repeated_Digits(s2) ) continue; 
            2) s1 := s2 * N; 
            3) if (s1 > S1_MAX) break; 
            4) if ( has_Repeated_Digits(s1) ) continue; 
            5) PRINT (s1 + " / " + s2 + " = " + N); 
        } 
        
}

One important conclusion can be made from this algorithm.
In the test data the Judge has only large numbers N.
If we suppose the opposite I would have got TLE as
for value of N < 100 my program needs too
much time to complete ( which is normal - see the
loop I have in the function posted above ). For example
for N=5 my program ran more than 3 mins and
produced more than 250 000 solutions.
So ... The Judge test data contains no small values for N

I hope these remarks make this problem clear and I hope
that the pseudo code above does not make it a spoiler.

Actually this is a very very simple problem but the fact
that some boundaries were not clearly stated had made
that problem a greater challenge than it really is.

[nymo]

I 've tried this problem a several times, but getting WA. i 've submitted the code here so that you may check what goes wrong. anyway, i know its not a good idea to post code on this forum, i 'll remove the code while its ACC.

Code: Select all

ACC now, it was a silly mistake :(

[opportunity]

error message generated by online judge is::
-----
03938035_24.c:49: integer constant out of range
03938035_24.c:49: warning: decimal integer constant is so large that it
is unsigned.
---------
guilty line is .------
if(S1>=S1_MAX)
break;

i defined S1_MAX as
#define S1_MAX 9876543210L

i tried with & without L at the end ...but result is same.....
what is the prob with this?????????.....