## 993 - Product of digits

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

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am

### 993 - Product of digits

It looked simple, I am not sure what I am missing...

This is some I/O (again, problem seemed easy), I have no idea what else I can do:

Code: Select all

5
0
1
216
1999
1000000000

Code: Select all

10
1
389
-1
555555555888
I tried printing "0", "10" and "01"(?!) for n=0. (I think that by "natural number" they mean "positive integer", but some people include a zero). Very puzzling.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Hello,

I am also getting WA. And I believe my code is right.

I also get the same output as yours for the cases you posted.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
I get wrong answer too. For N = 0 I try "0", "10", ""(empty string), "-1", all give me wrong answer.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Seems that this has been rejudged, and we all get AC~

Maybe 0 is not in the judge input?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
Hi, I just solved this problem... but I was shocked knowing that my code got AC with 0.002 secs... because the way I used is just a raw recursion (without memoization) and I think for 10^9, my code needed more time to produce the correct output. What do you think ? Is it possible that the limit for this problem is < 10^9 (i.e. 10^6,etc) ?

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
The inputs to this problem is actually very easy to solve LOL
Impossible is Nothing.

Piklu_sust
New poster
Posts: 23
Joined: Fri Sep 01, 2006 10:17 am
Location: CSE, SUST
Try with the input:
1
12

Output will be:
26

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
They should post some output that would make bruteforce TLE, like making N a 64bit integer.

Everyone should just use dp.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Everyone should just use dp.
There's a simple greedy solution.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
Yes, my dp is actually so optimized that it is greedy.

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:
I got AC...

Here is some I/O:
Input:

Code: Select all

5
0
1
17
34
22
Output:

Code: Select all

10
1
-1
-1
-1

It may be help...
Amra korbo joy akhdin............................

hasib_bd
New poster
Posts: 14
Joined: Wed Apr 30, 2008 12:39 pm

### 993 - Product of digits

Followings are some inputs/outputs generated by my AC code:
Input:

Code: Select all

17
10
123456789
216
1999
1000000000
888888888
12
24
32
48
17
34
22
288
96
1
0
Output:

Code: Select all

25
-1
389
-1
555555555888
-1
26
38
48
68
-1
-1
-1
489
268
1
10

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### 993 - Product of digits

can anyone give me some hints how to solve it???
is it to find prime factor???then multiply them in some arrangement???
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 993 - Product of digits

sazzadcsedu wrote:can anyone give me some hints how to solve it???
is it to find prime factor???then multiply them in some arrangement???
Well.. You might want to divide by 9 rather than 33, or 8 rather than 24
The higher digit is the better.. Do you think so?

CSGrandeur
New poster
Posts: 5
Joined: Tue Aug 16, 2011 11:15 am

Code: Select all

