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:
2014-05-13 18:20:42
Well, after some timings it is clear that converting a 20,000 digit integer to a base 10 string is about 10-15 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: 2013-07-06 02:26:52 |
|
|
Howard Roark:
2014-05-13 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: 2013-07-04 14:57:53 |
|
Giovanni Botta:
2014-05-13 18:20:42
Why is java allowed? There's no coding to be doing in java! |
|
Gurjaspal Singh Bedi:
2014-05-13 18:20:42
Is bot not supporting .net framework 4.5? |
|
(Tjandra Satria Gunawan)(曾毅昆):
2014-05-13 18:20:42
karatsuba just make your algorithm 2x slower than naive implementation!
|
|
Gerard Lledó:
2014-05-13 18:20:42
Just wanted to confirm that this is solvable under one second with an O(N^2) algorithm. No need for Karatsuba... |
|
anuradha yadav:
2014-05-13 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:
2014-05-13 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,,,<snip> ,,here's my code,,smbdy help plz... Last edit: 2023-05-17 20:50:14 |
|
nishant10:
2014-05-13 18:20:42
it gave wrong answer when its output r correct to my knowledge please gave some more testcase
|
|
Sandeep Singh Jakhar:
2014-05-13 18:20:42
nice problem of karatsuba..!! |
| Added by: | Darek Dereniowski |
| Date: | 2004-06-01 |
| Time limit: | 1.649s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
| Resource: | PAL |
RSS