MUL  Fast Multiplication
Multiply the given numbers.
Input
n [the number of multiplications <= 1000]
l1 l2 [numbers to multiply (at most 10000 decimal digits each)]
Text grouped in [ ] does not appear in the input file.
Output
The results of multiplications.
Example
Input: 5 4 2 123 43 324 342 0 12 9999 12345 Output: 8 5289 110808 0 123437655
Warning: large Input/Output data, be careful with certain languages
hide comments
Howard Roark:
20140513 18:20:42
Well, after some timings it is clear that converting a 20,000 digit integer to a base 10 string is about 1015 times slower than multiplying two 10,000 digit integers in python 3.2.3. So I have a few ideas on how to optimize the conversion. Last edit: 20130706 02:26:52 

Howard Roark:
20140513 18:20:42
Interesting; my python 3.2.3 code is too slow using native mult, and my python karatsuba implementation is slower than the native! Time to get smarter I guess to avoid the TLE. Perhaps I'm getting killed by the conversion to base10 for output? Last edit: 20130704 14:57:53 

Giovanni Botta:
20140513 18:20:42
Why is java allowed? There's no coding to be doing in java! 

Gurjaspal Singh Bedi:
20140513 18:20:42
Is bot not supporting .net framework 4.5? 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20140513 18:20:42
karatsuba just make your algorithm 2x slower than naive implementation!


Gerard Lledó:
20140513 18:20:42
Just wanted to confirm that this is solvable under one second with an O(N^2) algorithm. No need for Karatsuba... 

p0en!x:
20140513 18:20:42
Last edit: 20120926 17:46:47 

anuradha yadav:
20140513 18:20:42
My Code is working perfectly fine for each test case even the bigger ones. What could be the reason for still getting WA. Please Help :( 

Sumit Khanna:
20140513 18:20:42
Is Karatsuba the right approach?!?I wrote the code applying karatsuba and it gives correct outputs on ideone,but shows TLE here,,,http://ideone.com/8ITG0 ,,here's my code,,smbdy help plz... 

nishant10:
20140513 18:20:42
it gave wrong answer when its output r correct to my knowledge please gave some more testcase

Added by:  Darek Dereniowski 
Date:  20040601 
Time limit:  1.649s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  PAL 