1000
41692849
577344784
802758889
870132004
3232804
462035025
399480169
15015625
3418801
428324416
870958144
15217801
793098244
307300900
4932841
316128400
22231225
719104
304851600
191158276
188265841
69189124
108910096
645617281
811908036
207619281
926045761
9030025
300363561
258437776
17859076
13883076
324180025
99301225
465696400
734897881
799136361
905769216
176438089
4080400
10000
29019769
6012304
395651881
154703844
1021505521
840130225
70560000
646735761
161604
106832896
492041124
139877929
617920164
217887121
288796036
1048334884
592679025
934891776
473584644
5294601
2108304
6130576
887364
696220996
583464025
23882769
712890000
1552516
200335716
160985344
422672481
310429161
346369321
575856009
137522529
1015250769
404613225
792309904
62457409
141110641
745290000
271458576
1058786521
92698384
636451984
422672481
201867264
483912004
13454224
228221449
272679169
93818596
8082649
934524900
7001316
1960000
2396304
315062500
265038400
926167489
174160809
37368769
31843449
758066089
327791025
1057810576
74563225
48385936
1025088289
469588900
582643044
202920025
22259524
153760000
636250176
77369616
158835609
701932036
855679504
2934369
169624576
47334400
634334596
1036904401
307546369
42640900
662596
65286400
302238225
42003361
1597696
89680900
719151489
8850625
7579009
1067067556
12888100
18464209
599074576
6869641
149279524
409941009
193600
198951025
834574321
156625225
945009081
591121969
248314564
398641156
96294969
31114084
574800625
1216609
23174596
106729561
8334769
915849
449991369
101626561
627502500
433305856
20043529
83722500
215208900
2033476
656589376
9
281199361
361152016
624450121
994708521
851063929
543356100
149866564
516652900
74839801
12837889
990235024
358761481
553896225
97574884
8462281
1012003344
299151616
953080384
791915881
838102500
54449641
58537801
630010000
570025
396487744
299497636
376996
233233984
758947401
446138884
551357361
601573729
105206049
922944400
680322889
457831609
171610000
362102841
24285184
241864704
670861801
105062500
739078596
2310400
309936025
709689600
566868481
100400400
247936516
11088900
461304484
501804801
46212804
83685904
56580484
9928801
42941809
536385600
211644304
726248601
116035984
24196561
146579449
2377764
130507776
903062601
801625969
132227001
328261924
291521476
538657681
928238089
62599744
871253289
5391684
727273024
27447121
569204164
541725625
935136400
343546225
748022500
720922500
15023376
6390784
90003169
905287744
20034576
994960849
26728900
530058529
568107225
633616
239630400
69072721
395572321
580087225
217828081
284563161
470629636
657563449
251349316
210743289
15968016
494706564
944701696
587674564
1052807809
372914721
88604569
346965129
287505936
1737124
412780489
28987456
1065891904
464574916
2090916
593263449
468029956
383846464
614656
407636100
1002862224
724148100
34845409
895505625
2232036
812421009
366224769
735440161
384316816
98446084
6315169
656025769
432964
213072409
447195609
192709924
1430416
399520144
160985344
795691264
424772100
210337009
9217296
1329409
304851600
329567716
1028549041
450203524
8538084
8608356
392079601
310112100
574081600
167133184
266407684
916151824
844251136
200505600
302794801
183223296
358572096
12766329
340993156
35724529
267813225
29506624
171845881
62267881
788037184
665949636
362407369
34234201
595360000
376748100
2067844
102010000
130873600
24780484
36905625
392634225
606883225
529736256
134722449
131836324
412130601
43191184
101485476
853808400
336942736
156725361
468895716
183223296
194184225
1026753849
802645561
19501056
125193721
596238724
580954609
759388249
606833956
236083225
6482116
22240656
65755881
374151649
190495204
164096100
240033049
410953984
182628196
412699225
836655625
1036646809
841464064
237622225
433847241
244109376
22724289
222576561
173712400
991746064
267453316
269156836
147938569
234365481
332187076
27321529
58782889
147403881
125305636
176119441
197627364
657050689
592630336
180902500
195608196
719419684
115756081
52911076
122456356
875094724
4439449
571735921
416527281
616181329
1000393641
764854336
38738176
62948356
45481536
86304100
461003841
513974241
568488649
831918649
2968729
901020289
814759936
702144004
638219169
279023616
4405801
446772769
4096
435723876
10387729
471975625
245517561
949564225
688900
79103236
659821969
578402500
43771456
2500
396900
19829209
288388324
966836836
10523536
94400656
122921569
6350400
235131556
153784801
36602500
88642225
282206401
212459776
523357129
475414416
219958561
893471881
879774921
695113225
1053197209
562685841
111323601
409576644
272118016
870604036
925558929
313537849
3583449
417058084
315666289
306565081
685584
276590161
418898089
677300625
368448025
52591504
2592100
345327889
860542225
12054784
802418929
1049760000
43349056
979564804
364351744
127260961
504496521
397364356
588289
1567
495
1867
3127
708
1730
294
4993
3394
1602
3272
24
14
1402
2812
2066
151
4155
2420
1401
1942
4435
2892
72
648
1884
4255
3778
1089
631
4816
4031
1772
616
3611
2024
1416
3564
2030
1189
3045
3440
2242
2125
624
1915
1438
4654
3051
2055
4934
1750
3624
1292
4119
1345
2719
2982
4191
2283
646
1520
3435
1584
1641
4248
81
2050
594
1117
543
2476
1154
3182
339
1005
113
2157
2932
3454
2243
2365
4569
3215
140
255
4825
2319
1277
2307
3610
3675
390
1461
2206
1745
3246
3366
3003
3981
3570
3205
3114
2972
4090
3845
635
2871
1354
545
3630
1578
1584
2333
4469
94
2329
3606
1896
523
1929
4533
1153
3530
1786
2024
690
4650
3300
1026
1403
633
623
2805
704
1382
3397
4524
1802
437
4939
189
4621
1722
641
287
610
417
3752
17
902
1373
4387
2644
523
3928
90
633
3197
3323
923
829
2671
3022
4129
2588
4559
2066
258
2092
2576
2381
2483
4436
3439
2238
3087
100
1264
953
1760
622
2697
2637
3541
702
3255
148
1044
4943
3256
3675
2106
1918
4801
1435
1953
1618
1305
1199
2729
36
61
1120
4395
2483
4069
3829
1
1723
1375
2742
2498
719
3515
1666
3917
549
1487
2280
4723
1770
844
3971
3018
4517
312
4362
215
1424
85
2847
1812
1852
1425
573
2106
996
2480
4552
4872
2885
2112
2792
2597
3068
4339
2006
2451
104
2418
3074
3917
2626
2383
2060
4466
4395
628
97
3826
997
954
1728
376
1580
3901
3934
3073
3566
3318
2583
828
2392
1313
1846
2482
1819
369
4015
2952
64
1616
91
211
3184
1283
1443
1899
2863
4468
2369
1491
2417
1490
4379
3703
2109
3623
2057
239
713
3753
1754
1172
4062
1883
2153
3601
822
484
3174
4404
2204
2481
4090
3980
3811
2398
747
940
4545
3386
4177
2401
764
180
224
3945
1334
3489
1143
877
4885
1328
2712
545
559
4023
2466
1193
852
3318
2851
2662
1076
2940
105
3321
1267
4802
947
1318
2377
2301
4491
4541
3047
2496
1039
1198
3231
2529
2288
515
3227
3874
3995
4298
89
1835
2503
986
2382
1182
997
1526
2848
2596
4134
1193
312
4014
370
705
2072
3429
4317
4686
4897
358
1487
4661
2857
2609
1396
2400
4275
137
4257
4656
4174
1721
3488
4734
4507
604
1222
1134
929
574
3683
4973
1563
4769
3001
3644
3189
123
96
2333
2715
2670
1354
3710
275
2887
339
4644
4027
3612
2275
1250
4878
144
383
3514
1555
2328
1716
2331
2038
4371
4990
1900
868
1557
2408
2088
3065
261
308
4074
3220
2016
2774
2362
3861
893
2492
3081
2645
939
1945
2817
4807
4703
2418
3361
2550
1315
3560
72
1744
3779
3568
1935
3233
2009
47
4860
2346
2860
2169
1452
1668
196
3004
2041
840
2522
4432
1796
4984
1814
4515
1573
4883
3064
2026
1865
0

Code: Select all

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
255558
-1
-1
-1
-1
-1
-1
4555577889
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
47777999
55557788
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
9
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
888899999
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
4777788
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
555599999
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
779999999
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
8888
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
45555
4557799
-1
-1
-1
-1
-1
-1
55778899
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
45555889999
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
677
-1
-1
-1
-1
38
27
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
89
899
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
25557
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
99
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
457
-1
-1
-1
-1
-1
-1
35577
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
379
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
259
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
7779
455
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
35577
-1
-1
-1
-1
-1
-1
-1
-1
-1
49
-1
4578
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3889
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
88
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
7777
-1
459
478
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
25677
357
-1
-1
27777
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
25568
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2799
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
268
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
25555
-1
289
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
4789
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
89
-1
-1
-1
-1
-1
-1
-1
25699
-1
-1
-1
-1
-1
477
-1
-1
3578
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1